随机化算法

概述

随机化算法 在执行过程中利用随机数来控制算法行为，从而以概率方式保证正确性或性能。

定义

随机化算法

算法在运行过程中除了接收输入外，还访问一个随机数源（random number generator），使得算法的行为部分由随机比特决定。

核心性质

• Las Vegas 算法：总是给出正确答案，但运行时间是随机变量（如随机化快速排序）。
• Monte Carlo 算法：运行时间确定，但输出可能有错误，错误概率可通过重复运行降低。
• 随机化算法的优势：使算法性能不依赖于特定输入分布，将概率分析内化到算法本身。
• 随机化快速排序通过随机选择主元（pivot），使得对任何输入的期望运行时间均为 $\Theta (n\lg n)$。

章节扩展

第2章：入门

• 2.2 算法分析 引入随机化思想，说明随机化可以消除算法对输入分布的依赖。
• 第5章和第7章将深入讨论概率分析与随机化算法的设计与分析。

第5章：概率分析与随机化算法

• 5.3 随机化算法 详细介绍了随机化算法与概率分析的区别
• RANDOMIZE-IN-PLACE 生成均匀随机排列（引理5.3、5.4）
• 随机化算法分为 Las Vegas 和 Monte Carlo 两类
• 参见：概率分析、均匀随机排列

参见

• 平均情况分析
• 最好情况分析