Quickselect的平均运行时间

Question

维基百科指出,quickselect算法(Link)的平均运行时间为O(n).但是,我无法清楚地知道这是怎么回事.任何人都可以向我解释(通过递归关系+主方法使用)关于平均运行时间如何是O(n)？

Answer 1

因为

我们已经知道了我们想要的元素所在的分区.

我们不需要对所有元素进行排序(通过分区),而只需对我们需要的分区进行操作.

作为快速排序,我们要做的半分*,然后在半的一半,但这个时候,我们只需要做好下一轮的分区在一个单独的两个分区(一半),其中元素预期躺在.

这就像(不太准确)

n + 1/2 n + 1/4 n + 1/8 n + ..... <2 n

所以它是O(n).

_{为方便起见使用了一半,实际分区并不精确50%.}

Answer 2

要对quickselect进行平均情况分析,必须考虑在算法期间对每对元素进行比较并假设随机旋转的可能性.由此我们可以得出平均比较数.不幸的是,我将展示的分析需要更长的计算,但它是一个干净的平均案例分析,而不是当前的答案.

让我们假设我们想要选择第 - k个最小元素的字段是随机排列[1,...,n].我们在算法过程中选择的枢轴元素也可以看作给定的随机排列.在算法期间,我们总是从该置换中选择下一个可行的枢轴,因此随机选择它们,因为每个元素具有与随机置换中的下一个可行元素相同的发生概率.

有一个简单但非常重要的观察:我们只比较两个元素i和j(有i<j)当且仅当其中一个被选为范围中的第一个枢轴元素时[min(k,i), max(k,j)].如果首先选择此范围中的另一个元素,那么它们将永远不会被比较,因为我们继续搜索其中至少包含一个元素的子字段i,j.

由于上述观察和该枢轴被选择均匀的随机比较的概率之间的事实的i和j是:

2/(max(k,j) - min(k,i) + 1)

(两种max(k,j) - min(k,i) + 1可能的事件.)

我们将分析分为三个部分:

1. max(k,j) = k因此 i < j <= k
2. min(k,i) = k因此 k <= i < j
3. min(k,i) = i并且max(k,j) = j,因此i < k < j

在第三种情况下,省略了不太相等的符号,因为我们已经在前两种情况下考虑了这些情况.

现在让我们的手在计算上有点脏.我们只是总结了所有概率,因为这给出了预期的比较次数.

情况1

案例2

与案例1类似,所以这仍然是一个练习.;)

案例3

我们使用H_r大约相似的r次谐波数ln(r).

结论

所有三种情况都需要线性数量的预期比较.这表明quickselect确实具有预期的运行时间O(n).请注意 - 如前所述 - 最糟糕的情况是O(n^2).

注意:这个证明的想法不是我的.我认为这大致是quickselect的标准平均案例分析.

如果有任何错误,请告诉我.

Answer 3

在指定的quickselect中，我们仅对分区的一半应用递归。

平均案例分析：

第一步：T（n）= cn + T（n / 2）

其中，cn =执行分区的时间，其中c为任何常数（无关紧要）。
T（n / 2）=对一半分区应用递归。
由于这是平均情况，因此我们假设分区为中位数。

在继续进行递归时，我们得到以下等式：

T（n / 2）= cn / 2 + T（n / 4）
T（n / 4）= cn / 2 + T（n / 8）
。
。
。
T（2）= c.2 + T（1）
T（1）= c.1 + ...

对方程求和并进行交叉抵消，得出线性结果。

c（n + n / 2 + n / 4 + ... + 2 +1）= c（2n） // GP的总和

因此，它是O（n）