Algorithm complexity of neighbor list

[lhycms]

I want to use neighbor list do something. But i can't figure out the implementation in https://github.com/deepmodeling/deepmd-kit/blob/master/source/lib/src/neighbor_list.cc.
What confuse me is the algorithm complexity of this implementation. Is it $O(N^2)$?

[njzjz]

Yes.

[lhycms]

Thanks for your help.

[wanghan-iapcm]

several implementations are provided, which one do you mean?

[lhycms]

I see there are many implementation of builld_nlist(). Is there a implementation similar to Lammps, whose algorithm complexity is $O(N)$?

[njzjz]

To be clear, although there are several implementations, only build_nlist_cpu is actually used, whose complexity is $O(N^2)$.

[lhycms]

Got it. Thanks