假设您有一个对象列表,每个对象都需要计算距离它最近的对象以进行拍摄。这个对象有一个 x 和一个 y 值。物体也在移动。 kd树还有用吗?我不确定,因为如果物体在移动,你必须继续创建这个 kd 树。
我可以使用什么算法以获得最佳速度(最好使用 Big O)
最佳答案
k-d 树是一种非常非常有效的数据结构,可以用坐标确定欧几里得空间中最近的邻居。
k-d 树生成(它在 O(n log²n)
中生成)需要大量对象才能产生问题,因此几乎是线性时间,搜索所有最近的邻居需要 O(n log n)
,也很便宜)。所以你可能也会对程序的其余部分有问题。
从您的问题来看,似乎您需要跟踪的只是欧几里得空间中多个点的最近邻居。我建议您从 k-d 树的普通实现开始,并且在极端和不太可能的情况下,k-d 树的生成成本太高根据时间或内存,尝试找到一种方法来跟踪每个元素的多个邻居,并仅在需要时更新列表。
但老实说,我过去一直在使用 k-d 树,我记得尽管数据集非常大(二维空间中有数千万个点),但生成和搜索速度足够快,以至于可以忽略不计其他操作。
关于c++ - KD 树仍然是用于移动物体的最佳算法之一吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59667853/