数据结构与算法 / 系统课时

随机化算法

随机化算法

随机化算法把随机选择纳入计算过程,用来打破固定输入结构、降低对抗性数据的影响,或用可控错误概率换取速度。本课将区分两类随机化模型,并通过随机快速排序理解“结果始终正确、运行时间具有随机性”的分析方式。

学习目标

  • 区分拉斯维加斯算法与蒙特卡洛算法的保证。
  • 解释随机快速排序的最坏时间与期望时间。
  • 使用固定随机种子复现实验,并识别安全随机场景。

为什么引入随机性

确定性算法对同一输入总是走相同路径。如果输入刚好触发坏情况,或者数据由对手刻意构造,性能可能持续恶化。随机化通过打乱选择,使输入结构难以稳定控制算法行为。

随机性不会自动消除最坏情况。它改变的是坏情况出现的概率或期望成本,因此分析时必须说明随机变量来自哪里、期望对哪些随机选择取平均,以及算法是否允许错误答案。

拉斯维加斯与蒙特卡洛算法对比及随机快速排序流程

两类随机化算法

类型 正确性保证 时间特征 典型例子
拉斯维加斯算法 只要终止,输出一定正确 运行时间受随机选择影响,通常分析期望时间 随机快速排序、随机选择算法
蒙特卡洛算法 允许可量化的小概率错误 给定迭代轮数后,运行时间通常有明确上界 Miller-Rabin 概率素性测试、随机指纹算法

拉斯维加斯算法可以多花时间,但不能返回错误结果。蒙特卡洛算法则在规定计算预算内给出答案,代价是存在错误概率。独立重复通常可以降低错误概率,但降低幅度必须根据具体算法证明。

随机快速排序的分析

快速排序的分区工作与普通版本相同,区别在于每次从当前子数组中均匀随机选择枢轴。无论枢轴如何选择,只要分区和递归实现正确,最终排序结果都正确,因此它属于拉斯维加斯算法。

若每次都选到极端元素,递归规模会变成 n−1n-1 与 00,最坏时间仍是 O(n2)O(n^2)。但随机枢轴使持续极端分割的概率很低,对内部随机选择取期望后,比较次数为 O(nlog⁡n)O(n \log n)。

期望复杂度不是“多数输入上的复杂度”,而是固定输入后,对算法内部随机选择求平均。即使输入已经升序排列,只要枢轴均匀随机选择,期望时间仍保持 O(nlog⁡n)O(n \log n)。

可运行示例

下面的 Python 示例使用独立的 random.Random 实例选择枢轴。固定种子只用于让实验可复现,排序正确性不依赖某个特定种子。

python
import random

def randomized_quicksort(values, rng):
    if len(values) <= 1:
        return values.copy()

    # 枢轴在当前子数组中均匀随机选择,避免固定位置造成输入偏置。
    pivot = values[rng.randrange(len(values))]
    less = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    greater = [value for value in values if value > pivot]

    return (
        randomized_quicksort(less, rng)
        + equal
        + randomized_quicksort(greater, rng)
    )

def main():
    numbers = [9, 1, 5, 3, 9, 2, 8]
    rng = random.Random(7)

    print("原数组:", numbers)
    print("排序后:", randomized_quicksort(numbers, rng))

if __name__ == "__main__":
    main()

保存为 randomized_quicksort_demo.py 后运行:

bash
python randomized_quicksort_demo.py

预期输出

text
原数组: [9, 1, 5, 3, 9, 2, 8]
排序后: [1, 2, 3, 5, 8, 9, 9]

该实现为了突出随机枢轴与三路分区,使用额外列表,并不是原地快速排序。无论随机选择顺序如何,输出都保持升序;变化的是递归形状和实际比较成本。

Tips 与常见错误

  • 单元测试中可以固定种子以复现失败路径,但性能评估应使用多个种子并报告平均值或分布。
  • Python 的 random 适合模拟与一般算法实验,不适合生成密码、令牌或密钥;安全随机值应使用 secrets。
  • 不要把期望 O(nlog⁡n)O(n \log n) 写成最坏 O(nlog⁡n)O(n \log n)。随机快速排序仍存在最坏 O(n2)O(n^2) 路径。
  • 蒙特卡洛算法必须给出错误类型和概率上界,不能只说“结果大概率正确”。

本课练习

  1. 修改示例,统计每次分区处理的元素数量,并使用 20 个不同种子运行同一数组。验收条件是输出每次统计值、计算平均值,并保证每次排序结果正确。
  2. 设计一个重复执行的蒙特卡洛判定流程。已知单次错误概率不超过 1/41/4 且各轮独立。验收条件是写出执行 rr 轮后的错误概率上界,并说明如何根据目标错误率选择 rr。

本课总结

  • 拉斯维加斯算法保证结果正确,随机性影响运行时间;蒙特卡洛算法允许可控错误概率。
  • 随机快速排序的最坏时间仍为 O(n2)O(n^2),期望时间为 O(nlog⁡n)O(n \log n)。
  • 固定种子适合复现实验,不应被误当作安全随机机制或完整性能结论。

下一课预告

下一阶段将继续学习在精确求解代价过高时,如何用近似算法给出可证明的质量保证,并在运行时间与解的精度之间建立可解释的权衡。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

随机化算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通