为什么选择算法O（n）的运行时间？

Question

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

在常规快速排序中，运行时间为O(n log n)。每次将分支划分为两个分支（大于枢轴，小于枢轴）时，我们需要在both]分支中继续该过程，而quickselect只需要处理one分支。我完全理解这些观点。但是，如果您考虑使用二进制搜索算法，则在选择中间元素之后，我们也仅搜索分支的one侧。那是否使算法成为O(1)？ 否，当然，二进制搜索算法仍然是O(log N)而不是O(1)。这与二进制搜索树中的搜索元素也是一样。我们仅搜索one面，但是我们仍然考虑使用O(log n)而不是O(1)。

有人可以解释为什么在快速选择中，如果我们继续在轴的one

一侧进行搜索，将其视为O(1)而不是O(log n)？我认为该算法是O(n log n)，用于分区的O(N)和用于继续查找的次数的O(log n)。

根据Wikipedia，基于分区的选择算法（例如quickselect）的运行时间为O（n），但我对此并不感到信服。谁能解释为什么它是O（n）？在常规快速排序中，...

Answer 1

有几种不同的选择算法，从简单得多的快速选择（预期O（n），最坏情况O（n ²

Answer 2

让我来解释选择和二进制搜索之间的区别。

Answer 3

在Quicksort中，递归树的深度为lg（N）个级别，每个级别都需要O（N）个工作量。因此，总运行时间为O（NlgN）。

Answer 4

Quicksort没有nlogn的big-O-最坏的情况是运行时是n ^ 2。

Answer 5

由于选择，您不一定要排序。您可以简单地计算多少个具有给定值的项目。因此，可以通过计算每个值出现多少次，并选择值上下各占50％的值来执行O（n）中位数。它是1通过数组，只是为数组中的每个元素增加一个计数器，所以它是O（n）。