aiwiki.page
中文
计算机 / 算法与理论 / median-of-medians

中位数的中位数

中位数的中位数是一种确定性的枢轴选择方法,可在最坏情况下以线性时间找到任意指定秩的元素。

18 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
中位数排序算法时间复杂度快速选择递归插入排序伪代码计算复杂性中位数的中…

中位数的中位数是一种为选择算法选取枢轴的确定性方法,使算法能够在最坏情况下以线性时间找到任意指定秩的元素。其标准形式是将输入划分为每组五个元素,找出各组的中位数,再通过递归选择这些中位数的精确中位数。这个枢轴不一定是原始输入的中位数,但它能保证每一步选择都可以排除固定比例的元素。这种方法通常与 BFPRT 算法联系在一起,后者以曼努埃尔·布卢姆、罗伯特·W. 弗洛伊德、沃恩·普拉特、罗纳德·L. 里维斯特和罗伯特·E. 塔扬的姓名命名。

选择问题

给定 nn 个具有一致次序关系的元素,以及一个满足 1≤k≤n1 \leq k \leq n 的整数 kk,选择问题要求找出第 kk 小的元素。这个值称为次序统计量。重复值各自占据不同的秩:在序列 2,2,5,92,2,5,9 中,第二小的元素是 22。

选择问题包括寻找最小值、最大值或中位数。对于偶数个数值,统计学上的中位数通常定义为中间两个次序统计量的算术平均值;选择算法可以直接返回这两个中间元素中的任意一个,如果需要计算平均值,也可以分别找出两者。

一种做法是先对全部输入排序,再取出指定位置的元素。基于比较的排序算法通常需要 O(nlog⁡n)O(n\log n) 时间,而选择问题并不要求得到完整的排序结果。在通常假设比较和元素操作都耗费常数时间的前提下,中位数的中位数方法可达到最坏情况下 Θ(n)\Theta(n) 的时间复杂度。

算法

中位数的中位数方法为一种基于划分的选择过程提供枢轴,这一过程与快速选择密切相关。该过程在两处使用递归:一处是从各组中位数中选择枢轴,另一处是在原始输入的相应分区中继续查找。

对于非空输入序列 AA 和从 1 开始计数的有效秩 kk,步骤如下:

  1. 直接处理小规模输入。 对其排序,并返回秩为 kk 的元素。
  2. 分组。 将输入按每组五个元素划分,至多有一组不足五个。
  3. 找出各组中位数。 对每组排序并取出其中间元素。如果最后一组的元素个数为偶数,可以始终按同一约定选取中间两个元素中的任意一个。
  4. 选择枢轴。 递归地选择各组中位数组成的序列的精确中位数。
  5. 划分输入。 将元素分为小于、等于和大于枢轴的三部分。
  6. 仅在必要的分区中继续查找。 如果目标秩落在等于枢轴的分区中,就返回枢轴;否则调整秩,并在相应的严格小于或严格大于枢轴的分区中递归查找。

由于每组的大小固定,对所有组排序的总时间仅为 O(n)O(n)。对于这些很小的分组,使用插入排序这样的简单方法就足够了。

伪代码

以下伪代码使用从 1 开始计数的秩,并在序列长度为偶数时选择两个中间元素中较小的一个:

SELECT(A, k):
    要求 1 <= k <= length(A)

    如果 length(A) <= 5:
        对 A 排序
        返回 A[k]

    M = 空序列

    对 A 中每个至多包含 5 个元素的连续分组 G:
        对 G 排序
        将 G[ceil(length(G) / 2)] 追加到 M

    p = SELECT(M, ceil(length(M) / 2))

    L = A 中严格小于 p 的元素
    E = A 中等于 p 的元素
    R = A 中严格大于 p 的元素

    如果 k <= length(L):
        返回 SELECT(L, k)

    如果 k <= length(L) + length(E):
        返回 p

    返回 SELECT(R, k - length(L) - length(E))

对于重复值,三路划分十分重要。如果所有输入元素都等于枢轴,算法在划分后就会立即终止。如果某种实现将等于枢轴的元素送入递归分支,却不控制该分支的规模,就可能无法维持预期的最坏情况性能保证。

为什么枢轴能保证足够均衡的划分

考虑所有包含五个元素的完整分组。计入中位数本身,每组至少有三个元素不大于该组中位数,也至少有三个元素不小于它。

由于枢轴 pp 是各组中位数的中位数:

  • 大约一半的组中位数不大于 pp;
  • 大约一半的组中位数不小于 pp。

因此,每个符合条件的完整分组都为相应的计数下界贡献三个元素。考虑取整以及可能存在的不完整分组后,输入中至少有

3n10−O(1)\frac{3n}{10}-O(1)

个元素不大于 pp,也至少有同样多的元素不小于 pp。

因此,严格小于或严格大于枢轴的每个分区至多包含

7n10+O(1)\frac{7n}{10}+O(1)

个元素。完成输入划分后,即使在最不利的情况下,选择过程也能排除大约 30% 的元素。

对于互不相同的元素,这通常被描述为选取一个大致位于第 30 百分位与第 70 百分位之间的枢轴。存在重复值时,使用非严格不等关系的计数论证,以及对严格小于或严格大于枢轴的分区规模的界定,才是更精确的表述。

示例

假设有 2525 个互不相同的元素,分成五组,每组五个。设五个组中位数按大小排列为

m1<m2<m3<m4<m5.m_1 < m_2 < m_3 < m_4 < m_5.

选出的枢轴为 p=m3p=m_3。

以 m1,m2,m3m_1,m_2,m_3 为中位数的三个组,每组都至少包含三个不大于 pp 的元素,因此这样的元素至少有九个。同理,以 m3,m4,m5m_3,m_4,m_5 为中位数的三个组,共提供至少九个不小于 pp 的元素。因此,严格小于或严格大于枢轴的任一分区都不可能包含超过 1616 个元素。

这个例子说明,枢轴不必是全部 2525 个元素的精确中位数,也能有效地用于选择。

最坏情况复杂度

设 T(n)T(n) 表示最坏情况下的运行时间。选择各组中位数的中位数时,需要处理大约 n/5n/5 个元素。随后的选择调用至多处理大约 7n/107n/10 个元素。分组、查找固定大小分组的中位数以及划分都需要线性时间,因此有

T(n)≤T ⁣(⌈n5⌉)+T ⁣(7n10+O(1))+O(n).T(n) \leq T\!\left(\left\lceil\frac{n}{5}\right\rceil\right) + T\!\left(\frac{7n}{10}+O(1)\right) + O(n).

关键关系是

15+710=910<1.\frac{1}{5}+\frac{7}{10}=\frac{9}{10}<1.

忽略有界的取整影响,递归子问题的总规模会按固定比例缩小。因此,总工作量可以用一个几何级数来界定:

n+9n10+(910)2n+⋯=O(n).n+\frac{9n}{10} +\left(\frac{9}{10}\right)^2n+\cdots =O(n).

只要将直接处理的基本情形阈值设得足够大,取整项就不会改变这一界限。划分本身需要检查输入,因此标准实现的最坏情况时间为 Θ(n)\Theta(n)。这与一般的基于比较的选择问题在最坏情况下的渐近下界相符。

为什么每组五个?

五是一个较小的奇数组大小,而且直接分析就能证明递归子问题的总规模严格缩小。

如果每组三个元素,忽略取整后,类似的基本估计为

T(n)≤T(n/3)+T(2n/3)+O(n),T(n)\leq T(n/3)+T(2n/3)+O(n),

其中递归项的规模比例之和等于一,因此这个递推式给出的是 O(nlog⁡n)O(n\log n) 上界,而不能据此证明线性时间。这并不意味着所有采用三元素分组的算法都需要超线性时间:改进的分组策略可以获得更强的保证。

采用七或九等更大的固定奇数组大小,也可以通过同样的一般论证实现线性时间选择。它们的实际开销取决于计算各组中位数的方法和具体实现细节。

历史意义

布卢姆、弗洛伊德、普拉特、里维斯特和塔扬在 1973 年的论文《选择问题的时间界限》(Time Bounds for Selection)中发表了他们关于选择问题的成果。他们的算法称为 PICK,确立了确定性的最坏情况线性时间选择算法。

这一成果在计算复杂性领域具有重要意义,因为它表明,寻找中位数并不需要对输入排序。选择与排序对信息的需求不同:无需确定每一对元素之间的相对次序,也能找出指定的次序统计量。

现代介绍通常采用更简单的五元素分组形式来解释 BFPRT 成果。原始论文对比较次数进行了更细致的分析;不应认为标准教科书中的过程能够复现原论文中的所有常数。

与其他算法的关系

快速选择

快速选择围绕枢轴划分输入,并只在一个分区中继续查找。如果以均匀随机的方式选择枢轴,其期望运行时间为线性,但最坏情况下的运行时间为平方级。

中位数的中位数方法用确定性的规模保证替代了这种概率上的均衡性。它既不需要随机抽样,也不依赖于对输入初始排列的任何假设。代价则是需要额外的工作来构造具有保证的枢轴。在实践中,随机化算法或简单的启发式枢轴选择方法,在普通输入上可能更快。

三数取中枢轴选择

中位数的中位数不同于三数取中,后者是快速排序中常用的一种枢轴选择启发式方法。三数取中选取三个样本元素的中位数,这三个元素通常是某一区间的首元素、中间元素和末元素。仅凭这些样本,并不能保证整个区间中有固定比例的元素位于枢轴的任意一侧。

同样,反复对小分组取中位数,直到只剩下一个代表元素,也不一定就是标准的中位数的中位数算法。标准方法中的关键步骤,是选择全部组中位数组成的序列的精确中位数。

内省选择与混合方法

内省选择将快速的选择过程与旨在防止病态行为的后备策略结合起来。中位数的中位数可以作为一种线性时间的后备方法。

仅有后备方法,并不能证明整个混合算法具有线性时间界。切换触发条件还必须限制切换前完成的工作量:如果允许执行许多轮规模几乎等于完整输入的划分,那么在启用后备方法之前,就可能已经累积了超线性的工作量。

实现与应用

上面的伪代码为各组中位数和各分区分配独立的序列,因此这种直接实现需要 O(n)O(n) 的辅助空间复杂度。基于数组的实现可以原地重排元素,将各组中位数移到数组前部,并在不使用与输入等规模的辅助数组的情况下完成划分。直接采用递归的原地实现需要 O(log⁡n)O(\log n) 的调用栈空间。

当选择操作的最坏情况性能保证很重要时,中位数的中位数方法就很有用,应用包括精确分位数计算、围绕指定秩进行划分,以及计算几何中需要均衡划分的算法。它也是分析递归子问题规模不相等的分治法的一个标准示例。

它在实践中的主要局限是额外开销:反复处理分组和递归选择枢轴,可能比更简单的枢轴策略耗费更多时间。此外,其线性时间界描述的是特定计算模型下的基本操作次数。开销高昂的比较、大型记录以及内存访问成本,都可能显著影响实际运行时间,但不会改变基于比较的渐近性能保证。