python - 使用中位数的中位数找到第 k 个最大元素的复杂性

Question

我正在阅读有关通过ardendertatmedian-of-medians的算法查找数组中第 k 个最高元素的文章。在解释复杂性的部分，作者似乎忽略了一个因素，即递归查找每个分区的成本。当然，我不能按初始枢轴对所有子阵列进行分区，对吧？那么这不会增加复杂性吗？median-of-medians

Answer 1

中位数算法是为快速选择算法开发的，它与快速排序非常相似，但实际上是线性的，而不是 O(n log n)，因为它只在分区的一侧递归。选择问题是选择集合S中第k^大的元素；找到中位数是 k = (|S| + 1)/2 的特殊情况。

该算法很简单：

• 选择一些枢轴值，p。

• 将元素分成两组：S _<（所有元素 < p）和 S _≥（所有元素 ≥ p）。

• 递归：如果 S _<至少为 k，则在 S _{<中找到第 k}^个最大的元素；_{否则，在 S ≥}中找到 (k - |S _< |) ^th最大的元素。

与快速排序一样，关键是找到枢轴值。我们将按如下方式进行：

• 构造由 S的每组五个元素的中_{位数组成的 S 个中位数。}

• 通过递归调用 select找到 S 个_中位数的确切中位数。

现在，|S_中位数| 正好是 0.2 * |S|。此外，一旦我们有了主元，我们就知道 max(|S _< |, |S _≥ ) ≤ 0.7 * |S|。[fn 1] 所以对 select 的两个递归调用总和为 0.9 * |S|。

^{所以我们现在可以证明计算 select 的时间与 Σ0.9 i} n成正比，这在 n 中显然是线性的。

我希望这对你来说已经足够清楚了。

---

在不明显的情况下，S 中位数中的一半中_位数必须至少为 p（因为 p 是它们的中位数），并且对于与这些中位数相对应的每组五个，五个元素中的三个（中位数和两个较大的元素）必须至少为 p。所以这是 S 中总元素的 50% 的 60%，或 30%。一个类似的论点适用于用“最多”代替“至少”，所以我们知道两个子集中较小的一个至少是 S 大小的 30%，因此较大的一个最多是大小的 70%。

Answer 2

p对数组进行分区后的中位数的位置在0.3*n和之间0.7*n。

所以一轮之后，我们有三种可能：

1. p == n-k，纯粹靠运气，第一个枢轴是第k-th 大元素，在 O(n) 中找到（中位数和分区的中位数都是 O(n)）。

2. p > n-k，则第k-th大元素小于第一个pivot，我们需要找到k - (n-p)第一部分的第-th大元素，其中元素最多，因此找到第-th大元素0.7*n的总成本为k

   T(n) <= T(0.7*n) + C*n
   

3. p < n-k，那么我们需要找到k第二部分（枢轴之后）的第-个最大元素，该部分也最多0.7*n元素大，所以我们再次得到估计

   T(n) <= T(0.7*n) + C*n
   

迭代，我们发现

T(n) <= T((0.7)^k * n) + C*(1 + 0.7 + ... + (0.7)^(k-1))*n
     <= T(1) + C/(1 - 0.7)*n

这显然是 O(n)。