是否有可能计算出一个优于O(n log n)的数字列表的中位数？

Question

我知道可以计算O(n)中数字列表的平均值.但中位数呢？有没有比排序(O(n log n))和查找中间元素更好的算法(如果列表中的偶数项,则是两个中间元素的平均值)？

Answer 1

该链接讨论了"中位数的中位数",换句话说,是"真实"中位数的近似值.我不确定OP是什么要求的. (2认同)
@Chris Jester-Young:它确实谈到了"中位数的中位数",但只作为算法的中间值 - 而不是结果!该算法确实在O(N)中找到中位数(不是中位数的中位数),最坏的情况是时间. (2认同)

Answer 2

你所说的是一种选择算法,其中k = n/2.有一种基于quicksort中使用的相同分区函数的方法.毫不奇怪,它被称为快速选择.虽然它可以像快速排序一样具有O(n ²)最坏的情况,但是可以使用适当的枢轴选择将其降低到线性时间.

Answer 3

部分无关紧要,但是:快速提示如何快速找到网上常见基本问题的答案.

高效计算样本中位数

即使排序n项通常采用O(n log n)运算,通过使用"分而治之"算法,n项的中位数只能用O(n)运算来计算(事实上,你总能找到k使用此方法的值列表的第_个元素;这称为选择问题).

...有最坏情况的线性时间选择算法....