算法设计第 7 章：概率算法——四类随机化与跳跃表的期望分析

概率算法把"随机"变成一种设计资源：不是让结果变得不可靠，而是让最坏情况的触发条件不再由输入决定。这一章最容易被学成"随机快排"四个字，其实它真正要建立的是区分能力——同样是随机，有的算法允许答案错（蒙特卡洛），有的允许不出答案（拉斯维加斯），有的答案与时间都可靠、只是打乱输入（舍伍德）。分不清这三者，复杂度分析就会写错对象。

一、随机化思想与四类概率算法

确定性算法对每个输入都有唯一确定的执行路径；概率算法在执行中做随机选择，因此对同一输入可能走不同路径。按"可靠性"与"目标"两个维度分成四类：

类型	答案正确性	运行时间	典型问题
数值概率算法	近似解，误差随规模下降	确定	定积分、π 的估算
蒙特卡洛算法	一般正确，可能出错	确定上界	判定问题、素数测试
拉斯维加斯算法	一定正确	随机，可能失败	n 后、随机化线性选择
舍伍德算法	一定正确	确定上界	随机快排、随机选择

关键在于后两者常被混为一谈：舍伍德不改变算法的确定性，只消除"坏输入"与"坏随机选择"的相关性，所以它连最坏情况都能保证；拉斯维加斯把不确定性放在时间上，可能一直找不到解，但一旦返回就必对。

蒙特卡洛的可靠性靠重复提升：若单次正确概率 p > 1/2，独立跑 k 次取多数，错误率降到 (1−p)^k 级别。重复是蒙特卡洛的标准补救手段，代价是时间乘 k。

二、蒙特卡洛方法计算定积分

求 I = ∫ₐᵇ f(x) dx。取 n 个 [a, b] 上均匀分布的随机点 xᵢ，用

I ≈ (b − a)/n · Σ f(xᵢ)

这是"随机投点"的期望形式：每个点的贡献 (b−a)f(xᵢ) 的期望恰为 I。由中心极限定理，误差量级 O(1/√n)，与积分维数 d 无关。

这一点是它相对网格法的全部价值。d 维网格取每维 m 个点需要 m^d 次求值，误差 O(m⁻¹) = O(n^(-1/d))；当 d = 10 时，要达到 10⁻³ 精度，网格法需要 10³⁰ 次求值，蒙特卡洛只要 10⁶ 次。高维积分是蒙特卡洛的主场，一维反而是它的短板（梯形法误差 O(n⁻²) 更快）。

代价是结果随机：同样的 n 跑两次结果不同，报误差区间而非精确值。这是数值概率算法的共同特征。

三、舍伍德算法消除最坏情况

舍伍德的思路是：如果一个算法的最坏情况由特定输入触发（如快排遇到已排序数组），就在算法里引入随机选择，让任何输入都表现为"随机输入"。

随机化快速排序：基准从当前区间中等概率随机选取，而不是固定取首元素。对任意输入，划分的期望比例为常数比，期望时间 O(n log n)，且最坏 O(n²) 的概率随 n 增大迅速趋零。注意它没有把最坏情况降到 O(n log n)——理论上仍可能每次都选到极值，只是这个事件不再由输入控制。

随机化线性选择：随机选基准划分后只递归一侧，期望 O(n)，与第 2 章"五分化中"的确定性 O(n) 形成对照：一个是期望线性、常数小，一个是确定线性、常数大。

洗牌算法：对输入先做一次均匀随机置换，再跑确定性算法。这是舍伍德最纯粹的形式——算法一行没改，只把"输入分布"变成均匀的。

舍伍德的正确性从不打折，改变的是时间复杂度的分析对象：从"最坏输入"变成"期望随机选择"。

四、跳跃表：概率数据结构的样板

跳跃表在有序链表上叠加多层索引：每个元素以概率 p（通常 1/2）出现在上一层，层数由抛硬币决定，直到失败或达到上限。

• 查找：从最高层出发，能右移就右移，不能则下降一层。期望比较次数 O(log n)，期望空间 O(n)（每层元素数按 1/2 递减，总数 2n）。
• 插入 / 删除：先查找定位，再按随机层数更新各层指针，期望 O(log n)。
• 最坏情况：所有元素层数一致时退化为链表 O(n)，但概率极低。

它替代平衡树的价值在于：不需要旋转、不需要再平衡，实现只有几十行，并发场景下锁的粒度更小（Redis 的有序集合、LevelDB 的 memtable 都用它）。代价是依赖随机数质量，且常数比红黑树略大。

跳跃表是"用概率换实现复杂度"的典型：放弃最坏情况保证，换取代码简洁与期望性能。

五、拉斯维加斯与蒙特卡洛：怎么选

维度	拉斯维加斯	蒙特卡洛
答案	必正确	可能错
时间	随机，可能不终止/返回失败	有确定上界
重复的作用	提高成功概率	降低错误率
分析对象	期望运行时间	单次正确概率
例子	n 后随机放置、随机化选择	素数测试、字符串指纹

选择判据：结果必须绝对可信、且允许重试，用拉斯维加斯（如密码学中的随机素性构造）；时间有硬上界、允许极小错误概率，用蒙特卡洛（如 Miller-Rabin 素性测试，跑 40 轮错误率低于 2⁻⁸⁰）。

一个常被忽略的事实：两者可以互相转化。给拉斯维加斯算法加一个超时截断，失败就报"未知"，就成了蒙特卡洛；把蒙特卡洛算法重复到验证通过，就成了拉斯维加斯（如果验证是多项式时间的）。

易错点

1. 把随机快排说成"最坏 O(n log n)"，它是最坏 O(n²)、期望 O(n log n)。
2. 混淆拉斯维加斯与舍伍德，前者时间随机、后者时间确定。
3. 认为蒙特卡洛的误差随 n 线性下降，实际是 O(1/√n)。
4. 跳跃表查询写成 O(log n) 最坏，它只是期望 O(log n)。
5. 忘记"重复 k 次"对蒙特卡洛是乘 k 的时间代价。

这一章在整门课里的位置

本章建立在第 2、4 章的排序、选择与最短路之上，用随机化改造它们的最坏情况。第 8 章的随机化归约与近似算法会用到本章的"高概率"论证；第 9 章的字符串指纹（Rabin-Karp）是蒙特卡洛思想的直接应用；第 10 章的启发式搜索也常用随机重启来跳出局部最优。

本文是《算法设计与分析（89 讲）》第 7 章的知识点摘要。完整板书与代码见 课程页；上一章 分支限界法，下一章 NP 完全性理论。