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

Question

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

Answer 1

位置p划分数组后中位数的中位数介于 0.3*n 之间和 0.7*n .

那么在一轮之后，我们有三种可能:

1. p == n-k , 纯属幸运，第一个枢轴是 k -th 最大的元素，在 O(n) 中找到(中位数和分区的中位数都是 O(n))。

2. p > n-k , 然后是 k -th 最大的元素小于第一个主元，我们需要找到 k - (n-p)第一部分的第 - 个最大元素，最多有 0.7*n元素，所以找到 k 的总成本-th 最大的元素是

   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)。