在此之前我们所讨论的算法都是确定性的——对于同一输入算法的执行路径和输出结果完全固定。确定性给人以安全感只要算法正确结果永远正确。但这种安全感有时以效率为代价确定性的快速排序在最坏情况下退化到 Θ(n2)Θ(n2)确定性的素数测试直到2002年才出现多项式算法且常数巨大。随机化算法打破了这一范式——它在算法内部引入随机决策使得同一输入在不同运行中可能产生不同的执行路径甚至不同的输出。这种“刻意的不确定”并非缺陷而是一种强大的设计工具。一、两类随机化算法的严格定义根据输出正确性与运行时间的保证方式随机化算法分为两类。拉斯维加斯算法输出结果绝对正确但运行时间是随机变量。算法可能在某些随机选择下运行得很快在另一些选择下运行得很慢但无论随机选择如何一旦终止输出必为正确解。拉斯维加斯算法的性能指标是期望运行时间。蒙特卡洛算法运行时间是确定的或至少是有界的但输出结果可能错误。算法以一定的概率返回正确解以互补的概率返回错误解。蒙特卡洛算法的性能指标是错误概率通常可以通过多次独立运行将错误概率压缩至任意小。两类算法并非对立而是可以在同一问题中相互转化。例如若一个拉斯维加斯算法在某些随机选择下运行时间过长可以设置超时强制终止并切换为蒙特卡洛算法以可控的错误概率换取运行时间的上限保证。这种混合策略在实际系统中十分常见。二、随机快速排序拉斯维加斯范式的典范快速排序的性能瓶颈在于主元的选择。确定性快速排序通常固定选择首元素或末元素作为主元这一策略在输入已有序或逆序时导致每次划分极度不平衡递归深度达到 nn总比较次数 Θ(n2)Θ(n2)。随机快速排序的策略极其简单每次从待划分子数组中均匀随机地选取一个元素作为主元。这一随机化操作使得无论输入数组的初始排列如何主元在排序序列中的排名的分布始终是均匀的。算法的正确性不受随机选择影响——无论选谁做主元划分操作都能正确执行最终排序结果总是正确的。因此随机快速排序是典型的拉斯维加斯算法。期望运行时间的分析依赖于一个关键观察随机快速排序的比较次数等于任意两个元素被比较的概率之和。设输入数组已按升序重新标号为 z1z2⋯znz1z2⋯zn。元素 zizi 与 zjzjijij发生比较当且仅当在包含 zi,…,zjzi,…,zj 的子数组中第一个被选为主元的是 zizi 或 zjzj。在包含这 j−i1j−i1 个元素的子数组中每个元素被选为主元的概率相等因此 zizi 和 zjzj 被比较的概率为 2j−i1j−i12。对所有元素对求和E[X]∑i1n−1∑ji1n2j−i12n∑k2n1k2n(Hn−1)Θ(nlogn)E[X]∑i1n−1∑ji1nj−i122n∑k2nk12n(Hn−1)Θ(nlogn)其中 HnHn 是第 nn 个调和数。这一分析不依赖输入的分布——输入可以是任意排列甚至是攻击者精心构造的最坏情况序列期望比较次数始终是 Θ(nlogn)Θ(nlogn)。随机化提供了一种“普遍性”的保护没有确定的坏输入只有坏的随机选择而坏随机选择的概率可以被严格控制。三、Miller-Rabin素数测试蒙特卡洛范式的代表素数判定是密码学的核心操作。给定一个 nn 位整数 NN判断其是否为素数。确定性算法AKS虽然在理论上将问题纳入P类但其 O~(n6)O~(n6) 的运行时间对于实际密码学应用而言过慢。Miller-Rabin测试以概率算法的方式给出了实用的解决方案。Miller-Rabin算法基于费马小定理的推广。若 NN 为奇素数可写 N−12s⋅dN−12s⋅ddd 为奇数。对任意 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。这完美符合蒙特卡洛范式的特征运行时间固定且可控正确性以概率保证。取 k40k40错误概率已降至 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但 PBPPPBPP 是否成立仍是未解之谜。去随机化研究试图将随机化算法转化为确定性算法近年来在特定问题如素数判定AKS算法上取得突破但广泛意义上的去随机化依然是理论计算机科学的核心挑战。六、总结与展望随机化算法用一个小小的随机数生成器换来了最坏情况复杂度的质变和实现难度的骤降。拉斯维加斯算法保证了绝对的正确性蒙特卡洛算法以可控的错误概率换取确定性的效率。两者的灵活组合使得算法设计者可以在正确性与效率之间精确调校。下一篇我们将继续随机化的主题进入一个更巧妙的领域——随机化舍入与线性规划松弛。随机性不仅是加速计算的手段还可以作为连接连续优化与离散优化的桥梁先将整数约束松弛为线性约束求分数解再用随机化舍入技术恢复为整数解同时以概率分析给出近似比的保证。这将是随机化方法在近似算法设计中的一次精彩亮相。
【算法分析与设计】第23篇：随机化算法基础：拉斯维加斯与蒙特卡洛范式
在此之前我们所讨论的算法都是确定性的——对于同一输入算法的执行路径和输出结果完全固定。确定性给人以安全感只要算法正确结果永远正确。但这种安全感有时以效率为代价确定性的快速排序在最坏情况下退化到 Θ(n2)Θ(n2)确定性的素数测试直到2002年才出现多项式算法且常数巨大。随机化算法打破了这一范式——它在算法内部引入随机决策使得同一输入在不同运行中可能产生不同的执行路径甚至不同的输出。这种“刻意的不确定”并非缺陷而是一种强大的设计工具。一、两类随机化算法的严格定义根据输出正确性与运行时间的保证方式随机化算法分为两类。拉斯维加斯算法输出结果绝对正确但运行时间是随机变量。算法可能在某些随机选择下运行得很快在另一些选择下运行得很慢但无论随机选择如何一旦终止输出必为正确解。拉斯维加斯算法的性能指标是期望运行时间。蒙特卡洛算法运行时间是确定的或至少是有界的但输出结果可能错误。算法以一定的概率返回正确解以互补的概率返回错误解。蒙特卡洛算法的性能指标是错误概率通常可以通过多次独立运行将错误概率压缩至任意小。两类算法并非对立而是可以在同一问题中相互转化。例如若一个拉斯维加斯算法在某些随机选择下运行时间过长可以设置超时强制终止并切换为蒙特卡洛算法以可控的错误概率换取运行时间的上限保证。这种混合策略在实际系统中十分常见。二、随机快速排序拉斯维加斯范式的典范快速排序的性能瓶颈在于主元的选择。确定性快速排序通常固定选择首元素或末元素作为主元这一策略在输入已有序或逆序时导致每次划分极度不平衡递归深度达到 nn总比较次数 Θ(n2)Θ(n2)。随机快速排序的策略极其简单每次从待划分子数组中均匀随机地选取一个元素作为主元。这一随机化操作使得无论输入数组的初始排列如何主元在排序序列中的排名的分布始终是均匀的。算法的正确性不受随机选择影响——无论选谁做主元划分操作都能正确执行最终排序结果总是正确的。因此随机快速排序是典型的拉斯维加斯算法。期望运行时间的分析依赖于一个关键观察随机快速排序的比较次数等于任意两个元素被比较的概率之和。设输入数组已按升序重新标号为 z1z2⋯znz1z2⋯zn。元素 zizi 与 zjzjijij发生比较当且仅当在包含 zi,…,zjzi,…,zj 的子数组中第一个被选为主元的是 zizi 或 zjzj。在包含这 j−i1j−i1 个元素的子数组中每个元素被选为主元的概率相等因此 zizi 和 zjzj 被比较的概率为 2j−i1j−i12。对所有元素对求和E[X]∑i1n−1∑ji1n2j−i12n∑k2n1k2n(Hn−1)Θ(nlogn)E[X]∑i1n−1∑ji1nj−i122n∑k2nk12n(Hn−1)Θ(nlogn)其中 HnHn 是第 nn 个调和数。这一分析不依赖输入的分布——输入可以是任意排列甚至是攻击者精心构造的最坏情况序列期望比较次数始终是 Θ(nlogn)Θ(nlogn)。随机化提供了一种“普遍性”的保护没有确定的坏输入只有坏的随机选择而坏随机选择的概率可以被严格控制。三、Miller-Rabin素数测试蒙特卡洛范式的代表素数判定是密码学的核心操作。给定一个 nn 位整数 NN判断其是否为素数。确定性算法AKS虽然在理论上将问题纳入P类但其 O~(n6)O~(n6) 的运行时间对于实际密码学应用而言过慢。Miller-Rabin测试以概率算法的方式给出了实用的解决方案。Miller-Rabin算法基于费马小定理的推广。若 NN 为奇素数可写 N−12s⋅dN−12s⋅ddd 为奇数。对任意 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。这完美符合蒙特卡洛范式的特征运行时间固定且可控正确性以概率保证。取 k40k40错误概率已降至 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但 PBPPPBPP 是否成立仍是未解之谜。去随机化研究试图将随机化算法转化为确定性算法近年来在特定问题如素数判定AKS算法上取得突破但广泛意义上的去随机化依然是理论计算机科学的核心挑战。六、总结与展望随机化算法用一个小小的随机数生成器换来了最坏情况复杂度的质变和实现难度的骤降。拉斯维加斯算法保证了绝对的正确性蒙特卡洛算法以可控的错误概率换取确定性的效率。两者的灵活组合使得算法设计者可以在正确性与效率之间精确调校。下一篇我们将继续随机化的主题进入一个更巧妙的领域——随机化舍入与线性规划松弛。随机性不仅是加速计算的手段还可以作为连接连续优化与离散优化的桥梁先将整数约束松弛为线性约束求分数解再用随机化舍入技术恢复为整数解同时以概率分析给出近似比的保证。这将是随机化方法在近似算法设计中的一次精彩亮相。
