算法分析与设计

Appearance

3.6 顺序统计量：选择比排序容易 ​

这一节，你能解决什么问题 ​

学完这一节，你能够：

  1. 理解"选择比排序容易"的核心洞察，知道找第 k 小只需要 Θ(n)，而排序需要 Θ(n log n)
  2. 分析随机选择和确定性选择的复杂度，理解"期望 vs 最坏"的权衡
  3. 判断什么时候用选择而不是排序，避免"过度求解"浪费

问题情境 ​

某数据分析平台需要实时计算数据流的中位数。

工程师小刘的实现：

python
def median(data):
    sorted_data = quicksort(data)  # Θ(n log n)
    return sorted_data[len(data) // 2]

同事看到后问："为什么每次计算中位数都要排序？你只需要一个元素的位置，为什么要给出所有元素的顺序？"

问题：计算中位数需要 Θ(n log n) 吗？

答案：不需要。选择问题可以 Θ(n)。

直观思路 ​

先问自己一个问题：我需要什么信息？

排序：给出全部顺序信息 → Θ(n log n) 选择：给出局部位置信息 → Θ(n)

为什么差距这么大？

排序要确定 n 个元素的相对顺序。n! 种排列，需要 lg(n!) ≈ n log n bit 信息。

选择只要确定一个元素的位置——"左边有多少个元素"。只有 n 种可能位置，lg n bit 信息。

关键洞察：信息量差距 n 倍 → 复杂度差距也是。

规范定义 ​

顺序统计量 ​

定义：第 k 小的元素（第 1 小是最小值，第 n 小是最大值，第 ⌈n/2⌉ 小是中位数）

选择问题：给定 n 个元素，找到第 k 小的元素

复杂度对比 ​

问题复杂度信息需求
排序全部元素Θ(n log n)全部顺序信息
找第 k 小Θ(n)一个位置信息
找最小值Θ(n)最小是哪个
同时找 min 和 maxΘ(⌈3n/2⌉ - 2)min 和 max

算法实现 ​

随机选择：期望 Θ(n) ​

类似快排的分区，但只递归一边。

python
def randomized_select(A, p, r, k):
    if p == r:
        return A[p]
    
    q = partition(A, p, r)       # 分区
    i = q - p + 1                 # pivot 的排名
    
    if k == i:                    # pivot 就是第 k 小
        return A[q]
    elif k < i:                   # 第 k 小在左边
        return randomized_select(A, p, q-1, k)
    else:                         # 第 k 小在右边
        return randomized_select(A, q+1, r, k-i)

一步步执行：

找 [3, 2, 9, 0, 7, 5, 4, 8, 6, 1] 的第 4 小

Step 1：随机 pivot = 5（索引 5）
分区：[3, 2, 0, 4, 1 | 5 | 9, 7, 8, 6]
pivot 排名 = 6

第 4 小 < 第 6 小 → 在左边 [3, 2, 0, 4, 1]

Step 2：在左边找第 4 小
pivot = 2
分区：[0, 1 | 2 | 3, 4]
pivot 排名 = 3

第 4 小 > 第 3 小 → 在右边 [3, 4]，找第 (4-3) = 1 小

Step 3：在 [3, 4] 找第 1 小
pivot = 3，排名 1 → 找到！

答案：第 4 小是 3

确定性选择（BFPRT）：最坏 Θ(n) ​

用"5 元组"技巧，保证 pivot 不极端。

python
def bfprt(A, k):
    # 1. 分组：每组 5 个
    groups = [A[i:i+5] for i in range(0, len(A), 5)]
    
    # 2. 找每组中位数
    medians = [median_of_5(g) for g in groups]
    
    # 3. 找中位数的中位数（作为 pivot）
    pivot = bfprt(medians, len(medians)//2)
    
    # 4. 分区
    # 5. 递归一边

这个方法是怎么想到的 ​

随机选择的思路 ​

问题：怎么快速找到第 k 小？

朴素想法：排序后取第 k 个 → Θ(n log n)

洞察：类似快排分区，但只递归一边。

关键：分区后，pivot 的位置告诉我们第 k 小在哪一边。

确定性选择的思路 ​

问题：随机选择最坏 Θ(n²)。怎么保证最坏 Θ(n)？

洞察：保证 pivot 不极端 → 递归规模保证缩小。

为什么是 5？

分组大小影响递归规模：

分组大小系数和是否收敛复杂度
31/3 + 2/3 = 1不收敛Θ(n log n)
51/5 + 7/10 = 0.9收敛Θ(n)
71/7 + 9/14 ≈ 0.78收敛Θ(n)

分组 5 是最小的可行选择。

正确性分析 ​

随机选择：期望 Θ(n) ​

为什么期望 Θ(n)？

快排递归两边：期望深度 Θ(log n)，总时间 Θ(n log n)。

选择只递归一边：期望总规模 = n + n/2 + n/4 + ... = Θ(2n)。

关键：只递归一边，总规模是几何级数。

确定性选择：最坏 Θ(n) ​

为什么最坏 Θ(n)？

分组 5 保证：

  • 至少 3n/10 个元素 ≤ pivot
  • 至少 3n/10 个元素 ≥ pivot

递归规模 ≤ 7n/10。

T(n) ≤ T(n/5) + T(7n/10) + Θ(n)
     = Θ(n)  （系数和 0.9 < 1）

复杂度分析 ​

方法期望时间最坏时间适用场景
随机选择Θ(n)Θ(n²)一般场景
BFPRTΘ(n)Θ(n)需要最坏保证

什么时候不该用这个方法 ​

该用选择的情况 ​

  • 找第 k 小（单个位置信息）
  • 找中位数
  • 找最小值或最大值
  • Top-k 且 k << n

该用排序的情况 ​

  • 需要全部顺序信息
  • 多次查询不同位置
  • 需要稳定性（选择算法不稳定）

本节小结 ​

解决了什么问题？

找第 k 小元素，Θ(n) 而不是 Θ(n log n)。

核心方法是什么？

  • 随机选择：分区 + 递归一边
  • 确定性选择：分组 5 + 中位数的中位数

为什么正确？

分区保证 pivot 在正确位置。递归缩小规模。

代价是什么？

  • 随机选择：期望 Θ(n)，最坏 Θ(n²)
  • 确定性选择：最坏 Θ(n)，但常数大

适用场景？

需要单个位置信息，不需要全部顺序。

练习 ​

基本理解 ​

练习 1：对 [3, 2, 9, 0, 7, 5, 4, 8, 6, 1]，找中位数（第 5 小），手动执行随机选择。

练习 2：为什么分组 3 不能保证线性时间？写出递归方程验证。

方法应用 ​

练习 3：同时求 min 和 max。

朴素方法：逐个比较，比较次数 2(n-1)。

优化方法：成对比较，比较次数 ⌈3n/2⌉ - 2。

为什么成对比较更高效？写出分析。

错误诊断 ​

练习 4：以下实现有什么问题？

python
def select_bug(A, k):
    q = partition(A, 0, len(A)-1)
    if k == q:
        return A[q]
    elif k < q:
        return select_bug(A[:q], k)    # ← 这里
    else:
        return select_bug(A[q+1:], k)  # ← 这里

分析：递归范围和 k 的处理是否正确？

方案比较 ​

练习 5：场景选择。

场景应该用什么？理由
找最小值
找中位数
找第 10 小（查询一次）
找第 k 小（查询 100 次，不同 k）
Top-50（n = 10^6）

开放设计 ​

练习 6：数据流中位数。

设计一个 Skill，实时计算数据流的中位数：

  • 支持动态插入
  • 支持快速查询中位数
  • 分析复杂度

提示：可以用两个堆（最大堆 + 最小堆）。

上一节：3.5 线性时间排序

下一节：3.7 哈希与随机化

新时代的算法课程