CLRS 7.3 随机化快速排序深度解析:期望运行时间的动机与 RANDOM 调用次数的 Θ 分析

原创2026-10-12 13:49:571,351 阅读
文章标签:文档教程

CLRS 7.3 随机化快速排序深度解析:期望运行时间的动机与 RANDOM 调用次数的 Θ 分析

导读:本文以 CLRS 解题仓库的 7.3 小节解答 为核心骨架,完整继承并深入展开《算法导论(第三版)》第 7.3 节"快速排序的随机化版本"的两道习题:其一回答"为什么随机化算法要分析期望运行时间而非最坏情况运行时间",其二用递推式定量求解 RANDOMIZED-QUICKSORT 对随机数生成器 RANDOM 的调用次数。在此基础上,文章进一步串联第 7 章的 7.1、7.2、7.4 与 Problems 7-2、7-3、7-5 解答,把"随机化 → 期望分析 → Θ(n lg n)"这条主线讲透。

1. 背景:确定性快速排序的软肋

在进入随机化版本之前,先明确它要解决的问题。第 7.1 节的 PARTITION 过程以子数组末尾元素 A<a href="https://link.gitcode.com/i/014da2f22a9b8f47c8c5f915a182a245" target="_blank">r] 为主元,一趟扫描把数组分成"小于等于主元"与"大于主元"两部分,其运行时间对规模为 nn 的子数组是 Θ(n)\Theta(n)(见 [7.1-3 解答 之前的 7.1.md)。

问题出在第 7.2 节指出的最坏情况:当输入恰好是已排序(升序或降序)数组、或所有元素相同时,每次 PARTITION 都产出一个空分区和一个规模 n−1n-1 的分区,递推式

T(n)=T(n−1)+Θ(n)T(n) = T(n-1) + \Theta(n)

的解是 Θ(n2)\Theta(n^2)(7.2-1、7.2-2、7.2-3 解答)。也就是说,一个对绝大多数输入都很快的算法,会被少量"坏输入"直接拖垮——而且这类坏输入在现实数据(如按时间戳记录的银行流水、几乎有序的集合)中并不罕见。

随机化版本的思路由此而来:不让"输入"决定主元,而让"随机数生成器"决定主元。

2. 随机化机制:RANDOMIZED-PARTITION 与 RANDOMIZED-QUICKSORT

教材 7.3 节的标准做法是:在 PARTITION 之前先用 RANDOM(p, r) 从区间 [p,r][p, r] 中均匀随机地选出一个下标,把该位置元素与 A[r] 交换,再执行原有的 PARTITION 过程。即:

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange A[r] with A[i]
    return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r)
    if p < r
        q = RANDOMIZED-PARTITION(A, p, r)
        RANDOMIZED-QUICKSORT(A, p, q - 1)
        RANDOMIZED-QUICKSORT(A, q + 1, r)

这一结构的正确性在仓库中可以从两个方向得到印证:

  • 问题 7-1(Hoare 划分) 讨论了与教材 PARTITION 不同的原始划分算法,其 HOARE-QUICKSORT 递归调用 HOARE-PARTITION(A, p, q) 与 HOARE-PARTITION(A, q + 1, r),展示了主元处理方式变化时递归骨架的对应调整;
  • 问题 7-2(相等元素) 直接以 RANDOMIZED-QUICKSORT 为讨论对象,给出调用 RANDOMIZED-PARTITION' 的 QUICKSORT' 伪代码,并指出当元素全相等时 RANDOMIZED-QUICKSORT 恒返回 q=rq = r,递推式 T(n)=T(n−1)+Θ(n)=Θ(n2)T(n) = T(n-1) + \Theta(n) = \Theta(n^2)。

随机化之后,主元在 nn 个元素中等概率选取,最坏情况不再由特定输入唯一决定——这正是下一节习题 7.3-1 的论述起点。

3. 习题 7.3-1:为什么分析期望运行时间,而非最坏情况运行时间

题目:为什么我们要分析随机化算法的期望运行时间,而不分析它的最坏情况运行时间?

仓库解答(7.3.md 第 3-5 行):

We analyze the expected run time because it represents the more typical time cost. Also, we are doing the expected run time over the possible randomness used during computation because it can't be produced adversarially, unlike when doing expected run time over all possible inputs to the algorithm.

这段话包含两个递进的层次:

  1. 期望运行时间刻画"典型代价"。确定性算法的运行时间完全由输入决定,而随机化算法的运行时间还取决于算法内部的随机选择。对随机化算法取期望时,我们在"随机选择"这一维度上做平均,得到的是该算法在任意固定输入下、反复运行多次的典型时间成本,它比单个最坏情况更能反映实际使用体验。

  2. 关键差异:随机性无法被输入"对抗性构造"。如果对"所有可能输入"取期望(即平均情况分析),输入分布往往是假设的,攻击者或特殊数据可以刻意逼近最坏输入,让分析失效;但随机化算法的期望是针对算法内部抛硬币的结果取平均——输入可以任意选择,却无法预先知道并利用随机的落点。正如解答所说,这种期望"can't be produced adversarially"(不能被对抗性地制造出来)。于是,随机化把"与输入博弈"转化为"与概率博弈":无论输入多么糟糕,只要坏随机序列(坏分割)的概率足够小,算法总体就是高效的。

这个"小概率坏事件"的量化观,正是 7.2 节两道星号习题的用武之地:

  • 7.2-5:若每一层分割比例恒为 1−α1-\alpha 对 α\alpha(0<α≤1/20<\alpha\le 1/2),递归树叶子最小深度约为 −lg⁡n/lg⁡α-\lg n/\lg\alpha,最大深度约为 −lg⁡n/lg⁡(1−α)-\lg n/\lg(1-\alpha)——分割越失衡,递归越深;
  • 7.2-6:随机主元下,得到比 1−α1-\alpha 对 α\alpha 更平衡分割的概率约为 1−2α1-2\alpha(主元落入最小 αn\alpha n 个或最大 αn\alpha n 个元素的概率各约 α\alpha,合计 2α2\alpha)。

两题合起来说明:随机主元既大概率给出足够平衡的分割(如取 α=1/3\alpha = 1/3,平衡概率约 1/31/3),又把失衡情况限制为小概率事件,期望代价因此可控。

4. 习题 7.3-2:RANDOM 调用次数的最坏与最好情况

题目:当 RANDOMIZED-QUICKSORT 运行时,最坏情况下对随机数生成器 RANDOM 调用多少次?最好情况呢?请用 Θ 记号作答。

仓库解答(7.3.md 第 9-19 行):

最坏情况。 每次 RANDOMIZED-PARTITION 恰调用一次 RANDOM,而每次递归调用又对应一次新的 RANDOM 调用。最坏情况(每次分割产生一个规模 n−1n-1 的子问题和一个空子问题)下:

T(n)=T(n−1)+1=n=Θ(n).T(n) = T(n-1) + 1 = n = \Theta(n).

最好情况。 每次分割恰好对半分,两个子问题规模各为 n/2n/2:

T(n)=2T(n/2)+1=Θ(n).T(n) = 2T(n/2) + 1 = \Theta(n).

(对后者用主定理情形 1:f(n)=1=O(nlg⁡2−ϵ)f(n) = 1 = O(n^{\lg 2 - \epsilon}),故 T(n)=Θ(nlg⁡2)=Θ(n)T(n) = \Theta(n^{\lg 2}) = \Theta(n)。)

解答的直观注记:原文补充道,这并不令人意外,因为"每个(至少)第三个元素都会被选为主元"。这句话的含义可以从期望层面理解:主元在元素序列中等概率随机选取,任何元素都不会被系统性跳过,递归树节点数(即 RANDOM 调用次数)在两个极端情形下都只有线性规模。

需要强调的结论是:RANDOM 调用次数与快速排序本身的运行时间不在一个数量级上。一次 RANDOM(p, r) 的开销是常数或对数级的,即使最坏情况也仅 Θ(n)\Theta(n) 次调用;真正主导总运行时间的是每一层分割付出的 Θ(n)\Theta(n) 工作,以及随之而来的递归树深度。因此,7.3 节的期望分析把注意力放在"期望的分割质量"上,而不是随机数生成的开销上——这一点与 7.4 节的分析 一脉相承。

5. 期望运行时间 Θ(n lg n):7.4 分析与问题 7-3 的两条证明路线

随机化之后,核心定理是:RANDOMIZED-QUICKSORT 在任意输入上的期望运行时间为 Θ(nlg⁡n)\Theta(n\lg n)。仓库给出了两条完整的证明路线。

路线一:7.4 节的比较次数期望分析。 用指示随机变量刻画"元素 ziz_i 与 zjz_j 是否被比较",利用线性期望可得

E[X]=∑i=1n−1∑j=i+1n2j−i+1=Θ(nlg⁡n).\text E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1} = \Theta(n\lg n).

其中 7.4-4 解答 用不等式放缩给出下界:

E[X]≥∑i=1n−1∑k=1n−i22k=Ω(nlg⁡n),\text E[X] \ge \sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{2k} = \Omega(n\lg n),

从而期望比较次数(进而期望运行时间)为 Θ(nlg⁡n)\Theta(n\lg n)。

路线二:问题 7-3 的逐次调用分析。 它不从"比较次数"而从"每次递归调用的期望时间"入手:

  • (a) 任一特定元素被选为主元的概率为 1/n1/n,定义 Xi=I{第 i 小元素被选为主元}X_i = I\{\text{第 } i \text{ 小元素被选为主元}\},则 E[Xi]=1/n\text E[X_i] = 1/n;
  • (b) 由线性期望得 E[T(n)]=E[∑q=1nXq(T(q−1)+T(n−q)+Θ(n))]\text E[T(n)] = \text E\left[\sum_{q=1}^{n}X_q(T(q-1)+T(n-q)+\Theta(n))\right](式 7.5);
  • (c) 化简为 E[T(n)]=2n∑q=2n−1E[T(q)]+Θ(n)\text E[T(n)] = \frac{2}{n}\sum_{q=2}^{n-1}\text E[T(q)] + \Theta(n)(式 7.6);
  • (d) 用积分近似证明 ∑k=2n−1klg⁡k≤12n2lg⁡n−18n2\sum_{k=2}^{n-1}k\lg k \le \frac{1}{2}n^2\lg n - \frac{1}{8}n^2(式 7.7);
  • (e) 代入归纳假设 E[T(q)]≤qlg⁡q+Θ(n)\text E[T(q)] \le q\lg q + \Theta(n),最终得到 E[T(n)]=Θ(nlg⁡n)\text E[T(n)] = \Theta(n\lg n)。

两条路线互为印证:前者直接对比较次数求期望,后者对运行时间本身建立递推并求解,殊途同归地支撑了 7.3 节的结论——随机化让快速排序在任意输入上都有 Θ(nlg⁡n)\Theta(n\lg n) 的期望性能。

6. 延伸:随机化主元的两种实用改进

理解了期望分析的机制,再看第 7 章末尾两个随机化变体就水到渠成:

变体一:相等元素场景(问题 7-2)。 若数组含大量重复值,标准 RANDOMIZED-QUICKSORT 仍可能退化到 Θ(n2)\Theta(n^2)(元素全相等时 q=rq = r)。解答给出的 PARTITION' 返回两个下标 (low, high),把与主元相等的元素集中到 A[q..t]A[q..t] 中间带,QUICKSORT' 只递归两侧严格小于/大于主元的区间。由于不再递归相等元素,"子问题规模不会超过全异元素情形",7.4.2 的分析得以免除"元素互异"假设。

变体二:median-of-3 主元(问题 7-5)。 随机取 3 个元素,以其中位数为主元。解答推导出第 ii 小元素被选中的概率

pi=6(n−i)(i−1)n(n−1)(n−2),i=2,3,…,n−1,p_i = \frac{6(n-i)(i-1)}{n(n-1)(n-2)},\quad i = 2,3,\ldots,n-1,

当 n→∞n\to\infty 时选中真正中位数的概率比普通实现提升 32\frac{3}{2} 倍;"好分割"(n/3≤i≤2n/3n/3 \le i \le 2n/3)的概率则由 13\frac{1}{3} 提升到 1327\frac{13}{27}。这正是 7.4-6 所述"三点取中"思想的精确化——随机化不改变 Θ(nlg⁡n)\Theta(n\lg n) 的数量级,只优化常数因子。

7. 在仓库中的位置与进一步阅读

本仓库(CLRS Solutions)以 Markdown + KaTeX 组织《算法导论(第三版)》全书习题解答,站点导航定义见 mkdocs.yml,其中 7.3 一节位于"II Sorting and Order Statistics → 7 Quicksort"下。相关资源按阅读顺序推荐:

沿这条主线读下来,"为什么随机化"与"随机化后如何分析"两个问题会形成一个完整的闭环:期望分析针对的是算法内部的随机性,它无法被输入对抗性构造,因此随机化快速排序能够在任意输入上获得 Θ(nlg⁡n)\Theta(n\lg n) 的期望保证,而 RANDOM 调用本身仅为 Θ(n)\Theta(n) 次线性开销——这就是第 7.3 节全部习题要传达的核心。

登录后查看全文
CLRS