algorithm - 在未排序的列表中找到大约中位数

Question

我想在未排序列表中找到近似中位数，我知道两种算法

算法1-快速选择

算法 2- 中位数的中位数

我不能在我的项目中使用快速选择，因为在最坏的情况下它需要 O(n^2)。我听说过中位数的中位数，但我的同事建议它需要 O(n) 和一些常数因子。因此它的时间复杂度是 Cn 并且常数因子与快速选择相比很大。我想知道与中位数的中位数相关的常数因子是什么？为什么中位数的中位数不使用 9 元素的伪中位数？
或者他们是否有任何其他算法可以在线性时间 O(n) 中找到近似中位数？

Answer 1

虽然我不会很快放弃快速选择，因为如果选择正确的枢轴，它的最坏情况性能是非常不可能的......

也许introselect：

Introselect（“内省选择”的缩写）是一种选择算法，它混合了快速选择和中位数的中位数，具有快速的平均性能和最佳的最坏情况性能。

Introselect 的工作方式是乐观地从 quickselect 开始，如果它递归太多次而没有取得足够的进展，则只切换到最坏时间线性算法。切换策略是算法的主要技术内容。简单地将递归限制在恒定深度是不够的，因为这会使算法在所有足够大的列表上切换。Musser 讨论了几个简单的方法：

• 跟踪到目前为止处理的子分区的大小列表。如果在任何时候 k 递归调用没有减半列表大小，对于一些小的正 k，切换到最坏情况线性算法。
• 将到目前为止生成的所有分区的大小相加。如果这超过了列表大小乘以某个小的正常数 k，则切换到最坏情况线性算法。这个总和很容易在单个标量变量中跟踪。

两种方法都将递归深度限制为 k ⌈log n⌉ = O(log n)，并将总运行时间限制为 O(n)。