Quickselect的平均运行时间

Question

维基百科指出，快速选择算法(Link)的平均运行时间为O(n)。然而，我不能清楚地理解为什么会这样。有人能给我解释一下(通过递归关系+主方法的使用)，平均运行时间是O(n)吗？

Answer 1

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

让我们假设要从中选择k-th最小元素的字段是[1,...,n]的随机排列。我们在算法过程中选择的枢轴元素也可以被视为给定的随机排列。在算法过程中，我们总是从这个排列中选择下一个可行的轴心，因此它们被随机选择为均匀的，因为每个元素与随机排列中的下一个可行元素发生的概率相同。

有一个简单但非常重要的观察:我们只比较两个元素i和j (带有i<j)，当且仅当其中一个元素被选为范围[min(k,i), max(k,j)]中的第一个pivot元素时。如果首先选择这个范围中的另一个元素，那么它们将永远不会被比较，因为我们继续在一个子字段中搜索，其中至少有一个元素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和i < k < j

，因此max(k,j) = j

在第三种情况下，省略了不等号，因为我们已经在前两种情况中考虑了这些情况。

现在让我们来弄点计算方面的东西。我们只是将所有的概率相加，因为这给出了预期的比较次数。

案例1

​

​

​

​

案例2

与第一种情况类似，所以这仍然是一个练习。;)

案例3

​

​

​

​

​

​

我们使用H_r表示r阶调和数，它的增长类似于ln(r)。

结论

这三种情况都需要线性数量的预期比较。这表明quickselect在O(n)中确实有一个预期的运行时。注意--正如前面提到的--最坏的情况发生在O(n^2)中。

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

如果有任何错误，请告诉我。

Answer 2

在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 + ...

对方程求和并交叉抵销like值会产生线性结果。

c(n + n/2 + n/4 + ... +2+ 1) = c(2n) // GP的和

因此，它是O(n)

Answer 3

当我读到quickselect的平均时间复杂度是O(n)时，我一开始也感到非常矛盾，而我们每次都将列表一分为二(如二进制搜索或快速排序)。事实证明，每次将搜索空间一分为二并不能保证O(log )或O( n )运行时间。使快速排序O(n log n)和快速选择为O(n)的原因是，我们总是需要探索递归树的所有分支来进行快速排序，而只有一个分支来进行快速选择。让我们比较一下quicksort和quickselect的时间复杂度递归关系来证明我的观点。

快速排序：

T(n) = n + 2T(n/2)
     = n + 2(n/2 + 2T(n/4))
     = n + 2(n/2) + 4T(n/4)
     = n + 2(n/2) + 4(n/4) + ... + n(n/n)
     = 2^0(n/2^0) + 2^1(n/2^1) + ... + 2^log2(n)(n/2^log2(n))
     = n (log2(n) + 1)      (since we are adding n to itself log2 + 1 times)

快速选择：

T(n) = n + T(n/2)
     = n + n/2 + T(n/4)
     = n + n/2 + n/4 + ... n/n
     = n(1 + 1/2 + 1/4 + ... + 1/2^log2(n))
     = n (1/(1-(1/2))) = 2n                           (by geometric series)

我希望这能让你相信为什么quickselect的平均运行时间是O(n)。