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

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

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

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

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