x*i2010-04-07 07:045 楼最显然的方法当然是O(N)。 楼上用kd tree怎么解呢,算法复杂度是多少?【在 r****s 的大作中提到】: d=sqrt(x*2+y*2): 所有的点计算(Xi-x)**2+(Yi-y)**2,然后累计最小值。O(n)。
c*02010-04-07 07:046 楼lg n,每次刷一半,worst on【在 x********i 的大作中提到】: 最显然的方法当然是O(N)。 楼上用kd tree怎么解呢,算法复杂度是多少?
T*u2010-04-07 07:0411 楼提醒一下,内存很便宜【在 x********i 的大作中提到】: 一个数据库中已经有N个数据点(Xi,Yi)。给定一个新的点(X,Y),如何快速从数据库: 中找到距离最近的点?
c*02010-04-07 07:0413 楼是啊,题目说已经建立好了啊,如果你按照kd tree建立的话,查找的复杂度不是lgn吗?建立的复杂度是排序【在 t********e 的大作中提到】: 什么意思?要求原来的点都sorted好才能二分吧?