在此之前，我们所讨论的算法都是确定性的——对于同一输入，算法的执行路径和输出结果完全固定。确定性给人以安全感：只要算法正确，结果永远正确。但这种安全感有时以效率为代价：确定性的快速排序在最坏情况下退化到 Θ(n2)Θ(n2)，确定性的素数测试直到2002年才出现多项式算法且常数巨大。随机化算法打破了这一范式——它在算法内部引入随机决策，使得同一输入在不同运行中可能产生不同的执行路径，甚至不同的输出。这种“刻意的不确定”并非缺陷，而是一种强大的设计工具。
一、两类随机化算法的严格定义
根据输出正确性与运行时间的保证方式，随机化算法分为两类。
拉斯维加斯算法：输出结果绝对正确，但运行时间是随机变量。算法可能在某些随机选择下运行得很快，在另一些选择下运行得很慢，但无论随机选择如何，一旦终止，输出必为正确解。拉斯维加斯算法的性能指标是期望运行时间。
蒙特卡洛算法：运行时间是确定的（或至少是有界的），但输出结果可能错误。算法以一定的概率返回正确解，以互补的概率返回错误解。蒙特卡洛算法的性能指标是错误概率，通常可以通过多次独立运行将错误概率压缩至任意小。
两类算法并非对立，而是可以在同一问题中相互转化。例如，若一个拉斯维加斯算法在某些随机选择下运行时间过长，可以设置超时强制终止并切换为蒙特卡洛算法，以可控的错误概率换取运行时间的上限保证。这种混合策略在实际系统中十分常见。
二、随机快速排序：拉斯维加斯范式的典范
快速排序的性能瓶颈在于主元的选择。确定性快速排序通常固定选择首元素或末元素作为主元，这一策略在输入已有序或逆序时导致每次划分极度不平衡，递归深度达到 nn，总比较次数 Θ(n2)Θ(n2)。
随机快速排序的策略极其简单：每次从待划分子数组中均匀随机地选取一个元素作为主元。这一随机化操作使得无论输入数组的初始排列如何，主元在排序序列中的排名的分布始终是均匀的。算法的正确性不受随机选择影响——无论选谁做主元，划分操作都能正确执行，最终排序结果总是正确的。因此随机快速排序是典型的拉斯维加斯算法。
期望运行时间的分析依赖于一个关键观察：随机快速排序的比较次数等于任意两个元素被比较的概率之和。设输入数组已按升序重新标号为 z1<z2<⋯<znz1<z2<⋯<zn。元素 zizi 与 zjzj（i<ji<j）发生比较，当且仅当在包含 zi,…,zjzi,…,zj 的子数组中，第一个被选为主元的是 zizi 或 zjzj。在包含这 j−i+1j−i+1 个元素的子数组中，每个元素被选为主元的概率相等，因此 zizi 和 zjzj 被比较的概率为 2j−i+1j−i+12。对所有元素对求和：
E[X]=∑i=1n−1∑j=i+1n2j−i+1<2n∑k=2n1k=2n(Hn−1)=Θ(nlogn)E[X]=∑i=1n−1∑j=i+1nj−i+12<2n∑k=2nk1=2n(Hn−1)=Θ(nlogn)
其中 HnHn 是第 nn 个调和数。这一分析不依赖输入的分布——输入可以是任意排列，甚至是攻击者精心构造的最坏情况序列，期望比较次数始终是 Θ(nlogn)Θ(nlogn)。随机化提供了一种“普遍性”的保护：没有确定的坏输入，只有坏的随机选择，而坏随机选择的概率可以被严格控制。
三、Miller-Rabin素数测试：蒙特卡洛范式的代表
素数判定是密码学的核心操作。给定一个 nn 位整数 NN，判断其是否为素数。确定性算法AKS虽然在理论上将问题纳入P类，但其 O~(n6)O~(n6) 的运行时间对于实际密码学应用而言过慢。Miller-Rabin测试以概率算法的方式给出了实用的解决方案。
Miller-Rabin算法基于费马小定理的推广。若 NN 为奇素数，可写 N−1=2s⋅dN−1=2s⋅d（dd 为奇数）。对任意 aa 与 NN 互质，序列 ad,a2d,a4d,…,a2sdad,a2d,a4d,…,a2sd 模 NN 要么全为1，要么以 −1−1 后接1收尾。若 NN 为合数，至多四分之一的 a∈{2,…,N−2}a∈{2,…,N−2} 能使上述条件成立。
算法从 {2,…,N−2}{2,…,N−2} 中随机选取 kk 个基 aa，逐一测试。若任何一个基测试失败，则 NN 确定为合数（此输出100%正确）；若所有基测试通过，则输出“素数”。运行时间是确定的——每个基的测试仅需 O(logN)O(logN) 次模乘，总计 O(klogN)O(klogN)。然而，“素数”输出可能错误：NN 为合数但所有 kk 个基恰好均为“骗子”的概率不超过 (1/4)k(1/4)k。
这完美符合蒙特卡洛范式的特征：运行时间固定且可控，正确性以概率保证。取 k=40k=40，错误概率已降至 2−802−80，远低于硬件故障率，在密码学实践中被视为“确定无误”。通过增大 kk，错误概率可以指数级压缩，代价仅为线性增加的运行时间。
四、两类范式的选择与转化
选择拉斯维加斯还是蒙特卡洛，取决于应用对“效率不确定”与“结果不完美”的容忍度。
若应用场景要求输出绝对可信（如金融结算、安全关键系统），且期望运行时间在可接受范围内，应选择拉斯维加斯算法。随机快速排序和随机选择算法均属此类。
若应用场景允许极低概率的错误，但对运行时间有硬性上限要求，蒙特卡洛算法更合适。密码学中的素数生成大量使用Miller-Rabin，图算法中的最小割问题可用Karger的蒙特卡洛算法在 O~(n2)O~(n2) 时间内以高概率给出正确解。
值得指出的是，许多拉斯维加斯算法可以通过设置运行时间截断转化为蒙特卡洛算法：若算法在限定时间内完成，输出正确结果；若超时，则输出一个可能错误的结果或报告失败。这种转换在实时系统中尤为重要。
五、随机化方法的理论意义
随机化算法不仅在工程上提供了高效方案，更深刻地影响了计算复杂性理论。第10篇中我们讨论了P与NP。随机化引入了新的复杂度类：
RP（随机多项式时间）：存在多项式时间蒙特卡洛算法，对“是”实例以 ≥1/2≥1/2 概率正确，对“否”实例100%正确（单侧错误）。
BPP（有界错误概率多项式时间）：存在多项式时间蒙特卡洛算法，对任意实例错误概率 ≤1/3≤1/3（可放大至任意小）。
目前已知 P⊆RP⊆BPP⊆NPP⊆RP⊆BPP⊆NP，但 P=BPPP=BPP 是否成立仍是未解之谜。去随机化研究试图将随机化算法转化为确定性算法，近年来在特定问题（如素数判定AKS算法）上取得突破，但广泛意义上的去随机化依然是理论计算机科学的核心挑战。
六、总结与展望
随机化算法用一个小小的随机数生成器，换来了最坏情况复杂度的质变和实现难度的骤降。拉斯维加斯算法保证了绝对的正确性，蒙特卡洛算法以可控的错误概率换取确定性的效率。两者的灵活组合，使得算法设计者可以在正确性与效率之间精确调校。
下一篇，我们将继续随机化的主题，进入一个更巧妙的领域——随机化舍入与线性规划松弛。随机性不仅是加速计算的手段，还可以作为连接连续优化与离散优化的桥梁：先将整数约束松弛为线性约束，求分数解，再用随机化舍入技术恢复为整数解，同时以概率分析给出近似比的保证。这将是随机化方法在近似算法设计中的一次精彩亮相。
