quickselect

随机化与分治的交汇

分治的递归式假定子问题的规模是切出来的定数。一旦切分点由数据决定，规模就成了随机变量，分治的骨架与复杂度里那套逐层求和不再直接可用。本页从求第 $k$ 小这个问题出发，看随机性如何进入分治，以及它进入之后落在哪里。

1 · quickselect 的期望线性

求一组数里第 $k$ 小的元素，排一遍序再取是 $\Theta(n \log n)$ 。quickselect 借用 quicksort 的 pivot 与 partition：选一个 pivot，把数组分成小于它和大于它的两段，pivot 自己落到最终位置 $p$ 。若 $p = k$ 就完事；否则目标必在某一侧，只需递归那一侧。另一侧连碰都不用碰。

省掉的这一半正是它与 quicksort 的全部区别：后者两半都要递归， $T(n) = 2T(n/2) + \Theta(n)$ ；前者只递归一半， $T(n) = T(n/2) + \Theta(n)$ 。后一条落在情形三上，答案 $\Theta(n)$ 。

但 $n/2$ 是理想切分，真实的 $p$ 由 pivot 挑得好不好决定。pivot 在区间内均匀随机时，落在中间一半（第 $n/4$ 到第 $3n/4$ 名之间）的概率是 $1/2$ ，此时无论目标在哪一侧，剩下的区间都不超过 $3n/4$ 。于是期望上有

T(n) \le T(3n/4) + \Theta(n)

展开成公比 $3/4$ 的等比级数，总和收敛到 $4n$ 以内。随机化并没有消灭最坏情形：每次都挑到最小或最大元素时，quickselect 退化成 $\Theta(n^2)$ 。它做的是把「坏输入」换成「坏运气」，而坏运气的概率随 $n$ 指数衰减。

图 1-1 · quickselect 的单步执行。可换种子重跑同一份数据，观察答案不变而比较次数变动，右侧的区间长度逐轮按常数比例收缩。

注 · quickselectCost 在 $n = 1000$ 、 $k$ 取中位位置、300 个种子下量到的每轮区间收缩比平均是 0.669，轮数均值 12.7、最多 22 轮。 $n = 1600$ 时 500 个种子的比较次数均值 5406.6，约 3.38 倍的 $n$ ，最大的一次 10778，约 6.74 倍。理论界 $4n$ 说的是期望，单次跑高出它并不矛盾。

建议 · $k$ 取在两端比取在中间便宜。 $n = 400$ 、500 个种子的实测： $k = 0$ 平均 1.99 倍的 $n$ ， $k = n-1$ 平均 1.98 倍，而 $k$ 取中位位置要 3.24 倍。原因在于目标靠边时，被丢掉的那一侧期望更长。求最小或最大值时用不着专门写一遍线性扫描，quickselect 的常数已经接近它。

2 · median-of-medians 买断最坏

要让最坏也线性，pivot 就不能靠运气，得保证按比例分割。BFPRT 的做法是先花线性时间造一个「够好」的 pivot：

把 $n$ 个元素五个一组切开，每组内部排序取出各自的 median，再对这 $\lceil n/5 \rceil$ 个 median 递归地求它们的 median，拿它当 pivot。

这个 pivot 好在哪里：设组数为 $g$ ，至少有 $\lceil g/2 \rceil$ 个组的 median 不大于它；每个这样的组里，除了 median 还有两个元素不大于它。扣掉不满五个的那一组与 pivot 自身所在的组，至少有 $3(\lceil g/2 \rceil - 2)$ 个元素不大于 pivot，约合 $3n/10$ 。另一侧同理。于是每轮至少丢掉三成，剩下的不超过 $7n/10$ 。

定理 2.1 记求 pivot 的递归为 $T(n/5)$ ，主递归为 $T(7n/10)$ ，分组排序与 partition 合计 $\Theta(n)$ ，则

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

两个系数之和 $1/5 + 7/10 = 9/10 < 1$ ，代入归纳假设 $T(m) \le cm$ 得 $T(n) \le \frac{9}{10}cn + \Theta(n)$ ，取 $c$ 足够大即有 $T(n) = O(n)$ 。

组长取 5 不是凑的。组长 3 时保证只有 $2(\lceil g/2 \rceil - 2) \approx n/3$ ，剩下 $2n/3$ ，而 $1/3 + 2/3 = 1$ ，归纳里的那个 $9/10$ 变成 1，递归不再收敛到线性。5 是让两项之和小于 1 的最小奇数。

图 2-1 · BFPRT 的单步执行。分组、取各组 median、递归求 median 的 median、按它分区，每轮给出实际丢掉的元素数与

3

倍的组数一半减二这条下界。

警示 · 买断最坏是要付钱的，而且比预期贵。bfprtCost 与 quickselectCost 用同一套比较计数口径（BFPRT 一侧计入组内插入排序的比较）， $n = 1600$ 、 $k$ 取中位位置时：BFPRT 用 12364 次比较，约 7.73 倍的 $n$ ；quickselect 500 个种子的均值只有 5406.6 次，约 3.38 倍。BFPRT 甚至超过了 quickselect 在这 500 次里最差的那一次（10778）。同一份实现在 $n = 100$ 、200、400、800 上分别是 6.09、3.54、7.08、7.56 倍的 $n$ ，并不随 $n$ 平滑，因为每轮 pivot 的落点与 $k$ 的相对位置决定了还要不要再递归一层。

工程上真正在用的是两者的混合：Introselect 先跑 quickselect，递归深度超过阈值才切到 BFPRT。这样常见情形吃随机化的小常数，病态输入吃确定性的保证。

3 · Las Vegas 与 Monte Carlo

随机化算法按「随机性落在哪里」分成两族。

定义 3.1（Las Vegas 与 Monte Carlo） Las Vegas 算法的输出恒为正确答案，运行时间是随机变量。Monte Carlo 算法的运行时间有确定上界，输出以某个可控的概率出错。

quickselect 属前者：换种子只换执行路径，第 $k$ 小就是第 $k$ 小。lasVegasTrials 在 40 个种子上跑同一份数据，返回值全同，比较次数各不相同。

后者拿 Rabin-Karp 作例子最清楚。它给每个长度为 $m$ 的窗口算一个 rolling hash，与 pattern 的哈希相等就算命中。若就此上报，时间是死的（窗口数 $n - m + 1$ ，与文本内容无关），而两个不同的串哈希相同就成了一次误报。模数越大误报越少，代价是模数受机器字长限制。

monteCarloTrials 在长 60 的随机文本、长 4 的 pattern 上各跑 1000 次试验，窗口数恒为 57：

模数	至少出现一次误报的试验	误报总处数
11	993 / 1000	5111
31	797 / 1000	1533
101	375 / 1000	470
1009	0 / 1000	0

图 3-1 · 两族算法的试验台。左栏逐次跑 quickselect（答案恒定、代价波动），右栏逐次跑不做确认的 Rabin-Karp（代价恒定、答案可能出错），可调模数观察误报率随之变化。

两族之间可以互转，而且转换的方向决定了拿到什么。给 Monte Carlo 加一道验证就得到 Las Vegas：Rabin-Karp 在哈希命中后逐字符确认一遍，答案就再也不会错，但时间随碰撞次数波动。反过来，给 Las Vegas 设一个步数上限、超时就返回当前最好的结果，就得到 Monte Carlo。

注 · 本站的 Rabin-Karp 一页实现的是带确认的版本，按上面的定义那一版严格说属于 Las Vegas 而非 Monte Carlo，尽管这个算法在文献里通常被归进 Monte Carlo 那一栏。本页的 rabinKarpNoVerify 是专为对照写的，把确认那一步拿掉了，别拿它当可用的匹配实现。

4 · 参考文献

Hoare, C. A. R. (1961). Algorithm 65: Find. Communications of the ACM, 4(7), 321–322.
Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., & Tarjan, R. E. (1973). Time bounds for selection. Journal of Computer and System Sciences, 7(4), 448–461.
Karp, R. M., & Rabin, M. O. (1987). Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2), 249–260.
Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.