x********i
发帖数: 54 | 1 一个数据库中已经有N个数据点(Xi,Yi）。给定一个新的点（X,Y），如何快速从数据库
中找到距离最近的点？ |
i******t
发帖数: 798 | |
r****s
发帖数: 1025 | 3 d=sqrt(x*2+y*2)
所有的点计算（Xi-x)**2+(Yi-y)**2,然后累计最小值。O(n)。 |
x********i
发帖数: 54 | 4 最显然的方法当然是O（N）。 楼上用kd tree怎么解呢，算法复杂度是多少？
【在 r****s 的大作中提到】
: d=sqrt(x*2+y*2)
: 所有的点计算（Xi-x)**2+(Yi-y)**2,然后累计最小值。O(n)。
|
c***0
发帖数: 449 | 5 lg n，每次刷一半，worst on
【在 x********i 的大作中提到】
: 最显然的方法当然是O（N）。 楼上用kd tree怎么解呢，算法复杂度是多少？
|
p****d
发帖数: 621 | |
t*********1
发帖数: 70 | 7 不一样，排序慢，找最近快。
【在 p****d 的大作中提到】
: 我咋感觉这就是道排序题呢
|
s********a
发帖数: 2796 | 8 什么叫每次刷一半？怎么刷啊？
【在 c***0 的大作中提到】
: lg n，每次刷一半，worst on
|
T*****u
发帖数: 7103 | 9 e...
【在 c***0 的大作中提到】
: lg n，每次刷一半，worst on
|
T*****u
发帖数: 7103 | 10 提醒一下，内存很便宜
【在 x********i 的大作中提到】
: 一个数据库中已经有N个数据点(Xi,Yi）。给定一个新的点（X,Y），如何快速从数据库
: 中找到距离最近的点？
|
t********e
发帖数: 344 | 11 什么意思？要求原来的点都sorted好才能二分吧？
【在 T*****u 的大作中提到】
: e...
|
c***0
发帖数: 449 | 12 是啊，题目说已经建立好了啊，如果你按照kd tree建立的话，查找的复杂度不是lgn吗
？建立的复杂度是排序
【在 t********e 的大作中提到】
: 什么意思？要求原来的点都sorted好才能二分吧？
|
