arrays - 最近的点对（CLRS pg 1043）：将排序数组拆分为两个排序数组的运行时间

Question

在 O(nlgn) 时间内找到最接近的点对时，用于将排序列表拆分为两个排序列表的伪代码（CLRS 3rd ed pg 1043）据说在 O(n) 时间内运行。

但是，这假设第 4 行以恒定时间运行，我很难相信（如果它存储为二叉树，我假设它在 O(lgn) 时间内运行，总运行时间为 O(nlgn) .

Y 是一个排序数组，YL 和 YR 是两个新的子数组。PL 是随机顺序的 Y 的子集，而 YL 是相同的子集，但按排序顺序。

我的推理哪里出了问题？

Answer 1

为简单起见，我们假设列表是整数而不是字符串或整数，这会使事情变得非常复杂。

这里有两个计算需要考虑：

1. for循环：这运行了Y次，我假设这里是N
2. 棘手的部分 - Y[i] 与 PL 的比较（注意：如果我们认为它们是字长的，两个数字的比较是恒定的）。现在，访问 Y[i] 是不变的，因为我们正在处理随机访问机器。但是，要将其与长度为 PL 的数组进行比较，例如，k 将花费 k 时间。如果这个 k 非常小并且与输入数组 Y 的大小无关，理想情况下这将是常数。

以更高的精度编写它意味着您需要考虑 k 次比较所花费的时间（PL 的长度），因此，此伪代码的总时间将为 O(Nk)。但是，如果 k 是随机的且独立于 N 的假设成立，那么它确实是 O(N)

Answer 2

我不知道它在书中应该如何工作，但是考虑一下算法的样子，您可以提出以下想法：

• Y[i], X[i], YL[i], XL[i],YR[i]和XR[i]是整数，对应于i第 th 点的索引（所以你只需要存储一些全局数组，给定索引，返回xory坐标）。
• PL[i]是一个布尔值，true如果第i-th 点在左边，false否则。

在每个递归步骤中，您可以PL[i]使用y坐标（O(n)时间）进行计算。然后你使用书中的算法将点集分成两组“左”和“右”，将线替换为if Y[i] in PL（if PL[Y[i]]这样的访问是O(1)，所以总的来说我们得到O(n)）。

这具有O(n)时间复杂性并使用O(n)内存。

因此，在 中以这种方式解决了最近对问题T(n) = O(n log n)。