利用中间值求第k个最大元素的复杂性

Question

我正在读一篇关于通过median-of-medians算法在ardendertat找到数组中第k个最高元素的文章。在解释复杂性的部分，作者似乎忽略了一个因素，即递归地为每个分区查找median-of-medians的成本。我当然不能用初始轴来划分所有的子数组，对吧？所以这不会增加复杂性吗？在

Answer 1

对数组进行分区后，中位数的位置p介于0.3*n和{}之间。在

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

1. p == n-k，纯属运气，第一个支点是第k第二大元素，在O（n）中发现（中位数和分区都是O（n））。在

2. p > n-k，那么k-第1个最大元素比第一个轴小，我们需要找到第一个部分的第k - (n-p)-第三个最大元素，它最多有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）。在

Answer 2

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

算法简单明了：

• 选择一些轴值，p.

• ≥元素lt&p>集合所有元素（lt&sub）。

• 递归：如果S_<；至少是k，则找到S_<；中k^{th最大的元素；否则，求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ⁱn成正比，这在n中是明显的线性的

我希望这对你来说足够清楚。在

---

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