algorithm - 从 (n log^2 n) 到 (n log n) 时间的最近对算法

Question

我想了解如何从 n log^2 n 时间到壁橱对算法的 n log n 时间。我得到以下部分(来自 http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html )

1. 用直线 l 将集合分成两个大小相等的部分，并递归计算每个部分中的最小距离。
2. 令 d 为两个最小距离中的最小值。
3. 消除距离 l 远于 d 的点
4. 根据 y 坐标对剩余的点进行排序
5. 按 y 顺序扫描剩余的点并计算每个点与其五个相邻点的距离。
6. 如果这些距离中的任何一个小于 d，则更新 d。

第 4 步是一种需要 O(n log n) 时间的排序，它支配所有其他步骤，这是需要减少到 O(n) 以使整个算法达到 O(n log n) 时间。这是我很难理解的部分。作者提出

第 1 步:将集合划分为...，并递归计算每个部分的距离，返回每个集合中按 y 坐标排序的点。 第 4 步:在 O(n) 时间内将两个排序列表合并为一个排序列表。

您仍然需要在递归步骤中按 y 坐标对点进行排序，这需要 O(n log n) 时间。我们怎样才能避免这种情况？合并是 O(n)，但我们仍然需要在某处进行排序。

Answer 1

O(n log n) 是一个问题的原因是我们一遍又一遍地这样做:如果我们将集合分成两个子集，并将其中的每一个划分为两个子集，然后涉及七种分类(整个集合中的一种，一半以上的两种，四分之一以上的四种)。

所以提案通过重用之前排序的结果来解决这个问题:所以我们对最小的分区进行完全合并排序(每个分区都是 O(1)，总计 O(n)) ，但对于更大的分区，我们只需要执行一次 O(n) 合并传递来合并这些结果。所以我们总共只支付 O(n log n) 次价格，这很好。