从 (n log^2 n) 到 (n log n) 时间的最近对算法
Closest pair algorithm from (n log^2 n) to (n log n) time
我想了解如何从 n log^2 n 时间到壁橱对算法的 n log n 时间。我得到以下部分（来自 http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html）
- 用直线l将集合分成两个大小相等的部分，并递归计算每个部分中的最小距离。
- 令 d 为两个最小距离中的最小值。
- 消除距离 l 远于 d 的点
- 根据 y 坐标对剩余的点进行排序
- 按 y 顺序扫描剩余的点并计算每个点与其五个相邻点的距离。
- 如果这些距离中的任何一个小于 d，则更新 d。
第 4 步是一种需要 O(n log n) 时间的排序，它支配所有其他步骤，这是需要减少到 O(n) 以使整个算法实现 O( n log n) 时间。这是我很难理解的部分。作者提出
第1步：将集合分成...，并递归计算每个部分的距离，返回每个集合中的点按y坐标排序。
第四步：在O(n)时间内将两个排序列表合并为一个排序列表。
您仍然需要在递归步骤中按 y 坐标对点进行排序，这需要 O(n log n) 时间。我们怎样才能避免这种情况？合并是 O(n)，但我们仍然需要在某处进行排序。
他们的建议是你有两个（已经排序的列表）A 和 B。可以使用 merge sort 将它们组合成一个排序列表（只是步骤 (4) 中的合并步骤）种类）。
合并排序的结果是一个包含A和B所有成员的排序列表。一旦合并，就不需要再次排序。
O(n log n) 是一个问题的原因是我们一遍又一遍地这样做：如果我们将集合划分为两个子集，并将每个子集划分为两个子集，然后涉及七种（整个集合中的一种，一半以上的一半，四分之一以上的四种）。
因此提案通过重用先前排序的结果来解决此问题：因此我们对最小分区（每个分区都是 O(1)，总计 O(n))，但对于较大的分区，我们只需要执行一次 O(n) 合并传递来合并这些结果。所以我们总共只支付O(n log n)次的价格就可以了。
我提供了一个可能更容易理解的替代解决方案。首先对所有点 w.r.t 的 y 坐标进行排序。这是一次使用 O (n log n) 。有 n 个点，在排序后的数组中，每个点都有某个索引，该索引最多为 n。保存每个点的索引（为点数据结构的索引添加整数）。然后运行原算法。这一次，在我们要对点进行排序的那一刻，不要用普通的比较排序对它们进行排序。但是根据它们的索引对它们进行排序。我们可以根据它们的索引用 O(n) 中的基数排序对它们进行排序。所以整个过程是O(n log n)，因为我们只用了一次比较排序，剩下的就是T(n)=2T(n/2)+O(n)。但是常数不如问题中建议的修改。
问题中建议的修改过程类似于合并排序中的合并：当我们有两个排序列表时，我们不需要使用普通排序再次对它们进行排序，我们可以通过将它们合并到 O ( n).
我想了解如何从 n log^2 n 时间到壁橱对算法的 n log n 时间。我得到以下部分（来自 http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html）
- 用直线l将集合分成两个大小相等的部分，并递归计算每个部分中的最小距离。
- 令 d 为两个最小距离中的最小值。
- 消除距离 l 远于 d 的点
- 根据 y 坐标对剩余的点进行排序
- 按 y 顺序扫描剩余的点并计算每个点与其五个相邻点的距离。
- 如果这些距离中的任何一个小于 d，则更新 d。
第 4 步是一种需要 O(n log n) 时间的排序，它支配所有其他步骤，这是需要减少到 O(n) 以使整个算法实现 O( n log n) 时间。这是我很难理解的部分。作者提出
第1步：将集合分成...，并递归计算每个部分的距离，返回每个集合中的点按y坐标排序。 第四步：在O(n)时间内将两个排序列表合并为一个排序列表。
您仍然需要在递归步骤中按 y 坐标对点进行排序，这需要 O(n log n) 时间。我们怎样才能避免这种情况？合并是 O(n)，但我们仍然需要在某处进行排序。
他们的建议是你有两个（已经排序的列表）A 和 B。可以使用 merge sort 将它们组合成一个排序列表（只是步骤 (4) 中的合并步骤）种类）。
合并排序的结果是一个包含A和B所有成员的排序列表。一旦合并，就不需要再次排序。
O(n log n) 是一个问题的原因是我们一遍又一遍地这样做：如果我们将集合划分为两个子集，并将每个子集划分为两个子集，然后涉及七种（整个集合中的一种，一半以上的一半，四分之一以上的四种）。
因此提案通过重用先前排序的结果来解决此问题：因此我们对最小分区（每个分区都是 O(1)，总计 O(n))，但对于较大的分区，我们只需要执行一次 O(n) 合并传递来合并这些结果。所以我们总共只支付O(n log n)次的价格就可以了。
我提供了一个可能更容易理解的替代解决方案。首先对所有点 w.r.t 的 y 坐标进行排序。这是一次使用 O (n log n) 。有 n 个点，在排序后的数组中，每个点都有某个索引，该索引最多为 n。保存每个点的索引（为点数据结构的索引添加整数）。然后运行原算法。这一次，在我们要对点进行排序的那一刻，不要用普通的比较排序对它们进行排序。但是根据它们的索引对它们进行排序。我们可以根据它们的索引用 O(n) 中的基数排序对它们进行排序。所以整个过程是O(n log n)，因为我们只用了一次比较排序，剩下的就是T(n)=2T(n/2)+O(n)。但是常数不如问题中建议的修改。
问题中建议的修改过程类似于合并排序中的合并：当我们有两个排序列表时，我们不需要使用普通排序再次对它们进行排序，我们可以通过将它们合并到 O ( n).