2.2 线性时间选择算法

这一篇讲一个会让你重新认识"分治"威力的算法。问题很简单：给 $n$ 个数，找出第 $k$ 小的那个。（中位数就是 $k=\lceil n/2\rceil$ 的特例。）

最朴素的解法是先排序再取第 $k$ 个， $O(n\log n)$ 。但我们要做的是——不排序， $O(n)$ 搞定。 这听起来不可思议：找第 $k$ 小居然能比排序还快一整个 $\log n$ 因子？能。这就是 Blum、Floyd、Pratt、Rivest、Tarjan 五人在 1973 年给出的线性时间选择算法（常被叫做 "Median-of-Medians" 中位数的中位数法）。它也是分治思想最精彩的运用之一。

1.关键想法：划分，然后只递归一边

回忆快排的 PARTITION（2.1）：选个基准，把数组划成"小左大右"，基准归位到某个位置 $q$ 。如果基准归位到了第 $q$ 个位置，那它就是第 $q$ 小。

选择算法的洞见：我们不需要把两边都排好。归位后，如果 $k=q$ ，基准就是答案，完事；如果 $k<q$ ，答案只在左半边，只递归左半边；如果 $k>q$ ，只递归右半边。每次只走一边，不像快排要走两边。

RANDOMIZED-SELECT(A, p, r, k)   // 找 A[p..r] 里第 k 小
    if p == r: return A[p]
    q = RANDOMIZED-PARTITION(A, p, r)
    i = q - p + 1                 // 基准是当前段第 i 小
    if k == i: return A[q]
    elseif k < i: return RANDOMIZED-SELECT(A, p, q-1, k)
    else: return RANDOMIZED-SELECT(A, q+1, r, k-i)

如果用随机选基准，期望复杂度是 $\Theta(n)$ ——因为每次只递归一边，期望代价是个等比递减的级数 $n+n/2+n/4+\cdots=O(n)$ 。这已经够实用了。

但期望 $O(n)$ 不满足我们。我们要的是最坏情况 $O(n)$ ——不管输入多刁钻、随机数多倒霉，都保证线性。这就需要一个更聪明的选基准方法。

2.中位数的中位数：保证基准"不太偏"

随机选基准，期望很好，但运气差时会偏。我们要找一个基准，保证它既不会太小也不会太大——具体说，保证它至少比 $30\%$ 的元素大、又至少比 $30\%$ 的元素小。这样每次划分后，至少能甩掉 $30\%$ 的元素，递归规模保证缩小。

怎么找这样的基准？这就是"中位数的中位数"：

把 $n$ 个元素每 5 个一组，分成 $\lceil n/5\rceil$ 组。
找出每组（5 个元素）的中位数——5 个数找中位数用插入排序取中间那个即可， $O(1)$ 。
这样得到 $\lceil n/5\rceil$ 个中位数。递归地用选择算法找出这些中位数的中位数 $x$ （这是基准）。

$x$ 就是我们要的"不太偏"的基准。为什么？看图：

每组5个，取中位数(每组第3大)：
组1: [· · x₁ · ·]   组2: [· · x₂ · ·]  ...  共 ⌈n/5⌉ 组

$x$ 是这 $\lceil n/5\rceil$ 个中位数的中位数，所以至少有一半的中位数 $\ge x$ 。
每个中位数 $\ge x$ 的那组里，至少有 3 个元素（中位数本身及它右边两个） $\ge x$ 。
所以至少有 $3\cdot \lceil n/10\rceil \approx 0.3n$ 个元素 $\ge x$ 。对称地，约 $0.3n$ 个元素 $\le x$ 。

于是无论怎么划分，至少能甩掉 $30\%$ 的元素，递归规模最多是 $0.7n$ 。

3.复杂度： $T(n) \le T(n/5) + T(7n/10) + O(n) = O(n)$

写出递归关系。算法做了三件事：

每组找中位数、其他扫一遍： $\Theta(n)$ 。
递归找中位数的中位数：规模 $n/5$ ，代价 $T(n/5)$ 。
用 $x$ 划分后，递归处理较大的那一边：规模最多 $7n/10$ ，代价 $T(7n/10)$ 。

T(n) \le T(n/5) + T(7n/10) + \Theta(n)

关键： $1/5 + 7/10 = 9/10 < 1$ 。两个递归子问题的规模加起来只占 $90\%$ ，剩下的 $10\%$ 用来支付 $\Theta(n)$ 的工作。用递归树（4.1 节）或代入法可证：每层总代价是个等比递减级数 $n + 0.9n + 0.81n + \cdots = O(n)$ 。所以 $T(n)=O(n)$ 。

这就是最坏情况线性的来历。 $1/5+7/10<1$ 这个不等式是整个证明的命门——子问题规模的总占比严格小于 1，保证了代价收敛。

4.为什么 5：理论与实践的权衡

你可能会问：为什么每组分 5 个？分 3 个、分 7 个不行吗？

这是理论和实践的权衡。如果每组 $g$ 个，递归关系是 $T(n) \le T(n/g) + T(\text{较大那边的上界}) + O(n)$ 。要让总占比 $<1$ 保证线性， $g$ 不能太小：

$g=3$ ：中位数的中位数至少比约 $n/6$ 大、比约 $n/6$ 小，递归规模上界太大， $T(n)$ 可能退到 $O(n\log n)$ 。
$g=5$ ：刚好让 $1/5+7/10=0.9<1$ ，线性成立。这是能保证线性的最小分组大小，常数也还可控。
$g=7$ ：也线性，但常数更大、实现更繁琐，没有额外好处。

所以 5 是理论上的"甜蜜点"：最小且够用。这个数字背后是有道理的，不是随便选的。

5.这个算法的理论意义

这个算法最震撼的地方，不是它多实用（实际上随机化选择的期望 $O(n)$ 常数更小、工程上更爱用），而是它证明了一件事：选择问题本质上是线性的，比排序便宜。

排序有 $\Omega(n\log n)$ 的下界（1.8 节提过，4.9 节会证），所以排序再取第 $k$ 个是 $O(n\log n)$ 。但选择问题不需要全序信息，只需要"第 $k$ 个在哪"，所以它能做到 $O(n)$ 。这两个问题的难度差了一个 $\log n$ ，而线性选择算法把这个差距坐实了。 这种"精确刻画一个问题到底有多难"正是算法分析（第四卷）的追求。

它还是分治的范本：每次只递归一边（不像快排两边都走）、靠精心设计的基准保证子问题规模可控。第二卷结尾 2.7 会把这套"保证收缩比例"上升为分治设计的一般法则。

6.练习

Q1. 选择算法为什么能比排序（ $O(n\log n)$ ）更快地找到第 $k$ 小？

因为它不需要排好整个序。排序要确定所有元素的相对顺序，有 $\Omega(n\log n)$ 下界；而选择只要定位"第 $k$ 个在哪"，不需要全序信息。划基准归位后，只需判断 $k$ 在左还是右、只递归一边，省掉了另一边的全部工作。这种"只走一边"让它摆脱了排序的下界，做到 $O(n)$ 。

Q2. 为什么"中位数的中位数"能保证基准至少比 $30\%$ 的元素大？写出这个 $30\%$ 是怎么来的。

$x$ 是 $\lceil n/5\rceil$ 个组中位数的中位数，故至少一半组中位数 $\ge x$ 。每个这样的组里至少 3 个元素（中位数及右两个） $\ge x$ 。所以 $\ge x$ 的元素至少 $3\cdot\lceil n/10\rceil\approx 0.3n$ 个。对称地 $\le x$ 的也约 $0.3n$ 。于是划分后至少甩掉 $30\%$ ，递归规模 $\le 0.7n$ 。

Q3.（思考题） 线性选择的最坏 $O(n)$ 和随机化选择的期望 $O(n)$ ，工程上一般用哪个？为什么？

一般用随机化选择（期望 $O(n)$ ）。原因：中位数的中位数法虽然最坏线性，但常数大（要分组、递归找中位数的中位数），实现复杂；而随机化选基准期望也是 $O(n)$ 、常数小、实现简单，最坏虽然理论上是 $O(n^2)$ 但随机化后实际几乎不出现。和快排一样的道理——工程更看重期望性能和常数，而不是理论最坏界。

7.小结

线性时间选择算法用"中位数的中位数"挑出一个不太偏的基准，保证每次划分至少甩掉 $30\%$ 的元素，从而把选择问题做到最坏 $O(n)$ 。 $1/5+7/10<1$ 是线性成立的命门。它的理论意义在于坐实了"选择比排序便宜一整个 $\log n$ "。下一篇我们把分治带到几何世界——最近点对问题。