为什么选择算法的运行时间为O（n）？
根据Wikipedia的介绍，基于分区的选择算法（如quickselect）的运行时为O(n)，但我不相信它。谁能解释为什么O(n)？
在常规快速排序中，运行时为O(n log n)。每次将分支划分为两个分支（大于支点，小于支点）时，我们都需要在
分支中继续执行该过程，而quickselect只需要处理
分支。我完全理解这些观点。但是，如果你认为在二进制搜索算法后，我们选择了中间的元素，我们也只搜索 分支的一面。那使算法有效O(1)吗？
不 ，当然，二分搜索算法仍然O(log N)是O(1)。这与二进制搜索树中的搜索元素也是一样。我们只寻找
侧面，但我们仍然认为O(log n)代替O(1)。
有人可以解释为什么在quickselect，如果我们继续在寻找 一个 支点的一侧，它被认为是O(1)不是O(log n)？我认为该算法是O(n
log n)，O(N)用于分区以及O(log n)继续查找的次数。
回答：
有几种不同的选择算法，从更简单的快速选择（预期O（n），最坏情况O（n
2））到更复杂的中位数中值算法（Θ（n））。这两种算法都通过使用快速排序分区步骤（时间O（n））重新排列元素并将一个元素定位到其适当位置来工作。如果该元素位于相关索引处，则说明我们已经完成，可以返回该元素。否则，我们确定要在哪一侧递归并在那里递归。
现在让我们做一个非常强烈的假设-
假设我们正在使用quickselect（随机选择枢轴），并且在每次迭代中我们都设法猜测出数组的确切中间位置。在这种情况下，我们的算法将像这样工作：我们执行分区步骤，丢弃数组的一半，然后递归处理数组的一半。这意味着，在每个递归调用中，我们最终都在该级别上与数组的长度成比例地进行工作，但是该长度在每次迭代中都减少了两倍。如果我们算出数学（忽略常数因子等），我们将得到以下时间：
- 在第一级工作：
- 一次递归调用后工作：n / 2
- 经过两次递归调用后工作：n / 4
- 经过三个递归调用后才能工作：n / 8
- …
这意味着完成的总工作量由
n + n / 2 + n / 4 + n / 8 + n / 16 + … = n（1 + 1/2 + 1/4 + 1/8 + …）
请注意，最后一项是n的总和，等于1、1 / 2、1 / 4、1 / 8等。如果计算出这个无限和，尽管事实是存在无限多个，那么总和就是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分的东西之前，只需要两轮就可以选择一个枢轴。这是快速选择的O（n）的预期运行时所来自的地方。
对中位数中值算法的形式化分析要困难得多，因为其难易性也不易分析。直观地讲，该算法通过做少量工作来保证选择好的枢轴来工作。但是，由于进行了两个不同的递归调用，因此上述分析无法正常进行。您可以使用称为Akra-
Bazzi定理的高级结果，也可以使用big-
O的形式定义来明确证明运行时为O（n）。有关更详细的分析，请参阅Cormen，Leisserson，Rivest和Stein撰写的“算法简介，第三版”。
希望这可以帮助！
以上是 为什么选择算法的运行时间为O（n）？ 的全部内容， 来源链接： utcz.com/qa/402577.html
