用中位数求第k个最大元素的复杂度

Question

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

Answer 1

划分数组后中位数的位置p在0.3*n和0.7*n之间。

因此，在一轮之后，我们有三种可能性：

幸运的是，第一个轴心点是O(n)中的

1. p == n-k，k-th最大元素(中位数和分区的中位数都是O(n)).
2. p > n-k，，那么-th最大元素小于第一个轴心点，我们需要找到第一部分的k - (n-p)-th最大元素，它最多有0.7*n个元素，所以找到k-th最大元素的总成本是

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

• p < n-k，然后我们需要找到第二部分(在透视之后)的k-th最大元素，该部分也至多是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)。