形式陈述

随机化算法除输入外还读取独立随机位，其输出和运行时间成为随机变量。Las Vegas 算法始终正确，但运行时间随机；Monte Carlo 算法在规定时间内结束，允许有界错误概率。对每个固定输入的最坏情况期望、对输入分布的平均情况和“高概率”界是不同保证。重复独立试验可放大成功率，例如单侧错误从 $p<1$ 降到 $p^k$；依赖试验不能直接套乘法。

直觉

随机选择可避免对手精心构造的坏模式，或用少量样本近似巨大空间。分析把输入固定，只对算法内部随机性取概率，除非明确采用平均输入模型。

例子与边界

随机 Quickselect 对任意固定数组具有期望线性时间；Miller–Rabin 是具有单侧错误的素性测试版本；随机哈希可降低碰撞。期望 $O(n)$ 不保证每次都在 $O(n)$ 内结束，高概率界也必须说明失败概率随哪个参数衰减。伪随机生成器在工程中替代真随机时，理论保证取决于对手模型。设定随机种子可复现实验，却不会把算法变成输入无关的确定性最坏界。

推论与应用

随机算法用于哈希、采样、数论、图算法、近似和分布式对称性破缺，常以更简单结构获得良好期望或高概率性能。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995，Chs. 1–7。