随机化算法（Randomized Algorithm）
1. 核心思想
随机化算法在算法的执行过程中引入随机数，把随机数作为决策依据的一部分。这样做通常有两类收益：
- 降低最坏情况出现的概率：让对手无法构造出专门针对算法的输入（如随机化快速排序）；
- 用可控的出错概率换取效率：允许极小概率给出错误答案，但速度远快于确定性算法（如 Miller-Rabin 素数测试）。
2. 四种主要类型
| 类型 | 特点 | 举例 |
|---|---|---|
| 数值随机化算法 | 求数值问题的近似解，解的精度随计算时间增加而提高 | 随机投点法计算 $\pi$、计算定积分 |
| 舍伍德（Sherwood）算法 | 总能求出正确解，随机化只为消除最坏情形 | 随机化快速排序、随机化线性时间选择 |
| 拉斯维加斯（Las Vegas）算法 | 一旦找到解一定正确，但运行时间不确定 | n 皇后问题的随机化回溯、随机化素数分解 |
| 蒙特卡罗（Monte Carlo）算法 | 运行时间固定，但可能给出错误解，可通过重复执行降低出错概率 | Miller-Rabin 素数测试、素数判定 |
记忆：舍伍德求稳、拉斯维加斯求对、蒙特卡罗求快。
3. 蒙特卡罗算法的出错概率
若单次执行得到正确解的概率为 $p$（$p > 1/2$），独立重复执行 $k$ 次，则全部出错的概率不超过：
$$ (1-p)^k $$因此只要重复足够多次，出错概率可以降到任意小——这就是 Miller-Rabin 素数测试在实践中被广泛使用的原因。
4. 典型问题
| 问题 | 类型 | 思路 |
|---|---|---|
| 随机化快速排序 | 舍伍德 | 随机选取基准值，避免有序输入退化为 $O(n^2)$ |
| 随机化线性时间选择 | 舍伍德 | 随机选取划分元素，期望时间 $O(n)$ |
| 素数测试 | 蒙特卡罗 | Miller-Rabin：合数被误判为素数的概率 $\le 4^{-k}$ |
| 计算 $\pi$ | 数值随机化 | 向单位正方形内随机投点，用落入内切圆的频率估计面积比 |
| 随机化最小割 | 蒙特卡罗 | Karger 算法，重复 $O(n^2\log n)$ 次以高概率得到最小割 |
| 整数因子分解 | 拉斯维加斯 | Pollard’s Rho |
5. 期望运行时间分析
对拉斯维加斯算法，通常分析期望运行时间。例如随机化快速排序，设 $T(n)$ 为期望比较次数，可推出：
$$ T(n) = O(n\log n) $$分析的关键是：每一对元素被比较的概率等于它们在随机排列中相邻的概率，求和后得到 $2n\ln n$ 量级。
评论