algorithm - 为什么选择算法的运行时间是 O(n)？

Question

根据 Wikipedia ，基于分区的选择算法(例如 quickselect)的运行时间为 O(n) ，但我对此并不信服。谁能解释为什么是O(n) ？

在正常的快速排序中，运行时间是O(n log n) .每次我们将分支分成两个分支(大于主元和小于主元)，我们需要在两个分支中继续处理，而quickselect只需要处理一个分支。我完全理解这些观点。 但是，如果你认为在二分搜索算法中，我们选择了中间元素之后，我们也只搜索分支的一侧。算法也是如此 O(1) ？ 不，二分查找算法当然还是O(log N)而不是 O(1) .这也与二叉搜索树中的搜索元素相同。我们只搜索一面，但我们仍然考虑O(log n)而不是 O(1) .

有人能解释一下为什么在 quickselect 中，如果我们继续在枢轴的 one 侧搜索，它被认为是 O(1)而不是 O(log n) ？我认为算法是 O(n log n) , O(N)用于分区，O(log n)为继续查找的次数。

Answer 1

有几种不同的选择算法，从更简单的快速选择(预期 O(n)，最坏情况 O(n²))到更复杂的中位数算法 (Θ (n)).这两种算法都通过使用快速排序分区步骤(时间 O(n))重新排列元素并将一个元素定位到其正确位置来工作。如果该元素在相关索引处，我们就完成了，可以直接返回该元素。否则，我们确定在哪一侧递归并在那里递归。

现在让我们做一个非常有力的假设 - 假设我们正在使用快速选择(随机选择基准)并且在每次迭代中我们设法猜测数组的确切中间位置。在那种情况下，我们的算法将像这样工作:我们进行分区步骤，丢弃数组的一半，然后递归处理数组的一半。这意味着在每次递归调用中，我们最终所做的工作与该级别的数组长度成正比，但该长度在每次迭代中不断减少两倍。如果我们计算出数学(忽略常数因子等)，我们最终得到以下时间:

• 第一级工作:n
• 一次递归调用后工作:n/2
• 两次递归调用后工作:n/4
• 三个递归调用后的工作:n/8
• ...

这意味着完成的总功为

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...)

请注意，最后一项是 1、1/2、1/4、1/8 等的总和的 n 倍。如果计算出这个无限总和，尽管存在无限多项，总和sum 正好是 2。这意味着总的工作是

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...) = 2n

这可能看起来很奇怪，但我们的想法是，如果我们在每个级别上进行线性工作，但继续将数组切成两半，我们最终只会做大约 2n 次工作。

这里的一个重要细节是，这里确实有 O(log n) 次不同的迭代，但并非所有迭代都在做等量的工作。实际上，每次迭代的工作量是前一次迭代的一半。如果我们忽略工作量正在减少的事实，您可以得出工作量为 O(n log n) 的结论，这是正确的但不是紧界。这种更精确的分析使用了完成的工作在每次迭代中不断减少的事实，给出了 O(n) 运行时间。

当然，这是一个非常乐观的假设——我们几乎永远不会得到 50/50 的分配! - 但使用此分析的更强大版本，您可以说，如果您可以保证任何常数因子拆分，则完成的总功只是 n 的某个常数倍。如果我们在每次迭代中选择一个完全随机的元素(就像我们在 quickselect 中所做的那样)，那么在我们最终选择数组中间 50% 的一些枢轴元素之前，我们只需要选择两个元素，这意味着，期望，在我们最终选择给出 25/75 拆分的东西之前，只需要两轮选择一个枢轴。这就是 quickselect 的 O(n) 预期运行时间的来源。

中位数算法的正式分析要困难得多，因为递归很难且不易分析。直观地说，该算法通过做少量工作来保证选择一个好的枢轴来工作。但是，由于进行了两次不同的递归调用，因此上述分析将无法正常进行。您可以使用称为 Akra-Bazzi theorem 的高级结果。 ，或者使用 big-O 的正式定义来显式证明运行时间是 O(n)。如需更详细的分析，请查看 Cormen、Leisserson、Rivest 和 Stein 合着的“算法导论，第三版”。