algorithm - 在最接近的对中预排序点以实现 O(nlogn) 而不是 O(nlog^2n)

Question

在最近对算法中，据说根据 x 和 y 坐标对点进行预排序可以帮助将时间复杂度从 O(nlog^2n) 降低到 O(nlogn)，但这怎么可能呢？我认为presort也需要O(nlogn)的时间而不是O(n)，所以方程还是T(n)=2T(n/2)+O(nlogn)。

任何人都可以详细说明如何完成预排序以实现 O(n) 吗？还是我对此有什么误解？

Answer 1

不确定您所说的“预排序”是什么，但算法是O(n log(n))，根据these steps :

1. 首先，根据x坐标排序。

2. 递归地，分成两个大小相似的集合，除以 x_m 值。

   一个。将左右子集分别求解为 x_m。

   对于左侧的每个点，在包含右侧点的有界矩形中找到最近的点(请参阅上面链接中的详细信息)；右边的点也一样。

   返回在 b 中找到的最小距离中的最小值。

第 1 步是 O(n log(n)。第 2 步由 T(n) = 2 T(n/2) + Θ(n) 给出.