第9章 中位数和顺序统计

导读

顺序统计（Order Statistics）是数据处理中的基本问题。给定一组数据，第i个顺序统计就是排序后第i个位置的元素。最小值是第1个顺序统计，最大值是第n个顺序统计，中位数是第⌊(n+1)/2⌋个顺序统计。

本章将讨论如何高效地选择顺序统计，特别是中位数。我们将从最简单的情况（最小值和最大值）开始，逐步深入到一般性的选择问题，最终介绍在最坏情况下也能保证线性时间的BFPRT算法。

核心概念详解

9.1 顺序统计的定义

给定一个包含n个元素的集合和一个整数i（1 ≤ i ≤ n），第i个顺序统计是指集合中第i小的元素。

特殊情况：

• i = 1：最小值
• i = n：最大值
• i = ⌊(n+1)/2⌋：下中位数
• i = ⌈(n+1)/2⌉：上中位数

中位数：

• n为奇数时，中位数唯一，为第⌊(n+1)/2⌋个顺序统计
• n为偶数时，通常取下中位数或上中位数，或两者的平均值

9.2 最小值和最大值

同时找最小值和最大值：

朴素方法需要2(n-1)次比较（分别找最小和最大）。通过成对比较可以优化到⌊3n/2⌋次比较。

SIMULTANEOUS-MIN-MAX(A)
    if n为奇数
        min = max = A[1]
        start = 2
    else
        if A[1] < A[2]
            min = A[1], max = A[2]
        else
            min = A[2], max = A[1]
        start = 3
    for i = start to n step 2
        if A[i] < A[i+1]
            if A[i] < min
                min = A[i]
            if A[i+1] > max
                max = A[i+1]
        else
            if A[i+1] < min
                min = A[i+1]
            if A[i] > max
                max = A[i]
    return min, max

比较次数分析：

• 每对元素需要3次比较（1次比较两个元素，2次分别与min和max比较）
• 共有⌊n/2⌋对
• 总比较次数：⌊3n/2⌋ - 1（或⌊3n/2⌋，取决于n的奇偶性）

下界证明：

找最小值至少需要n-1次比较（每个非最小元素至少输一次）。类似地，找最大值也至少需要n-1次比较。但通过成对比较，可以共享部分比较信息，将总比较次数降低到⌊3n/2⌋。

9.3 期望线性时间的选择算法

RANDOMIZED-SELECT算法基于快速排序的分区思想：

RANDOMIZED-SELECT(A, p, r, i)
    if p == r
        return A[p]
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q - p + 1
    if i == k
        return A[q]
    else if i < k
        return RANDOMIZED-SELECT(A, p, q - 1, i)
    else
        return RANDOMIZED-SELECT(A, q + 1, r, i - k)

工作原理：

随机选择主元并分区

主元的位置q-p+1就是它在排序后的位置

如果i等于这个位置，返回主元

如果i小于这个位置，递归在左半部分查找

如果i大于这个位置，递归在右半部分查找

期望时间分析：

设T(n)为期望时间。在最坏情况下，每次分区都产生最不平衡的划分，但期望情况下：

T(n) ≤ (1/n) · Σ(k=1 to n) T(max(k-1, n-k)) + O(n)

通过代入法可以证明T(n) = O(n)。

直觉上，每次分区后，期望情况下子问题规模减半，总时间为：

n + n/2 + n/4 + ... = 2n = O(n)

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

BFPRT算法（Blum-Floyd-Pratt-Rivest-Tarjan）在最坏情况下也能保证O(n)时间。

算法步骤：

SELECT(A, p, r, i)
    // 步骤1：将元素分组
    将A[p..r]分成⌈(r-p+1)/5⌉组，每组5个元素（最后一组可能不足5个）
    
    // 步骤2：找每组的中位数
    对每组进行插入排序，返回每组的中位数
    
    // 步骤3：递归找中位数的中位数
    创建中位数数组M
    pivot = SELECT(M, 1, ⌈n/5⌉, ⌈⌈n/5⌉/2⌉)
    
    // 步骤4：以pivot为基准分区
    q = PARTITION-AROUND(A, p, r, pivot)
    
    // 步骤5：递归选择
    k = q - p + 1
    if i == k
        return A[q]
    else if i < k
        return SELECT(A, p, q - 1, i)
    else
        return SELECT(A, q + 1, r, i - k)

关键分析——为什么中位数的中位数是好主元：

中位数的中位数M保证：

• 至少⌈n/5⌉/2 = ⌈n/10⌉个组的中位数≤M
• 每个这样的组至少有3个元素≤M（包括中位数本身和两个比中位数小的元素）
• 因此至少有3·⌈n/10⌉ ≥ 3n/10个元素≤M
• 类似地，至少有3n/10个元素≥M

所以，以M为主元分区后，两个子问题的规模都不超过7n/10。

递归式：

T(n) ≤ T(⌈n/5⌉) + T(7n/10) + O(n)

证明T(n) = O(n)：

假设T(n) ≤ cn

T(n) ≤ c·⌈n/5⌉ + c·7n/10 + an

≤ cn/5 + c + 7cn/10 + an

= 9cn/10 + c + an

= cn - cn/10 + c + an

当c足够大使得cn/10 ≥ c + an（即c ≥ 10a），有T(n) ≤ cn。

9.5 选择问题的下界

定理：在最坏情况下，选择第i小的元素至少需要Ω(n)次比较。

证明思路：

• 任何选择算法必须至少"看到"每个元素一次
• 否则，未看到的元素可能是答案
• 因此至少需要n-1次比较

这个下界与RANDOMIZED-SELECT和BFPRT的O(n)上界匹配，说明线性时间是最优的。

9.6 多个顺序统计的选择

如果需要同时找到多个顺序统计（如所有四分位数），有两种策略：

独立选择：

• 对每个顺序统计独立调用SELECT
• 时间：O(kn)，k为顺序统计的个数

排序后选择：

• 先排序，然后直接读取
• 时间：O(n log n)

分治选择：

• 先找中间的顺序统计
• 将问题分为两个子问题
• 递归求解
• 时间：O(n log k)

当k = O(n/log n)时，排序后选择更优；否则分治选择更优。

9.7 中位数的应用

中位数在算法设计中有广泛的应用：

1. 划分问题：

• 将集合分为大小相等的两部分
• 用于负载均衡、并行计算

2. 最近点对问题：

• 使用中位数划分点集
• 分治求解

3. 线性时间中位数滤波：

• 图像处理中的去噪
• 使用中位数替代平均值

4. 快速排序的主元选择：

• 使用中位数作为主元
• 保证平衡分区

9.8 选择算法的实现细节

BFPRT的分组大小：

• 为什么选择5？因为5是最小的奇数，使得递归式T(n) = T(n/5) + T(7n/10) + O(n)有线性解
• 如果用3分组：T(n) = T(n/3) + T(2n/3) + O(n)，解为O(n log n)
• 如果用7分组：也可以，但常数更大

实际应用中的选择：

• BFPRT虽然理论最优，但常数因子大
• 实践中RANDOMIZED-SELECT更快
• 某些标准库使用Introselect（结合RANDOMIZED-SELECT和BFPRT）

9.9 近似中位数

在某些场景下，不需要精确的中位数，只需要一个接近中位数的元素。

Munro-Paterson算法：

• 使用O(log n)额外空间
• 在数据流中近似中位数
• 精度与空间成正比

随机采样：

• 随机抽取O(log n)个元素
• 返回采样中的中位数
• 以高概率接近真实中位数

9.10 顺序统计树

顺序统计树是在二叉搜索树的每个节点上增加子树大小信息的数据结构。

支持的操作：

• INSERT：O(log n)
• DELETE：O(log n)
• SELECT(i)：找第i小的元素，O(log n)
• RANK(x)：找x的排名，O(log n)

实现：

使用红黑树或AVL树，在每个节点维护子树大小。通过子树大小信息，可以在O(log n)时间内找到任意顺序统计。

重要知识点

知识点1：期望分析与最坏情况分析的区别

RANDOMIZED-SELECT的期望时间为O(n)，但最坏情况为O(n²)。BFPRT的最坏时间为O(n)。在实际应用中，需要根据场景选择：

• 对最坏情况敏感：使用BFPRT
• 追求平均性能：使用RANDOMIZED-SELECT

知识点2：中位数的中位数的性质

中位数的中位数保证至少3n/10个元素≤它，至少3n/10个元素≥它。这个性质是BFPRT算法正确性的关键。

知识点3：选择问题与排序问题的关系

选择问题是排序问题的推广。排序可以解决选择问题（排序后直接读取），但选择问题不需要完全排序。选择问题的下界是Ω(n)，而排序的下界是Ω(n log n)。

知识点4：分组大小的选择

BFPRT算法中，分组大小为5是最优选择。太小（如3）不能保证线性时间，太大（如7）增加常数因子。

知识点5：选择算法在实际系统中的实现

C++的std::nth_element使用Introselect算法，结合了快速选择和BFPRT的优点。Java和Python也有类似的选择算法实现。

常见误区

误区1：找中位数需要排序

找中位数不需要完全排序。RANDOMIZED-SELECT和BFPRT都可以在O(n)时间内找到中位数，而不需要排序所有元素。

误区2：BFPRT在实践中最快

虽然BFPRT在最坏情况下是O(n)，但由于较大的常数因子，实践中RANDOMIZED-SELECT通常更快。理论最优不等于实践最优。

误区3：选择问题的下界是Ω(n log n)

选择问题的下界是Ω(n)，不是Ω(n log n)。只有排序的下界才是Ω(n log n)。

误区4：分组大小必须是5

5是最优的分组大小，但不是唯一的选择。7、9等也可以，只是常数因子更大。3则不行，因为不能保证线性时间。

误区5：顺序统计树是多余的

如果需要频繁查询不同的顺序统计，顺序统计树比每次调用SELECT更高效。INSERT和DELETE后仍然可以O(log n)查询。

实践应用

应用1：数据库查询优化

数据库系统使用选择算法优化查询：

• LIMIT/OFFSET子句
• 百分位数计算
• Top-K查询

应用2：统计分析

中位数在统计分析中广泛应用：

• 描述数据的中心趋势
• 异常值检测
• 非参数统计

应用3：图像处理

中值滤波是图像处理中的重要技术：

• 使用中位数替代平均值
• 有效去除椒盐噪声
• 保持边缘信息

应用4：负载均衡

在分布式系统中，中位数用于负载均衡：

• 将任务按中位数分为两组
• 分配给不同的处理器
• 保证两组工作量大致相等

应用5：快速选择在实际系统中的应用

• C++ std::nth_element
• Python的heapq.nsmallest/nlargest
• SQL的PERCENTILE_CONT/PERCENTILE_DISC

9.11 选择算法的详细正确性证明

RANDOMIZED-SELECT的期望时间分析：

设T(n)为期望运行时间。在第i次分区后，子问题规模为max(i-1, n-i)的概率各为1/n。

T(n) ≤ (1/n) · Σ(i=1 to n) T(max(i-1, n-i)) + cn

由于max(i-1, n-i) ≥ n/2当i ≤ n/2或i > n/2时：

T(n) ≤ (2/n) · Σ(i=⌊n/2⌋ to n-1) T(i) + cn

假设T(n) ≤ c'n，代入验证：

T(n) ≤ (2/n) · Σ(i=⌊n/2⌋ to n-1) c'i + cn

≤ (2/n) · c' · (3n²/8) + cn

= (3c'n/4) + cn

= c'n(3/4 + 1/c')

当c' ≥ 4时，3/4 + 1/c' ≤ 1，因此T(n) ≤ c'n。

BFPRT的递归式求解：

T(n) ≤ T(⌈n/5⌉) + T(7n/10) + O(n)

使用代入法证明T(n) ≤ cn：

T(n) ≤ c·n/5 + c + c·7n/10 + an

= 9cn/10 + c + an

= cn - cn/10 + c + an

当cn/10 ≥ c + an，即c ≥ 10a时，T(n) ≤ cn。

9.12 选择算法的工程实现

Introselect：

C++ std::nth_element使用的算法：

先使用RANDOMIZED-SELECT

如果递归深度超过阈值，切换到BFPRT

结合两者的优点：平均快速，最坏保证

小数组优化：

• n ≤ 5：直接排序后返回
• n ≤ 20：使用插入排序后直接索引
• 避免递归开销

重复元素处理：

当数组中有大量重复元素时，标准分区可能产生不平衡划分。三路分区（类似快速排序的三路分区）可以高效处理这种情况。

9.13 顺序统计树的详细实现

红黑树基础上的顺序统计树：

每个节点增加size字段，表示以该节点为根的子树中的节点数。

SELECT操作：

OS-SELECT(x, i)
    r = x.left.size + 1
    if i == r
        return x
    else if i < r
        return OS-SELECT(x.left, i)
    else
        return OS-SELECT(x.right, i - r)

RANK操作：

OS-RANK(T, x)
    r = x.left.size + 1
    y = x
    while y ≠ T.root
        if y == y.parent.right
            r = r + y.parent.left.size + 1
        y = y.parent
    return r

维护size字段：

INSERT和DELETE操作需要更新沿路径上所有节点的size字段。由于路径长度为O(log n)，更新时间为O(log n)。

9.14 中位数在机器学习中的应用

中位数滤波：

• 去除异常值的影响
• 鲁棒估计的中心趋势

中位数机制：

• 分布式系统中的共识算法
• 联邦学习中的安全聚合

分位数回归：

• 中位数回归是L1损失的特殊情况
• 对异常值更鲁棒

9.15 选择问题的扩展

多个顺序统计的同时选择：

如果需要同时找到第i₁, i₂, ..., iₖ个顺序统计：

• 独立选择：O(kn)
• 排序后选择：O(n log n)
• 分治选择：O(n log k)

加权中位数：

给定n个元素和权重w₁...wₙ（Σwᵢ = 1），加权中位数xₖ满足：

Σ(xᵢ < xₖ) wᵢ < 1/2 且 Σ(xᵢ > xₖ) wᵢ ≤ 1/2

可以在O(n)时间内找到。

在线中位数维护：

使用两个堆（最大堆+最小堆）维护数据流的中位数：

• 插入：O(log n)
• 查询中位数：O(1)
• 空间：O(n)

本章小结

本章深入讨论了顺序统计的选择问题。我们学习了：

顺序统计的定义：第i个顺序统计是排序后第i个位置的元素。中位数是最重要的顺序统计。

最小值和最大值：通过成对比较，可以在⌊3n/2⌋次比较内同时找到。

RANDOMIZED-SELECT：基于快速排序的分区思想，期望时间O(n)，最坏O(n²)。详细的期望分析。

BFPRT算法：通过中位数的中位数选择主元，保证最坏情况O(n)。递归式的严格求解。

选择问题的下界：Ω(n)，与算法的上界匹配。

工程实现：Introselect、小数组优化、重复元素处理。

顺序统计树：基于红黑树，支持O(log n)的SELECT和RANK操作。

应用：中位数在划分、滤波、负载均衡、机器学习等方面的应用。

选择问题是算法设计中的经典问题。理解选择算法的设计思想和分析方法，对于掌握更复杂的算法至关重要。

关键术语

思考题

证明：在最坏情况下，找第二小的元素需要n + ⌈log n⌉ - 2次比较。

设计一个算法，在O(n)时间内找到数组中第k小和第k大的元素。

分析当BFPRT算法的分组大小改为7时，时间复杂度如何变化。

设计一个顺序统计树，支持在O(log n)时间内查询第i小的元素和元素的排名。