【Unsolved】线性时间选择算法的复杂度证明

时间:2022-11-25 08:56:02

线性时间选择算法中,最坏情况仍然可以保持O(n)。

原因是通过对中位数的中位数的寻找,保证每次分组后,任意一组包含元素的数量不会大于某个值。

普通的Partition最坏情况下,每次只能排除一个元素,所以会造成O(n2)的复杂度。

具体证明可以参考: 王云鹏论文《线性时间选择算法时间复杂度深入研究》