算法与数据结构 · 第 8 课
随机化算法入门:为什么随机 Quickselect 期望线性,却仍可能最坏平方?
2026 年 10 月 27 日|第 2 周 · 第 1 节|正文约 16–17 分钟(自测另计)
上一课证明了 BFPRT 的最坏线性时间。今天不再重复五元组证明,而是回答另一个问题:不精心挑枢轴,仅靠每轮随机挑一个元素,为什么仍能有可证明的效率?“期望”又究竟保证了什么?
一、学习目标与成本模型(约 1 分钟)
本课结束应能:区分 Las Vegas 与 Monte Carlo;准确指出随机性来自哪里;写出能处理重复值的三路 Quickselect;利用条件概率 + 几何等待证明期望运行时间 (O(n)),并构造其最坏 (\Theta(n^2)) 执行。
明确假设: 输入数组 (A) 和排名 (1\le k\le n) 固定;每轮在当前未处理区间的元素位置上重新均匀抽样,新抽样不受以往枢轴选择偏置;比较、交换和取一个随机索引的成本按 (O(1)) 计;每轮原地三路分区扫描 (O(m)) 项,其中 (m) 为当前区间长度。元素可相等,排名采用升序、从 1 开始的多重集合排名。
二、随机性到底影响“正确性”还是“运行时间”?(约 2 分钟)
Las Vegas 算法: 对每个合法输入,只要算法结束,答案总是正确;随机性影响运行时间或搜索路径。随机 Quickselect 是典型例子:枢轴可能很坏,但正确分区后从未丢掉目标排名。
Monte Carlo 算法: 在受控的计算预算内给出答案,允许经过明确概率界约束的错误。一个直观例子是“快速判断两个等长位数组是否一致”:独立均匀抽取 (t) 个位置逐一比较,只要发现不同就报告“不一致”,否则报告“看上去一致”。若两数组至少有 (\varepsilon n) 个位置不同,则错误地报告一致的概率为
[ \Pr(\text{漏检})\le (1-\varepsilon)^t. ]
为什么?一次抽样未碰到差异的概率至多 (1-\varepsilon),在独立、有放回抽样下,连续 (t) 次未碰到的概率是其 (t) 次方。这里能在少量抽样下保证低误差,依赖“差异比例至少 (\varepsilon)”的前提;若仅差一个位置,错误概率变为 ((1-1/n)^t),不能宣称小样本就很可靠。这是 Monte Carlo 的“错误概率—成本”权衡。
两类算法不能仅根据“有没有 random()”判断:应分别检查输出能否错误、计算成本在哪个随机意义下有界。
三、固定输入与随机运行:期望对谁取?(约 2 分钟)
对一个固定的最坏排列 (A) 及固定 (k),算法可能沿多条由随机数决定的执行轨迹运行。记随机选择序列为 (R),时间为 (T(A,k;R))。我们要证明的是:
[ \boxed{\forall A,\forall k:\quad \mathbb E_R[T(A,k;R)]\le Cn.} ]
这不是“把所有可能输入平均一下”的 average-case 保证。即使输入是对抗性地预先固定的,也对该输入单独成立。
简单回顾离散期望:若随机变量 (X) 取值 (x_i) 的概率为 (p_i),则 (\mathbb E[X]=\sum_i p_ix_i);若观察到了先前抽样的历史 (H),就应使用条件概率 (\Pr(\cdot\mid H)) 与条件期望。今天的证明必须在任意已有历史下仍能推进,而不能只分析第一轮的平均划分。
四、算法:三路分区,永远不丢目标排名(约 3 分钟)
与上课的 BFPRT 相比,只有一处实质变化:从确定性五元组枢轴改为从当前区间均匀随机抽取;小于、等于、大于三路分区及排名更新不变。
RandomQuickselect(A, k): # 1 ≤ k ≤ |A|
lo = 0; hi = |A| - 1 # k 是当前区间的 1-based 排名
while lo < hi:
p = A[RandomIntInclusive(lo, hi)]
lt = lo; i = lo; gt = hi
while i <= gt:
if A[i] < p:
swap(A[lt], A[i]); lt += 1; i += 1
elif A[i] > p:
swap(A[i], A[gt]); gt -= 1
else:
i += 1
a = lt - lo # 小于 p 的数量
b = gt - lt + 1 # 等于 p 的数量
if k <= a:
hi = lt - 1
elif k <= a + b:
return p
else:
lo = gt + 1
k -= a + b
return A[lo]
扫描中不变量(这里只说当前区间):
[ \underbrace{A[lo:lt]}{<p}\quad \underbrace{A[lt:i]}{=p}\quad \underbrace{A[i:gt+1]}{\text{未检查}}\quad \underbrace{A[gt+1:hi+1]}{>p}. ]
特别注意:遇到 (A[i]>p) 时,将它与右端未检查元素交换,不能立刻把 (i) 加一;新换回来的元素尚未分类。每一步都会缩小“未检查”区间,扫描必终止。
分区结束时,原区间里最小的 (a) 个值在 (L),紧接着 (b) 个值都等于 (p),剩下在 (G)。若 (k\le a) 就进入 (L);若 (a<k\le a+b) 直接返回 (p);否则进入 (G),新排名 (k’=k-a-b)。归纳可知目标排名始终被保留,因此随机枢轴不会造成答案错误。每轮至少剔除包含枢轴的非空等值段;迭代实现最终停止。
flowchart TD
A["固定输入 A、排名 k"] --> B["从当前区间均匀随机抽一个枢轴 p"]
B --> C["单次扫描:L 小于 p / E 等于 p / G 大于 p"]
C --> D{"k 落在哪里?"}
D -->|L| E["只保留 L;k 不变"]
D -->|E| F["返回 p:正确性不依赖枢轴质量"]
D -->|G| G["只保留 G;k ← k - |L| - |E|"]
E --> B
G --> B
一次数值 Trace。 输入 (A=[7,2,9,1,4,8,3,6]),求第 (5) 小。假设第一次随机选 (p=4):
| 分组 | 元素(组内尚未排序) | 数量 |
|---|---|---|
| (L) | [2,1,3] | 3 |
| (E) | [4] | 1 |
| (G) | [7,9,8,6] | 4 |
因为 (k=5>3+1),进入 (G),新的 (k’=1)。再假设抽到 (p=7),其小于段为 [6],目标落在左段。最后单元素返回 6。这里的 4 和 7 是一条示例随机轨迹,不是“算法必然选择”的枢轴。
五、先算一轮:平均缩小,不等于每轮都缩得好(约 2 分钟)
假设当前有 (m) 个互异键,目标第 (k) 小;把枢轴在升序中的名次记为 (j)。由于枢轴从所有位置均匀抽取,(\Pr(j=s)=1/m)。一次分区后需要递归的元素数 (S_j) 是
[
S_j=
\begin{cases}
m-j, & j<k \quad (\text{进右侧}),
0, & j=k \quad (\text{直接找到}),
j-1, & j>k \quad (\text{进左侧}).
\end{cases}
\qquad
\mathbb E[S]=\frac1m\sum_{j=1}^{m}S_j.
]
这是单轮期望,尚不是整个算法的时间复杂度。更不能随意写 (\mathbb E[T(S)]=T(\mathbb E[S])):对非线性的 (T),把期望移入函数通常不成立。我们需要真正控制可能连续出现的坏枢轴。
六、关键证明:坏枢轴会发生,为什么总期望还是 (O(n))?(约 3 分钟)
给当前 (m) 个元素排一个带唯一位置标签的全序(相等键可用固定标签打破名次平局;算法本身仍按键值三路分区)。定义“好枢轴”为其排名 (j) 落在
[ \boxed{\lfloor m/4\rfloor+1\ \le j\ \le\ \lceil3m/4\rceil}. ]
这个集合里至少有 (m/2) 个排名,因为
[ \lceil3m/4\rceil-\lfloor m/4\rfloor\ge m/2. ]
故在任意已发生的历史下,下一轮选到好枢轴的条件概率至少 (1/2)。若选到好枢轴,左侧至多 (j-1\le3m/4) 个,右侧至多 (m-j\le3m/4) 个;等值元素一并从递归中剔除,只会让剩余规模更小。
现在不要求连续每轮都好,而是把算法切成若干阶段:每个阶段从当前规模 (M) 开始,直到选到一次好枢轴或算法提前结束。
若 (N) 是本阶段发生的分区次数,由于每轮的条件成功概率 (\ge1/2),
[ \Pr(N>t)\le(1/2)^t, \quad \mathbb E[N] =\sum_{t=0}^{\infty}\Pr(N>t) \le \sum_{t=0}^{\infty}2^{-t}=2. ]
所以阶段里虽然可能遇到很多坏枢轴,但期望至多扫描两轮。坏轮不会使区间变大,每轮至多耗费 (cM),故该阶段的期望成本不超过 (2cM)。
每经历一次好枢轴,下一阶段起始规模最多变为此前的 (3/4)。于是各阶段期望工作量受控于
[
\begin{aligned}
\mathbb E[T(n)]
&\le 2cn+2c(3n/4)+2c(3/4)^2n+\cdots+O(1)
&\le 2cn\sum_{r\ge0}(3/4)^r+O(1)
=\boxed{8cn+O(1)=O(n)}.
\end{aligned}
]
这是一个针对任意固定输入的期望上界,只用到每轮条件均匀随机抽样与线性分区成本;证明没有假设每轮缩小 (3/4),也没有用错误的“期望规模代替随机规模”。
七、边界、反例与与 BFPRT 的区别(约 2 分钟)
为什么还有 (\Theta(n^2)) 最坏执行? 对互异键 (1,2,\ldots,n) 查第 (n) 小(最大值),设随机过程每轮恰好都抽中当前最小值。每轮只丢弃一个元素,扫描成本按区间规模依次为 (n,n-1,\ldots,2),总和 (\Theta(n^2))。这条随机轨迹概率虽很小(均匀独立抽样下为 (1/n!)),却是合法轨迹。期望线性不等于每次运行线性。
为什么重复值一定要处理? 若采用“(\le p)”的二路 Lomuto 分区,全相等输入可能每次都只去掉一个元素,随机选什么位置都无法改善。三路分区将整个等值段一次排除,全相等输入一次扫描即可返回。
| 算法 | 输出正确性 | 时间保证 | 代价与边界 |
|---|---|---|---|
| 随机 Quickselect + 三路分区 | 一定正确(Las Vegas) | 期望 (O(n)),最坏 (\Theta(n^2)) | 枢轴每轮条件均匀抽样;迭代原地辅助空间 (O(1)) |
| BFPRT + 三路分区 | 一定正确(确定性) | 最坏 (O(n)) | 需要额外的分组与中位数选择工作 |
| 固定预算随机抽样判断“是否一致” | 可能漏检(Monte Carlo) | 样本数给定时 (O(t)) | 误差受差异比例 (\varepsilon) 与独立抽样前提控制 |
适用前提辨析: 若随机种子对攻击者完全可预测,他可以针对产生的枢轴序列构造坏输入;不能把“对真实随机选择取期望”的数学结论升级成“固定任何种子也具有最坏线性保证”。同时,概率上的快也不等于一定快;重视硬实时最坏延迟时,BFPRT 一类确定性保证可能更合适。
八、今日总结与下一课
本课真正需要记住的不是“随机快”,而是三个逻辑层次:分区不变量保证答案正确;好枢轴的条件概率保证不会在同一尺度上平均停留太久;阶段成本形成收敛几何级数,得到期望线性。 哪一层缺失,都不能直接宣称 Las Vegas 期望 (O(n))。
下一课(2026-10-28,第 9 课): 从选择算法的随机枢轴转向随机哈希:随机函数族、碰撞概率、链地址法为何能在明确负载条件下达到期望 (O(1)),以及为什么不能简单假设“哈希值天然均匀”。
九、四级自测(100 分;首次不给答案)
四题依次考机制辨析、期望数值计算、复杂度边界推理和完整证明。前三题由互动测验客观判分;Lv4 需要书面推导,由自评/人工/ChatGPT 批改。首次不显示答案,提示不泄露选项。
Lv1|Las Vegas / Monte Carlo 与复杂度保证|15 分|预计 2 分钟|单选
关于 Las Vegas、Monte Carlo 和随机 Quickselect,下列哪一项同时正确?
A. Las Vegas 必须在预设时间内返回,允许小概率错误;Monte Carlo 保证答案正确但运行时间随机。
B. 随机 Quickselect 的答案始终正确;每轮在当前区间均匀随机选枢轴时,期望耗时为 O(n),但某次执行仍可能需要 Θ(n²)。
C. 随机 Quickselect 期望线性,因此固定任意一个伪随机种子也能保证最坏 O(n)。
D. 给任何确定性算法加入随机选择,都能自动把最坏运行时间降到 O(n)。
中立提示:区分输出是否允许出错、时间的随机性,以及“期望”到底对什么取平均。
Lv2|枢轴位置的离散均匀分布与期望|20 分|预计 3 分钟|数值
有 n=8 个互异键,目标是第 k=5 小。第一次分区从 8 个当前位置等概率选枢轴,采用三路分区。令 S 为第一次分区后仍需继续处理的子问题元素数;若枢轴恰好第 5 小,则 S=0。求 E[S](单位:元素;填数值)。
中立提示:用枢轴在升序中的名次 j=1,…,8 枚举;分别讨论 j<k、j=k、j>k,再把八种剩余规模平均。
Lv3|条件期望、重复键、递归误区|25 分|预计 4 分钟|多选
下列判断哪些正确?(多选,选出全部正确项)
A. 对任意固定输入(允许重复键)和合法 k,若每轮在当前区间重新均匀抽枢轴并正确三路分区,随机 Quickselect 的期望时间为 O(n)。
B. 随机枢轴自动排除了最坏 Θ(n²) 的执行,因此不需要考虑连续抽到端点的情况。
C. 只要知道 E[S]≤3n/4 且 T 单调,就必然有 E[T(S)]=T(E[S]),可直接替换递归规模。
D. 如果每次条件概率至少 1/2 将规模降到当前规模的 3/4 以下,且每轮工作 O(当前规模),则可用几何等待与分阶段求和证明期望 O(n)。
中立提示:检查“对随机运行时间取期望”与“每次运行的最坏情况”;并回忆一般的非线性函数能否把期望移入函数。
Lv4|算法设计、不变量与概率分析|40 分|预计 9 分钟|开放推导
设计可处理重复键的原地随机 Quickselect(输入长度 n≥1,排名 k 从1开始)。(a) 写出随机枢轴与三路分区伪代码,说明循环不变量和排名更新为何正确(12分);(b) 对当前大小 m,证明“好枢轴”的条件概率至少1/2,且发生时下一子问题大小不超过3m/4,注明整数端点、重复值的处理(10分);(c) 用几何等待和阶段成本严格推出期望 O(n),不得直接假定 E[T(S)]=T(E[S])(12分);(d) 构造一次 Θ(n²) 的合法随机执行,解释为何它不否定期望线性,并与 BFPRT、Monte Carlo 的保证作比较(6分)。
中立提示:可用 [⌊m/4⌋+1, ⌈3m/4⌉] 作为好枢轴名次集合;在两次好枢轴之间,当前区间大小不会增加。
十、作答方式
回复 Lv1:选项;Lv2:数值及简要算式;Lv3:全部选项;Lv4:(a)–(d) 分步证明。批改总分 100 分:80–100 继续,60–79 补一道针对题,低于 60 先复习分区不变量和条件概率;补练不改变自然日课号。