企业官网建设流程全解析

简介：《算法设计》课程英文课件第11章聚焦随机化算法（Randomized Algorithms），面向已掌握基础算法、希望系统理解随机化思想与概率分析的计算机专业学生、考研学生及算法竞赛选手。课件先概述随机化算法的两类基本形态：优化问题中追求最优解且关注平均复杂度，决策问题中允许以极小概率出错。随后以经典最近点对问题为主线，展示随机选取子集、确定初始距离、划分网格、倍增网格尺寸、检查同网格点对并更新结果等完整流程，并给出平均O(n)时间复杂度的推导。同时还延伸到素数测试和Rabin-Karp模式匹配，体现随机化在不同问题下的灵活应用。资源为1个PPT文件，约494KB，英文原版幻灯片包含定义、伪代码、图示和复杂度分析，适合双语教学、课后复习和面试准备。已有163人加入学习，可作为算法设计课程第11章的配套参考资料。

1. Randomized Algorithms 不是撞运气，而是把随机性当计算资源

Randomized Algorithms 这一章在算法设计与分析课程里常被排到最后，很多人把它当成“选修中的选修”。但真实情况正好反过来：Bloom filter、跳表、随机化快速排序、通用哈希、RSA 里的素数生成，这些生产环境天天在用的东西，底层全是随机化算法。它的核心思路是把“最坏情况”从确定性算法的必然事件，压缩成概率意义上的小概率事件，用很小的失败概率或近似偏差，换确定性算法给不出的时间下界。这篇按课件一贯的叙事线走：先立理论，再给三个能直接跑通的最小实现，接着讲参数权衡，最后讨论随机数质量与去随机化验证。正在准备算法设计与分析期末编程题、或者要在系统里自己写随机组件的工程师，都能从里面拿到可复现的东西。

2. 期望分析与集中不等式：Randomized Algorithms 的两个理论支点

随机化算法的正确性证明，通常不依赖具体哪一次随机结果，而依赖两个层面：期望值和尾概率。前者回答“平均表现如何”，后者回答“偏离平均的可能性有多大”。这两件事在课件里是分开讲的，但做题和写代码时往往要一起用。

2.1 期望的线性性质：为什么平均情况那么好算

期望的线性性质说的是，对于任意随机变量 X 和 Y，即使它们完全不独立，也有 E[X+Y] = E[X] + E[Y]。这一条常常被低估，但它几乎是所有随机化算法平均复杂度分析的基础。

以随机化快排为例。把数组里的两个元素 x、y 称为“可比较对”，它们发生比较当且仅当在递归过程中，先于两者被选为主元的元素在两者之外。对任意一对元素，它们被比较的概率是 2/(它们在数组中相隔的距离+1)。利用线性期望，把所有元素对的比较概率加起来，得到总比较次数的期望是：

E[C] = Σ 2/(j - i + 1) = O(n log n)

这个推导里，元素对之间是否互相独立完全不影响结论。用线性期望把每对元素的贡献求和，一步到位。

注意区分：这里算的是“期望比较次数”，不是“以高概率完成的比较次数”。课件里通常先证期望，再补充 Boltzmann 界说“偏离期望太远的概率随偏差指数下降”，两条线叠加，才能得出“几乎总是 O(n log n)”这种更强的结论。

2.1.1 用模拟验证期望与集中不等式的关系

理论讲得再顺，不如跑一次数字直观。下面这个脚本统计掷 n 枚公平硬币时正面数偏离均值超过 0.1n 的经验频率，并把它和 Hoeffding 不等式的理论上界对比：

import random def coin_deviation_freq(n: int, trials: int = 20000) -> float: over = 0 for _ in range(trials): heads = sum(random.randint(0, 1) for _ in range(n)) if abs(heads - n / 2) > n / 10: over += 1 return over / trials for n in (50, 200, 800): freq = coin_deviation_freq(n) bound = 2 * pow(2.71828, -2 * n * 0.1 * 0.1) print(f"n={n:4d}, 经验频率={freq:.6f}, Hoeffding上界={bound:.4e}")

参数说明：参数 n 是硬币数量，trials 是模拟轮数，0.1 是允许偏离均值的比例阈值。运行后会看到，当 n 从 50 涨到 800，经验频率从约 1.6e-2 掉到 1e-6 以下，而 Hoeffding 上界始终比经验值大一个数量级左右。这个对照说明两件事：集中不等式给出的上界足够保守，可以用来设计预算；但它也偏松，工程上要留余量时，上界只作为数量级参考，不要直接拿它当实际失败概率。

2.2 集中不等式：概率离期望有多远

期望只能说明“长期来看不错”，但随机化算法的用户更关心单次运行会不会翻车。集中不等式就是回答“X 偏离 E[X] 超过 t 的概率上界”的工具。课件里最常见的三个：

实际应用时不需要记全部形式，只需要判断“随机变量之间独立吗”“有没有界”，然后选能用的最紧的那条。Hoeffding 对独立有界变量最常用，Chernoff 变体则可以处理泊松型试验和乘积型阈值。

2.3 两种算法契约：Las Vegas 与 Monte Carlo

随机化算法的正确性契约有两类，这个分类比具体算法更重要，因为它决定了你怎么设置参数、怎么测试：

• Las Vegas：结果永远正确，运行时间是随机变量。随机化快排、随机化的 Treap 查找都属此类。它不引入错误概率，代价是最坏运行时间可能爆炸，但概率极小。
• Monte Carlo：运行时间可以设定上限，结果以小概率出错。Miller–Rabin 素性检测、Bloom filter 的查询都属于此类。它们给出的是“能以至少 1−ε 的概率正确”的保证。

还有一个容易混淆的细分：Monte Carlo 算法有“单侧错误”和“双侧错误”。Miller–Rabin 把合数判成素数是假阳性，属于单侧错误；而随机化近似算法输出一个在区间内的近似值时，上下都可能超差，属于双侧错误。单侧错误可以通过重复试验快速压低失败率，双侧错误只能靠对称放大样本量，两者的参数公式不一样。

3. 三个最小实现：随机化快排、蓄水池抽样与 Miller–Rabin 素性检测

理论和参数讲得多，不如三个能直接运行的实现。这三个算法一个代表 Las Vegas、一个代表流式采样、一个代表 Monte Carlo，恰好覆盖 Random ized Algorithms 课件最常见的三个例题类型。

3.1 随机化快排：随机选主元，把最坏情况变成概率问题

import random def randomized_quicksort(arr): if len(arr) <= 1: return arr pivot = random.randrange(len(arr)) pivot_val = arr[pivot] left = [x for x in arr if x < pivot_val] mid = [x for x in arr if x == pivot_val] right = [x for x in arr if x > pivot_val] return randomized_quicksort(left) + mid + randomized_quicksort(right)

参数说明：random.randrange(len(arr)) 从当前数组范围等概率取主元下标，而不是固定取第一个或最后一个元素。固定主元最坏 O(n²)，随机主元后，任一特定输入触发最坏情况的概率最多是 2/n，且主要发生在总是抽出最小或最大元素时。代码里把等于主元的元素单独放进 mid，避免大量重复元素时递归深度失控，这是 LeetCode 版快排常被忽视的坑。

3.2 蓄水池抽样：未知长度流中的均匀抽样

import random def reservoir_sample(stream, k: int): reservoir = [] for i, item in enumerate(stream): if i < k: reservoir.append(item) else: j = random.randint(0, i) if j < k: reservoir[j] = item return reservoir

逻辑说明：前 k 个元素直接入池。从第 k+1 个元素（下标 i = k）开始，每个新元素以 k/(i+1) 的概率被纳入池子，并等概率替换掉池子里的某个旧元素。当流结束时，任意位置的元素最终留在池中的概率均为 k/n，其中 n 是流总长度。注意这里 random.randint(0, i) 两端都闭合，如果写成 random.randrange(i) 会让新元素的入选概率偏小，抽样就不是均匀的。

这个算法在课件里常被当作“在线均匀抽样”的标准答案，实际工程里对应的场景是：从日志流、传感器数据或大批量扫描结果里，在不知道总条数的前提下抽取固定大小的样本。只要不要求重置，就不需要把全量数据落盘。

3.3 Miller–Rabin 素性检测：单侧错误的 Monte Carlo

import random def is_probable_prime(n: int, rounds: int = 10) -> bool: if n < 2: return False if n % 2 == 0: return n == 2 d, s = n - 1, 0 while d % 2 == 0: d //= 2 s += 1 for _ in range(rounds): a = random.randint(2, n - 2) x = pow(a, d, n) if x in (1, n - 1): continue for _ in range(s - 1): x = x * x % n if x == n - 1: break else: return False return True

参数说明：rounds 是独立随机基底的试验次数，默认 10。先把 n−1 分解成 d·2^s 的形式，再用随机基 a 做平方探测。如果某次试验没通过平方链，直接判定合数；全部通过则返回“可能是素数”。返回 True 时，合数被误判的概率不超过 4^(−rounds)，rounds=10 时理论误判率在 1e-6 以下。

这里把 Fermat 检测和 Miller–Rabin 放在一起对比，效果最明显。用 561（卡迈克尔数）测试，Fermat 在多数基底下都会误判成素数，而 M-R 几轮就能踢出合数。所以生产环境不要只做费马小定理检测，必须用平方探测。

4. Monte Carlo 的参数权衡：轮数、采样比例与失败概率怎么定

课件里给了各种概率上界公式，但实践中最常被问的是“rounds 设多少”“样本量要多大”。这一章给出可以直接抄的参数推演方法和一组参考表。

4.1 重复试验次数怎么定：用 union bound 控制总失败率

对 Miller–Rabin，每轮独立试验的错误概率至多 1/4，重复 r 轮的错误概率是 (1/4)^r。这个乘积已经足够小，不用再做更复杂的联合概率计算。但注意，很多工程场景会把“检测失败”和“检测次数超预算”两个事件混在一起，严格的写法应该是：

P(总失败) ≤ P(第1轮坏) + P(第2轮坏 | 前一轮没坏) + … ≤ r · (1/4)^r

用 union bound 收紧后，实际所需的轮次比直觉少很多。下面这张表可以直接拿来设计参数：

表里的抽样行用了简单随机抽样的正态近似公式 n ≈ (1.96/0.05)² · p(1−p)，在 p=0.5 时样本量最大。实际做 AB 测试或流式统计时，样本量先按这个公式起步，再配合序贯检验动态调整。

4.2 用实验观察轮数和错误率的实际关系

import random def mr_error_rate(rounds: int, trials: int, composite_pool): errors = 0 for _ in range(trials): n = random.choice(composite_pool) if is_probable_prime(n, rounds): errors += 1 return errors / trials # 用前 1000 个奇合数做测试池 odd_composites = [n for n in range(9, 20000, 2) if not is_probable_prime(n, rounds=20) and n % 2 == 1] for r in (1, 3, 5, 10): print(f"rounds={r:2d}, 误判率={mr_error_rate(r, 2000, odd_composites[:1000]):.4f}")

逻辑说明：这个实验先筛出一个合数池，再统计不同轮次下把这些合数误判成素数的比例。因为测试池里故意放了很多难缠的合数，实验得到的误判率通常比理论界的 4^(−r) 还低，这符合预期，但不能反过来说理论界没用——真实输入分布未知，理论上界才是安全线。

4.2.1 轮次不是越多越好：计算预算与延迟

从表里看，失败率目标从 1e-6 降到 1e-9 只需要把轮次从 10 加到 15，计算量只增加 50%；但从 1e-9 再往下压，收益就很有限，因为此时瓶颈已经不是算法本身的错误率，而是随机数生成器的质量、系统熵源、算法实现里平方链的常数开销。生成 RSA 素数时，常规做法是每轮 Miller–Rabin 用 16 到 20 轮，配合一次确定的 Pocklington 或 Lucas 素性证明来兜底。

4.3 Las Vegas 转 Monte Carlo：给不确定的运行时间设定上限

拉斯维加斯算法的运行时间是无界的，工程上不好直接做 SLA。常见做法是给它加上“重试预算”：设一个最大尝试次数 T，超过就放弃或降级。以随机化快排为例，如果每次随机选主元都选到区间最小元素，递归深度会达到 n，但这种情况的概率是 2/n。设最大深度预算 D，当递归深度超过 D 时直接切换到堆排序，算法就从 Las Vegas 变成了一个确定时间内结束、最坏结果是排序不完全正确的 Monte Carlo 变体。切换阈值 D 取 4n 时，触发概率约为 e^(−Ω(n))，几乎没有实际影响。

这种“确定性算法兜底 + 随机化主路径”的组合，是生产系统里最常见的落地形态。课件里讲的纯随机化算法，在工程上往往要加一个 fallback 分支才敢上线。

5. 随机数质量与可复现性：种子管理、并行流与抽样偏差陷阱

随机化算法的正确性建立在“输入概率分布正确”的前提上。如果随机数生成器不合格，或者使用姿势不对，再好的算法也会悄悄产生偏差。课件一般只讲“假设有真随机源”，但实际工程里的坑都在这一层。

5.1 常用伪随机生成器的选型：从 MT19937 到 PCG

Python 的 random 模块默认用梅森旋转（MT19937），它统计性质好，但状态大、启动慢，且在并行场景下容易出现相关性。C 库里的 rand() 往往是 LCG，低位周期很短，直接取模会产生明显偏差。现代替代品是 PCG 系列和基于 ChaCha20 的 CSPRNG。

非密码学场景（随机化快排、蓄水池抽样、蒙特卡洛模拟）用 PCG 或 MT 都行；涉及安全、抽奖、密钥生成时必须用密码学安全生成器。一个常见误区是把 random.seed(time.time()) 当成“增加随机性”，多进程同时启动时会拿到几乎相同的时间戳，生成高度相关的随机序列，实际效果比固定种子还差。

5.2 取模偏差：经典有偏抽样 bug

把均匀整数映射到 m 个桶时，直接取模是错误做法。假设随机数源产生 [0, 2^31) 的均匀整数，直接 x % 6 会让 0 和 1 这两个桶分别多获得约 1/32768 的概率增量。单独一次抽样感知不到，但像蓄水池抽样、随机洗牌这类执行千万次的算法，偏差会被放大到肉眼可辨。

import random def sample_with_modulus(rng_high: int, modulus: int) -> int: limit = (1 << 31) - (1 << 31) % modulus while True: x = rng_high() if x < limit: return x % modulus

参数说明：limit 是小于 2^31 的最大模数整数倍。当生成的 x 落在 [limit, 2^31) 区间时，直接丢弃并重新采样，称为拒绝采样。这样每个桶接收到的取值数量严格相等，概率完全均匀。Python 的 random.randrange 内部就实现了这一套，所以业务代码尽量不要自己写取模逻辑，直接交给标准库即可。

5.3 并行环境下的随机流隔离

多进程并行跑蒙特卡洛模拟时，最忌讳共享一个随机数生成器或在每个进程里用相同种子初始化。前者会造成进程间锁竞争和序列相关性，后者会让所有进程产出完全相同的结果，浪费整机算力。

常见做法是按进程或者按任务划分独立随机流。NumPy 1.17 之后的推荐姿势是用 SeedSequence.spawn 生成互不相关且可复现的子种子：

import numpy as np from numpy.random import SeedSequence, default_rng ss = SeedSequence(20240601) children = ss.spawn(8) rngs = [default_rng(c) for c in children]

简单说明：SeedSequence.spawn 不是简单地“种子加一”，而是通过对父种子做哈希派生，确保子序列之间统计独立且互不重叠。同一组子种子在任意机器上可复现同一序列，这对调试和回归测试非常关键。

5.4 洗牌算法的偏差来源

随机洗牌如果用排序法，即给每个元素生成随机 key 再排序，在 key 冲突时会引入由排序稳定性和冲突解决策略决定的偏差。标准做法是 Fisher–Yates 洗牌：从后往前遍历，每次把当前元素与前面随机位置交换。Python 的 random.shuffle 已经实现 Fisher–Yates，不需要自己写。如果必须自定义，注意交换时用 random.randrange(i + 1)，而不是 random.randrange(n)，否则会产生有偏排列。

6. 去随机化的接口设计：把随机算法变成可验证的确定性结果

随机算法的结果天然不可直接复现，这让 CI 回归测试和线上问题排查变得棘手。下面是一个既保留随机性优势、又能稳定验证的设计套路：把随机种子从算法内部提升到接口层。

6.1 固定种子 + 种子扫描的验证方法

实现上，把所有随机调用收敛到少数几个入口函数，并允许从外部注入随机源：

import random def sort_with_seed(arr, seed: int) -> list: rng = random.Random(seed) # 用 rng 代替 random 模块做内部随机决策 return randomized_quicksort(arr, rng)

测试时，先固定若干种子跑一次冒烟测试判断功能正确，再做种子扫描估计失败率：

def seed_sweep(fn, inputs, seeds=200): failures = 0 for s in range(seeds): try: fn(inputs, seed=s) except AssertionError: failures += 1 return failures / seeds

逻辑说明：因为随机种子是显式传入的，任何单次失败都可以用对应的种子精确复现。种子扫描的目的不是证明“绝无问题”，而是估计算法在这个特定输入分布上的实际失败率。如果扫描 200 个种子出现一次失败，先不要急着加轮次，先确认失败是否集中在某类输入上，再决定是修算法还是修边界条件。

6.2 去随机化的两条生产线

去随机化不是让随机算法消失，而是让“随机性的效果”可以被确定性手段逼近。常用思路有两类：

第一类是“随机采样改确定性选择”。比如 Miller–Rabin 的高精度版本可以把随机基换成一个固定的、针对目标位数验证过的基集合。对 64 位以内的整数，固定用 [2, 325, 9375, 28178, 450775, 9780504, 1795265022] 这 7 个基底就足够确定性地判断素性。第二类是“随机选择改中位数分组”。算法第四版里提到的确定性快排选主元，用三数取中法近似随机化效果，复杂度退化到最坏 O(n log n) 的概率远小于手写随机版本踩雷的概率，适合对可复现性要求极高的环境。

调试这类算法时，建议先跑一遍固定种子的单测，再针对极端输入做种子扫描，最后再上正式的失败概率验证。多跑几个种子看分布，比在一个种子上跑到天荒地老更能说明问题。

本文还有配套的精品资源，点击获取