第4卷第10章随机算法

从普通快速排序的两只翅膀、最坏与平均递推走向随机快速排序；用调和数、期望线性法则和指示器随机变量证明任意输入上的期望比较次数为Θ(n log n)，并在双仓图书馆完成关于数学传递的报告。

学习目标

能用循环不变量解释快速排序的划分过程，写出左右子数列和递归基本情况
能推导固定枢纽的最坏/输入平均递推，并区分 Θ(n²) 与 Θ(n log n) 各自依赖的概率空间
能用指示器随机变量和期望的线性法则证明随机快速排序的期望比较次数为 2(n+1)H_n-4n
能切换枢纽策略、检查比较过程，并回答“输入平均与算法随机为什么不是一回事”

从“排整齐”开始：主动掷骰子的路线图

排序追求秩序，随机选择看起来制造混乱。第10章要解释的反差正是：把一个局部选择随机化，反而能让对任意输入保持稳定的期望表现。

先预测，再带着五个问题进入原章：

为什么固定选择最左元素作枢纽，会让已经排好序的输入触发最坏情况？
“普通快排平均为n log n”究竟平均了什么，隐藏了什么前提？
为什么随机快排只增加两行，却能把结论改成“对任意输入成立”？
不解递推公式，如何只观察任意两元素是否比较，就算出总比较次数？
数学报告中，示例、前提、定量评估和可复查推导为什么与公式同样重要？

10.1 休闲餐厅

雨夜与过量的讲稿

两周后，泰朵拉要在双仓图书馆面向初高中生作算法报告。她把想讲的内容塞满整本笔记，担心删掉任何一步都会让听众迷路；但报告时间和准备时间都有限。

理纱用很少的话指出问题：内容多不等于传达得好。三人最终把排序例子压缩为两个：冒泡排序负责建立直观，负责把分析推向本章主线。

这段开场先提出一个教学约束：讲解必须在完整与可理解之间取舍。后面泰朵拉的报告会用示例承担直观、用讲义承载推导、用关键句固定主线。

10.2 学校

10.2.1 中午

两天后的午休，“我”向米尔嘉谈起泰朵拉的准备。理纱嘴上严厉，实际已经答应帮助制作报告材料。米尔嘉原本计划去国外参加数论研讨会，返程恰好比双仓会议晚一天，这为报告现场的变化埋下伏笔。

10.2.2 快速排序算法

放学后的图书室里，泰朵拉与理纱从输入输出开始讲解。给定数列A和闭区间[L,R]，算法只排序A[L]至A[R]，范围外元素保持不变；排序全体时取L=1、R=n。原章分析还假定元素互不相同，以免相等元素干扰秩的讨论。

普通快排选择最左元素A[L]作为：

procedure QUICKSORT(A, L, R)
  if L < R then
    p ← L
    k ← L + 1
    while k ≤ R do
      if A[k] < A[L] then
        swap A[p + 1], A[k]
        p ← p + 1
      end if
      k ← k + 1
    end while
    swap A[L], A[p]
    QUICKSORT(A, L, p - 1)
    QUICKSORT(A, p + 1, R)
  end if
  return A
end procedure

例如输入5,1,7,2,6,4,8,3。以5为枢纽完成第一次划分后，小于5的3,1,2,4在左侧，大于5的7,8,6在右侧，5位于两组之间。随后同样处理左右子数列。

快速排序由两种动作反复构成：

通过枢纽项划分数列：扫描并建立小于区、非小于区；
对子数列排序：在左右两边递归调用同一个过程。

10.2.3 通过枢纽项划分数列：两只翅膀

p 维护小于枢纽区，k 扫描未确认区；一次划分只负责分组，不负责把两翼完全排好。

变量p与k不是临时下标，而是一个的边界。在每次比较A[k]之前，区间被分成：

\begin{array}{c|c|c|c} A[L] & A[L+1..p] & A[p+1..k-1] & A[k..R]\\ \hline \text{枢纽} & \text{小于枢纽} & \text{大于等于枢纽} & \text{未确认} \end{array}

若A[k]小于枢纽，就把它交换到p+1，再同时推进p；否则只推进k。因此每轮恰好消化一个未确认元素，又不会破坏前面两个已分类区域。

当k越过R，未确认区为空。交换A[L]与A[p]后：

A[L..p-1]\lt A[p]\le A[p+1..R].

泰朵拉把两边称为：

-；-。

枢纽项若落在端点，其中一只翅膀大小为0。算法仍正确，但递归树会极不平衡。

10.2.4 对子数列排序：递归

左翼范围是[L,p-1]，大小为p-L；右翼范围是[p+1,R]，大小为R-p。用过程自身处理更小输入，就是：

\operatorname{QUICKSORT}(A,L,p-1),\qquad \operatorname{QUICKSORT}(A,p+1,R).

大小为0或1的子数列满足L≥R，不进入划分，直接返回。这个基本情况既保证停止，也提供递推公式的初值。

这就是递归：划分负责“分”，递归负责“治”，枢纽已到最终位置使两边答案可以直接合成。

10.2.5 运行步数的分析

泰朵拉与理纱逐行计数。若L≥R，只有过程入口、条件、返回和过程结束，共4步：

T_Q(0)=T_Q(1)=4.

若L<R，设行内交换执行W次，左右递归运行步数为T_{\mathrm{left}}与T_{\mathrm{right}}。把各行次数相加：

T_Q(R-L+1) =9+4R-4L+3W+T_{\mathrm{left}}+T_{\mathrm{right}}.

这里W、左右子问题大小都由输入决定。这不是推导失败，而是暴露了算法代价真正依赖的结构：枢纽项最后落在哪里。

10.2.6 分情况讨论

令：

n=R-L+1,\qquad j=p-L+1.

于是枢纽项是当前子数列中第j小的元素，左翼大小为j-1，右翼大小为n-j。因为每个非枢纽元素至多触发一次交换：

0\le W\le n-1.

这也可写成0≤W≤n-1。为了得到保守上界，原章把W取为n-1，得到“作为线索的缎带”：

T_Q(n) \le 7n+2+T_Q(j-1)+T_Q(n-j), \qquad 1\le j\le n.

这里的范围是1≤j≤n。这个式子仍含j，因为同样大小的输入可以产生不同的枢纽秩。分析必须明确选择：研究最大值、研究平均值，还是算法内部随机选择后的期望值。

10.2.7 最大运行步数

若每次枢纽都落在端点，两个子问题大小是0和n-1。记最大运行步数为M(n)：

M(n)\le 7n+2+M(0)+M(n-1).

用M(0)=4吸收常数并展开：

\begin{aligned} M(n) &\le M(1)+\sum_{r=2}^{n}(7r+6)\\ &=M(1)+7\left(\frac{n(n+1)}{2}-1\right)+6(n-1)\\ &=\Theta(n^2). \end{aligned}

固定选择最左元素时，已经升序的数列每次都让最小元素成为枢纽；已经降序的数列也会不断产生端点划分。因此“输入已经很整齐”反而可能触发最坏递归树。

同一个分区过程，枢纽秩的分布决定递归树；随机化把输入顺序的攻击性变成可分析的期望。

10.2.8 平均运行步数

为了汇总枢纽秩的n种情况，原章转向。先假设输入是1,2,...,n的全部n!种排列，并且每种排列出现概率相同。于是最左元素的秩j在1至n上均匀分布。

记平均运行步数为A(n)。对全部枢纽秩取平均：

\begin{aligned} A(n) &=7n+2+\frac1n\sum_{j=1}^{n} \left(A(j-1)+A(n-j)\right)\\ &=7n+2+\frac2n\sum_{i=0}^{n-1}A(i), \qquad n\ge2. \end{aligned}

其中A(0)=A(1)=4。乘以n：

nA(n)=7n^2+2n+2\sum_{i=0}^{n-1}A(i).

把n替换为n+1，再用相邻两式相减消去求和：

(n+1)A(n+1)=(n+2)A(n)+14n+9.

等价地：

A(n+1) =\frac{n+2}{n+1}A(n)+14-\frac5{n+1}.

原章在这里把“差分法”留成问题10-1，并在下一节继续求解。

10.2.9 回家路上

泰朵拉打算在报告中分享的不只是冒泡排序、快速排序和公式，而是“亲自分析问题的快乐”。理纱一直安静地支持她。米尔嘉则按原计划不在日本，似乎无法参加会议。

10.3 自己家

10.3.1 变形

周六，“我”与尤里继续解问题10-1。递推中A(n)前面带着随n变化的系数，先定义：

F(n)=\frac{A(n)}{n+1}.

把相邻递推除以(n+1)(n+2)：

F(n+1) =F(n)+\frac{14n+9}{(n+1)(n+2)}.

部分分式分解要求：

\frac{14n+9}{(n+1)(n+2)} =\frac{a}{n+1}+\frac{b}{n+2}.

比较系数得到：

a+b=14,\qquad 2a+b=9,

所以a=-5、b=19，即：

F(n+1)=F(n)-\frac5{n+1}+\frac{19}{n+2}.

为了看清累加结构，还可改写为：

F(n+1) =F(n)+\frac{14}{n+1} +19\left(\frac1{n+2}-\frac1{n+1}\right).

第二部分会望远镜式消去，第一部分留下：

H_n=\sum_{r=1}^{n}\frac1r.

由A(2)=24可得F(2)=8。从2展开到n，得到精确式：

F(n)=14H_n+\frac{19}{n+1}-\frac{58}{3}.

因此：

\boxed{ A(n)=14(n+1)H_n+19-\frac{58}{3}(n+1) } \qquad(n\ge2).

10.3.2 Hₙ与log n

为什么调和数与对数同阶？函数1/x单调下降，用单位宽矩形和曲线下面积比较：

\int_1^{n}\frac{dx}{x} \le H_n \le 1+\int_1^{n}\frac{dx}{x}.

所以：

\log n\le H_n\le 1+\log n,

也就是：

H_n=\Theta(\log n).

也就是H_n=Θ(log n)。代回精确式：

A(n)=\Theta(n\log n).

也就是A(n)=Θ(n log n)。尤里追问“评估平均运行步数有没有前提条件”。“我”一时认为平均本身已经足够，但这个回答忽略了最重要的一层：平均必须相对于某个概率分布。

10.4 图书室

10.4.1 米尔嘉：被遗漏的大前提

周一，米尔嘉直接指出普通快排平均分析的前提：

输入的n!种排列服从均匀分布。

正因为每种排列等概率，枢纽秩才会在1至n上均匀，前面的平均递推才成立。若真实输入经常已经排序，固定最左枢纽的运行步数就接近平方阶。

这里要区分两个对象：

-：随机性来自输入模型；-：随机性来自算法自身。

同一个n log n形式可以来自不同概率空间，结论的适用范围因此完全不同。

10.4.2 随机快速排序

只需在划分前增加两步：

procedure RANDOMIZED-QUICKSORT(A, L, R)
  if L < R then
    r ← RANDOM(L, R)
    swap A[L], A[r]
    # 以下划分与普通QUICKSORT相同
    partition around A[L]
    RANDOMIZED-QUICKSORT(A, L, p - 1)
    RANDOMIZED-QUICKSORT(A, p + 1, R)
  end if
  return A
end procedure

无论输入顺序如何，随机选择都会让枢纽秩j在1至n上均匀。因此对每一个固定输入，期望递推仍是：

\mathbb E[T(n)] =7n+2+\frac2n\sum_{i=0}^{n-1}\mathbb E[T(i)].

结论变为：

普通快排：对均匀分布的输入，平均运行步数为Θ(n log n)；
随机快排：对任意固定输入，算法运行步数的期望为Θ(n log n)。

随机枢纽没有消除最坏运行轨迹。它让连续选中极端枢纽成为低概率事件，从而把输入对固定规则的攻击能力转化为算法内部可分析的随机变量。排序结果始终正确，随机的只是运行时间，所以它属于。

10.4.3 观察比较过程

米尔嘉换了一个分析视角：不再逐层解递推，而是问随机快排排序1,2,...,n时，固定元素j与k何时比较，其中1≤j<k≤n。

一次划分只比较“枢纽项与当前子数列中的其他元素”。枢纽就位后不再进入任何子问题，因此：

任意一对元素至多比较一次；
左右翅膀之间再也不会发生比较；
j与k是否比较，只取决于集合{j,j+1,...,k}里谁最先成为枢纽。

若中间某个p满足j<p<k并先成为枢纽，j和k立刻被分到两只翅膀，以后不会相遇。只有j或k先成为枢纽时，二者才会直接比较。

换言之：

j\text{与}k\text{比较} \iff \{j,j+1,\ldots,k\}\text{中最先成为枢纽的是}j\text{或}k.

10.4.4 期望的线性法则

定义：

X_{j,k}= \begin{cases} 1,&j\text{与}k\text{被比较},\\ 0,&j\text{与}k\text{未比较}. \end{cases}

总比较次数X就是所有元素对指示器之和：

X=\sum_{1\le j<k\le n}X_{j,k}.

简记为X=ΣXj,k。根据：

\mathbb E[X] =\sum_{1\le j<k\le n}\mathbb E[X_{j,k}].

这一步不要求不同元素对的比较事件独立。线性法则恰好让我们绕过复杂依赖。

10.4.5 指示器随机变量的期望等于概率

对任意指示器I：

\mathbb E[I] =0\cdot\Pr(I=0)+1\cdot\Pr(I=1) =\Pr(I=1).

区间{j,j+1,...,k}有k-j+1个元素，随机枢纽顺序中每个元素同样可能最先出现，有利端点是j和k两个。因此：

\mathbb E[X_{j,k}] =\Pr(X_{j,k}=1) =\frac{2}{k-j+1}.

代回总和：

\begin{aligned} \mathbb E[X] &=\sum_{j=1}^{n-1}\sum_{k=j+1}^{n} \frac2{k-j+1}\\ &=2\sum_{j=1}^{n-1} \sum_{m=2}^{n-j+1}\frac1m\\ &=2\sum_{j=1}^{n-1}(H_{n-j+1}-1). \end{aligned}

使用调和数恒等式：

\sum_{\ell=1}^{n}H_\ell=(n+1)H_n-n,

可得精确期望：

\boxed{ \mathbb E[X]=2(n+1)H_n-4n }.

于是：

\mathbb E[X]=\Theta(n\log n).

这个证明比运行步数递推更聚焦：先找出一次比较发生的充要条件，再用指示器完成计数。

把每一对比较编码成0/1变量，就能用期望的线性法则绕过比较事件之间的复杂依赖。

10.5 休闲餐厅

10.5.1 各种各样的随机算法

米尔嘉把本卷出现的随机算法按目的归纳：

随机抽样：研究对象太大时，用少量样本估计整体，像把汤搅匀后尝味道；
回避最坏情况：随机快排不让固定输入稳定诱发坏枢纽；
积累概率证据：概率质数测试可输出“一定是合数”或“可能为质数”，并定量给出误判上界；
在困难搜索中探索：上一章的RANDOM-WALK-3-SAT用局部随机漫步寻找可验证答案。

把不确定性放在正确性上；Las Vegas算法把不确定性放在运行时间上。两类都必须说明概率空间、失败含义和重复策略。

原章强调：概率结果不是含糊地说“也许会错”，而是报告失败概率至多多少、追加验证需要多少成本。

输入平均与算法随机不是一回事；写清概率空间，才能知道期望结论对谁成立。

10.5.2 准备

泰朵拉想把随机快排也加入报告，时间却不能增加。理纱建议把来不及现场推导的内容写入讲义，像给听众写信。报告从“把全部内容说完”转向“让听众能沿关键线索继续理解”。

会议房间从想象中的小教室变成名为Iodine的会场，听众也比预期更多。泰朵拉的紧张由此升级。

10.6 双仓图书馆

10.6.1 Iodine

会议早晨下着小雨。“我”、泰朵拉、尤里与理纱进入双仓图书馆。会场名Iodine意为碘，元素符号是I。众人还认出图书管理员瑞谷先生是瑞谷女史的弟弟。

泰朵拉把报告内容全部写在稿纸上，但沉默和反复检查暴露了她的紧张。米尔嘉按计划仍应在国外。

10.6.2 紧张

面向初高中生的研讨会远比泰朵拉预计正式。轮到她上台时，稿纸散落、会场嘈杂，她站在讲台上发不出声音。

就在局面失控时，提前一天回国的米尔嘉出现。理纱接管屏幕，让大屏幕显示“请安静”，再用沙哑的声音喊出：

Continue！

这个词不替泰朵拉完成报告，只帮她重新获得下一步。

10.6.3 报告

泰朵拉恢复节奏后，没有堆叠公式，而是用具体示例演示划分与比较。她反复使用贯穿全书的方法句：

示例是理解的试金石；
从理所当然的地方开始思考；
通过导入变量进行一般化；
做明确前提条件的定量评估；
比较不会横跨左右翅膀；
和的期望等于期望的和；
指示器随机变量的期望等于概率；
指示器随机变量是用于计数的工具。

这些句子把长推导压缩成可迁移的方法。听众不仅看到结论，也看到结论如何被发现和检查。

10.6.4 传达

报告最后，泰朵拉不再谈算法细节，而是谈学习数学：面对不明白、复杂、模棱两可的事物，提出问题并动手解决，本身就会带来惊奇。

排序把错乱元素整理有序，却通过随机选择获得稳定表现，这种反差正是她想传递的惊讶。她感谢数学家、老师、伙伴与听众，并借用“我”常说的话结束：

数学，能够穿越时空。

知识不会因研究者离开而消失。定义、证明、论文、教育和对话让后来者接过问题。报告最后，全场一起做斐波那契手势，泰朵拉在掌声中完成了从学习者到讲述者的一步。

10.6.5 Oxygen

午餐地点是三层咖啡餐厅Oxygen，即氧。来自不同国家的学生拿着讲义和泰朵拉交流，数学不仅穿越时间，也跨越国境。

米尔嘉在这里精确区分两个英文术语：

probabilistic analysis of algorithms：在假设输入服从某种概率分布后分析确定性算法；
analysis of randomized algorithms：不假设输入分布，分析算法内部随机选择产生的期望。

普通快排的均匀排列平均属于前者，随机快排对任意输入的期望属于后者。

10.6.6 连接

Iodine的元素符号I与Oxygen的元素符号O形成输入输出般的连接。泰朵拉认为，超越个人生命传递思想，不只依靠论文，也依靠教育：一个人教给另一个人，另一个人继续传下去。

尤里担心语言能否连接远方的人，恰好在餐厅遇见一直通信的男生。抽象的“连接”在现实中得到回应。

10.6.7 庭园

雨停后，“我”与提前回来的米尔嘉走进庭园。两人的对话从支持、约定走向无需电话与书信的近距离表达。原章没有用算法语言解释这一幕，但它延续同一主题：表达不是单向输出，而是人与人之间真实建立联系。

10.6.8 约定的印记

泰朵拉来提醒下午研讨会即将开始。雨后蓝天出现彩虹，被称为“约定的印记”。梅雨季将尽，炎热夏天将至；数学报告完成了，本卷人物的关系也走到新的起点。

尾声

多年后的教师办公室里，一位少女提出两个关于随机性的题。

第一题是“售卖点B比售卖点A更容易中奖”的传言。若B卖出的彩票更多，那么“B出现一张中奖彩票”的概率确实更大，但每张彩票的中奖概率没有变化。这里混淆了：

\Pr(\text{某售卖点至少出现一张中奖彩票})

与：

\Pr(\text{某一张彩票中奖}).

传言还可能形成反馈：更多人相信B，更集中地在B购买，B出现中奖彩票的概率继续增加，但个人手中每张票的机制仍未改变。

第二题是：

被改动过一个数的随机数表，还能称作随机数表吗？

若回答“改一个仍随机”，反复应用同一理由似乎会推出“改任意多个仍随机”，最终任何数表都能被叫作随机数表。这说明“随机或不随机”的二选一表述可能过于粗糙。更好的问题是：

这个数表在给定检验、模型和尺度下，随机程度怎样？

随机性不是只凭外观作出的标签。必须说明生成机制、待检验性质与评价尺度；分析随机算法还要定义失败概率。少女进一步追问人生是否存在通过后便一路顺利的“真正测试”。教师没有给出公式答案，只能说明学习、提问和对话本身如何连接现在与更长的时间。

雨停后，少女离开办公室；窗外再次出现约定的彩虹。全卷从赌博直觉、线性搜索、指数爆炸、概率公理、期望、渐近阶、矩阵、随机漫步、随机3-SAT，最终落到随机快排与“如何评价随机”：

\text{随机不是放弃分析，而是把不确定性纳入分析。}

概念证据索引：把缺失锚点放回推导

本节把 manifest 中容易被伪代码、递推和叙事掩盖的锚点逐一说明。它们不是额外背诵清单，而是检查“算法对象、概率空间、证明工具和传达场景”有没有接上。

完整与可理解：算法报告必须在完整推导和听众可跟随之间做取舍。
数列A：A 是快速排序接收的输入数列，[L,R] 只指定当前子区间。
变量p / 变量k：p 管理小于枢纽区，k 扫描未确认区。
比较A[k] / 交换到p+1：比较当前项后，若小于枢纽，就交换到 p+1 并扩大左区。
交换A[L]与A[p]：扫描结束时把枢纽从左端交换到它的最终排序位置。
左边的翅膀 / 右边的翅膀：枢纽把子数列分成左右两个可递归处理的区域。
分组正确 / 排序完成：一次划分只保证分组正确，递归完成后整个区间才排序完成。
分而治之：划分把一个问题拆成两翼，递归分别解决，再合并枢纽位置。
交换执行W次：运行步数中的 W 由输入决定，最多为 n-1。
第j小：枢纽若是当前子数列中的第 j 小元素，两翼大小就是 j-1 和 n-j。
子问题大小是0和n-1：枢纽落在端点时递归树退化为一边为空、一边少一个元素。
线性扫描代价 / 快排的复杂度：每层扫描是线性代价，但层数由枢纽分布决定快排的复杂度。
n!种排列：固定输入规模 n 有 n! 种互不相同的排列。
58/3：精确平均式中的常数写作 58/3，提醒近似阶隐藏了具体常数。
输入的n!种排列服从均匀分布：普通快排的 A(n) 结论依赖这条输入模型假设。
均匀随机选择枢纽项：随机快排不需要输入均匀，而是在当前区间均匀选择枢纽项。
固定元素j与k：比较次数证明固定一对元素 j,k，再研究它们是否相遇。
中间某个p：若区间内部的中间某个 p 先当枢纽，j 与 k 会被分到两翼。
永久分开：两元素被不同翅膀分开后，之后递归不会跨边界比较它们。
k-j+1个元素：从 j 到 k 的候选集合共有 k-j+1个元素。
双重和：逐对累加比较概率得到双重和，再按距离重排为调和数。
休闲餐厅中的随机算法：休闲餐厅的比喻把抽样、回避最坏情况和积累证据放在同一张菜单上。
Monte Carlo算法：Monte Carlo算法允许输出带概率保证的可能错误，必须说明失败含义。
抉择 / 确定性验证：随机探索完成后仍需做抉择，并可用确定性验证检查候选答案。
Iodine会场 / Iodine的元素符号I：Iodine会场的名称来自碘，I 是它的元素符号。
Oxygen的元素符号O：Oxygen 的元素符号 O，与 I 形成会场之间的输入输出连接。
统计性质：随机数表不能只凭外观看，还要指定要检验的统计性质。

互动实验与四步复盘

猜一猜：把枢纽选择从固定最左改成随机选择，会让最坏情况消失，还是只改变它出现的概率？切换策略，观察递归树形状与分析对象的变化。

QuickSort Pivot Lab

在同一输入上切换枢纽策略，观察平均对象从哪里来。

当前策略：随机选择

分析结论：Θ(n log n) 期望

对任意固定输入平均化枢纽秩。

分步1 / 4

1. 划分：让枢纽落位

追踪 p、k 和四个区域；区分分组正确与排序完成，并观察端点枢纽怎样制造长链。