g*****u
发帖数: 298 | 1 给你x-y坐标轴上n个点，求每个点的K个最近邻，K为常数。比较好的算法有吗？有低于
O(n^2)的解法吗？（我觉得应该没有，但是好的算法肯定还是会快一些的。） |
c*****t
发帖数: 1879 | 2 用 Delaunay triangle / Voronoi diagram 的话应该可以更快。光算
triangle / diagram 的话是 O (n log n)。
对于每个点搞定 k 个 neighbor 花的时间应该是 O (k)。因为你这个 k 是
constant，所以总共是 O (n log n)
【在 g*****u 的大作中提到】
: 给你x-y坐标轴上n个点，求每个点的K个最近邻，K为常数。比较好的算法有吗？有低于
: O(n^2)的解法吗？（我觉得应该没有，但是好的算法肯定还是会快一些的。）
|
y*******g
发帖数: 6599 | 3 kd tree, quadtree之类的方法可以
ps :你做facebook的puzzle?
【在 g*****u 的大作中提到】
: 给你x-y坐标轴上n个点，求每个点的K个最近邻，K为常数。比较好的算法有吗？有低于
: O(n^2)的解法吗？（我觉得应该没有，但是好的算法肯定还是会快一些的。）
|
c*****z
发帖数: 182 | 4 search for ANN if you only need approximate neighbors,
the lower bound should be NlogN,
【在 g*****u 的大作中提到】
: 给你x-y坐标轴上n个点，求每个点的K个最近邻，K为常数。比较好的算法有吗？有低于
: O(n^2)的解法吗？（我觉得应该没有，但是好的算法肯定还是会快一些的。）
|
I*********g
发帖数: 93 | 5 厉害啊。一直在想这道题怎么做。
没有想到这个现成的数据结构。还是书看少了。
【在 y*******g 的大作中提到】
: kd tree, quadtree之类的方法可以
: ps :你做facebook的puzzle?
|
