我正在尝试使用 KD 树平衡一组(百万以上)3D 点,我有两种方法可以做到这一点。
方式一:
使用 O(n) 算法找到沿给定轴的数组大小/第 2 大元素并将其存储在当前节点
遍历向量中的所有元素,并针对每个元素,将它们与我刚刚找到的元素进行比较,并将较小的元素放入 newArray1,将较大的元素放入 newArray2
递归
方式二:
使用快速排序 O(nlogn) 沿给定轴对数组中的所有元素进行排序,取出位置 arraysize/2 的元素并将其存储在当前节点中。
然后将索引0到arraysize/2-1的所有元素放入newArray1,将arraysize/2到arraysize-1的元素放入newArray2
递归
方法 2 似乎更“优雅”,但方法 1 似乎更快,因为中值搜索和迭代都是 O(n),所以我得到 O(2n),它只是减少到 O(n)。但是同时,虽然方式2是O(nlogn)的时间来排序,但是把数组拆分成2可以在常数时间内完成,但是是否弥补了O(nlogn)的排序时间呢?
我该怎么办?还是有我什至没有看到的更好的方法来做到这一点?
最佳答案
方式三如何:
使用诸如 QuickSelect 之类的 O(n) 算法来确保位置 length/2 处的元素是正确的元素,之前的所有元素都小于它,而之后的所有元素都大于它(无需对它们进行完全排序! ) - 这可能是您在方法 1 的第 1 步中使用的算法...
递归到每一半(中间元素除外)并重复下一个轴。
请注意,您实际上不需要制作“节点”对象。您实际上可以将树保存在一个大数组中。搜索时,从第一个轴的 length/2 开始。
我已经看到 ELKI 使用了这个技巧。它使用非常少的内存和代码,这使得树非常快。
关于performance - 平衡 KD 树 : Which approach is more efficient?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17021379/