昨天我读了一个问题,可以通过稍加修改转化为以下问题:
点的坐标在2D空间中由(x,y)表示.
输入:点阵ARRAY = (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn)
和另一个点D = (xi, yi)
找到ARRAY距离最近的点D.
通过说"最近",我指的是欧几里德距离.
有一个明显的解决方案:遍历每个点ARRAY并计算其欧几里德距离D.然后,找到最短的距离.这可以在O(N)时间内完成.
我们可以在O(logN)中做得更快吗？我试图使用分而治之的方法,但尚未得出具体的想法.
问题的推广:如何在K维空间中找到最近的点？我们能否在低于O(N)的情况下做到这一点？
sla*_*ker 10
如果数组没有以任何方式排序,那么就不可能比O(n)更快地进行排序,因为你必须检查每个点以确保它不比你到目前为止找到的任何点更近.
您可以执行一些预处理来对点进行排序或将它们打包到某个结构中,然后对该结构进行搜索.在这种情况下,虽然预处理步骤可能比O(n)慢,但是单个搜索可能更快.如果你有很多要点来检查同一组点,这可能是有利的.