使用k阶统计量查找无序列表中的第K个元素 - 时间复杂度O(n)？

Question

有人能告诉我随机选择算法如何获得O(n)的平均时间复杂度吗？我知道如果在第一次遍历时随机选择的主元素是列表中的第k个元素，则它将具有最佳情况O(n)。但是这怎么可能是平均情况呢？我们无法保证每次运行算法时都能在第一次遍历中命中正确的主元素，对吧？

- broun

Answer 1

在随机选择位置并分割当前范围后，我们知道第k个元素是在左侧还是右侧。然后我们在一侧上递归算法。因此，平均复杂度为T(n) = n + T(n/2)（n为分割）。因此，平均情况下的时间复杂度为O(n)。

- Andrey Sboev

Answer 2

第一轮过后，你就知道第k个元素会在哪一半。现在你在那一半上重复这个过程，以此类推。

因此，在平均情况下，第一次迭代需要n步，第二次需要n/2步，然后是n/4步，以此类推。作为一个简单的计算，假设n = 2**k。总步数将会是

2**k + 2**k/2 + 2**k/4 + ... = 2**k + 2**(k-1) + 2**(k-2) + ... + 2 + 1 
                             = 2**(k+1) - 1 
                             = 2n - 1

所以，该算法的时间复杂度为O(2n - 1) = O(n)。

- user515430