第09章 中位数与序统计 — 章节汇总

章节概览

本章研究了选择问题（Selection Problem）——从 $n$ 个元素中找出第 $i$ 小的元素（即第 $i$ 个序统计量）。 surprising 的是，选择问题可以在 $\Theta (n)$ 时间内解决——与找最小值一样快。本章从最简单的最小/最大值问题出发（9.1 最小值和最大值），介绍了实用的随机化选择算法 RANDOMIZED-SELECT（9.2 期望线性时间选择），以及理论意义重大的确定性线性时间选择算法 SELECT（9.3 最坏情况线性时间选择，即 BFPRT 算法）。

---

9.1 最小值和最大值

小节	核心主题	关键结论
9.1 最小值和最大值	MINIMUM/MAXIMUM、同时找最小最大	最小/最大各需 $n-1$ 次比较；同时找需 $\lceil 3n/2\rceil -2$ 次

核心思路：找最小值（或最大值）的下界为 $n-1$ 次比较——通过锦标赛论证，每个非胜者元素至少输掉一场比赛。同时找最小和最大值时，先将元素成对比较，较大者与当前最大比较、较小者与当前最小比较，总比较次数 $\lceil 3n/2\rceil -2$，比分别找的 $2n-2$ 次节省约 25%。

---

9.2~9.3 选择算法

小节	核心主题	关键结论	特点
9.2 期望线性时间选择	RANDOMIZED-SELECT	期望 $\Theta (n)$，最坏 $\Theta (n^2)$	实用，常数因子小
9.3 最坏情况线性时间选择	SELECT（BFPRT）	最坏 $\Theta (n)$	理论意义大，常数因子大

核心思路：9.2 期望线性时间选择 的 RANDOMIZED-SELECT 类似快速排序的分区，但只递归处理包含目标元素的一侧，因此期望时间从快速排序的 $\Theta (n\lg n)$ 降至 $\Theta (n)$。9.3 最坏情况线性时间选择 的 SELECT 通过”中位数的中位数”策略选择保证良好的枢轴——将数组分为 $\lceil n/5\rceil$ 组，取每组中位数，再递归取这些中位数的中位数作为枢轴，保证至少 30% 的元素在两侧，从而在最坏情况下也达到 $\Theta (n)$。

---

本章核心知识点

关键定义

概念	定义	出处
序统计量（$i$th order statistic）	集合中第 $i$ 小的元素	9.1 最小值和最大值
中位数	$i=\lfloor (n+1)/2\rfloor$ 时的序统计量	9.1 最小值和最大值
选择问题	找出第 $i$ 个序统计量	9.2 期望线性时间选择

关键过程与复杂度

过程	功能	期望时间	最坏时间
MINIMUM	找最小值	$\Theta (n)$	$\Theta (n)$
RANDOMIZED-SELECT	随机化选择第 $i$ 小	$\Theta (n)$	$\Theta (n^2)$
SELECT	确定性选择第 $i$ 小	$\Theta (n)$	$\Theta (n)$

核心定理

编号	内容	出处
定理 9.1	RANDOMIZED-SELECT 的期望运行时间为 $\Theta (n)$	9.2 期望线性时间选择
定理 9.2	SELECT 的最坏情况运行时间为 $\Theta (n)$	9.3 最坏情况线性时间选择

---

与前序章节的知识关联

前序章节	关联方式
第7章 快速排序	RANDOMIZED-SELECT 基于快速排序的 PARTITION；SELECT 使用类似的分区思想
第5章 概率分析	指示器随机变量用于 RANDOMIZED-SELECT 的期望分析
第4章 分治策略	代入法用于 SELECT 的递归关系式求解
第8章 线性时间排序	选择问题是排序问题的简化版本；中位数是重要的序统计量

---

学习路线

第9章学习路径：
  9.1 最小值和最大值（基础问题，建立下界意识）
    → 9.2 期望线性时间选择（实用算法，RANDOMIZED-SELECT）
      → 9.3 最坏情况线性时间选择（理论算法，BFPRT）

学习建议

本章展示了”看似需要排序的问题实际上可以更快解决”的典型范例。9.2 的 RANDOMIZED-SELECT 是工程中最常用的选择算法，务必掌握其与快速排序的区别（单侧递归 vs 双侧递归）。9.3 的 SELECT 是理论计算机科学的杰作——BFPRT 算法，其”中位数的中位数”策略虽然常数因子大，但证明了选择问题的线性时间下界是可达的。

中位数与序统计