算法设计与分析课程-第8讲-概率算法

概率算法 —— 算法设计与分析课程第 8 讲

课程：北京大学 屈婉玲 《算法设计与分析》0A002 讲次：第 8 讲 主题：概率算法（随机算法） 页数：56 页（PDF 共 ~49 页内容，含 7 大经典实例）

---

一、伪随机数

1. 概念

• 真正的随机数：物理过程产生，不可预测
• 伪随机数：按某种数学规则生成，在统计意义上模拟随机数
• 均匀分布：随机变量 X 在 (0,1) 上均匀分布，即对任意 0<a<1，P{0<X≤a}=a

2. 线性同余法

最经典的伪随机数生成算法：

a₀ = d                        （种子）
aₙ = (b·aₙ₋₁ + c) mod m       （n = 1,2,...）

参数：

• 模数 m：机器最大数（通常 2³¹-1）
• 乘数 b：2 ≤ b < m
• 常数 c：0 ≤ c < m
• 种子 d：0 ≤ d < m，由计算时随机给出

3. 乘同余法

c = 0 的特殊情况：

a₀ = d
aₙ = b·aₙ₋₁ mod m

经典参数：m = 2³¹-1，b = 7⁵ = 16807，d ≠ 0

实例（d=1）：16807, 282475249, 1622650073, …

4. 离散型伪随机数

从集合 P = {aᵢ, aᵢ₊₁, …, aⱼ} 中按等概率选一个：

算法 Random(i, j)

1. 产生伪随机数 x（乘同余法）
2. n ← j - i + 1
3. 对 k = 1..n，若 x/m ≤ k/n 则返回 a_{i+k-1}

本质：将 [0,1) 区间均匀分成 n 段，根据 x 落在第几段选元素。

---

二、随机算法概述

1. 确定型 vs 随机算法

维度	确定型算法	随机算法
对同一输入的每次运行	过程可重复，结果一样	过程随机，结果也可能随机
时间/空间	固定	期望时间度量
设计难度	可能很复杂	往往更简单

2. 随机算法的优势

• 运行时间或空间需求往往优于确定型算法
• 算法设计更简单
• 对很多问题，随机算法是目前已知最好的算法

3. 复杂性度量

• 随机算法 A 对规模为 n 的实例 I，每次运行时间可能不同
• 期望时间：反复求解实例 I 的平均时间
• 许多随机算法对规模 n 的不同实例，运行时间期望都一样，因此该期望代表平均预期时间

---

三、Sherwood 算法

核心思想：找到确定性算法的最坏情况实例，通过随机选择使最坏情况的发生概率极低，从而改善最坏情况的预期复杂性。

特点

• ✅ 一定能得到正确的解
• ✅ 算法比确定型算法简单
• ✅ 平均性能与确定型算法一样
• ✅ 改善了最坏情况的预期复杂性
• ✅ 运行时间基本与输入实例无关

实现途径

1. 将确定型选择原则改为随机选择
2. 在确定型算法前增加随机洗牌步骤

例 1：随机快速排序 RandQuicksort

确定型快排问题：最坏情况（已排序数组）O(n²)，平均 O(n log n)

随机化改进：每次随机选一个元素作为轴值

RandQuicksort(A, p, r):
    if p < r:
        q ← RandPartition(A, p, r)
        RandQuicksort(A, p, q-1)
        RandQuicksort(A, q+1, r)

RandPartition(A, p, r):
    i ← Random(p, r)
    A[i] ↔ A[p]
    return Partition(A, p, r)

• 预期时间：O(n log n)
• 最坏情况概率非常小，实际应用中可忽略

例 2：随机选择算法 RandSelect

从 A[p..r] 中选第 k 小的元素：

RandSelect(A, p, r, k):
    if p = r: return A[p]
    i ← Random(p, r)
    以 A[i] 为标准划分
    j ← 划分后≤A[i]的元素个数
    if k ≤ j:
        return RandSelect(A, p, p+j-1, k)
    else:
        return RandSelect(A, p+j, r, k-j)

时间期望分析：

假设每个数被选概率相等，且第 k 个数总是出现在较大的数组（最坏上界）：

T(n) ≤ (2/n)·∑_{i=n/2}^{n-1} T(i) + O(n)

用数学归纳法可证 T(n) ≤ cn，即预期时间 O(n)

与拟中位数选择算法对比：

算法	最坏情况	平均情况
拟中位数选择（确定型）	O(n)	O(n)
随机选择	O(n²)	O(n) 预期

随机选择的最坏情况（每次恰好选到边界）概率很小，可以忽略；且与具体实例无关，只与随机选择有关。

预期复杂度的一般结论

设 A 为确定型算法，B 为对应的 Sherwood 算法：

• A 的平均时间：t_A(n) = (1/|Xₙ|)·∑t_A(x)
• B 在实例 x 的预期时间：t_B(x) = t_A(n) + s(n)
• B 的平均复杂性：t_B(n) = t_A(n) + s(n)

即 Sherwood 算法的运行时间对所有实例都”拉平”到平均水平，消除了最坏实例。

随机洗牌算法

RandomShuffle(A, n):
    for i ← 1 to n-1:
        j ← Random(i, n)
        A[i] ↔ A[j]

原理：遍历每个位置，随机选一个后面的元素交换。确保所有 n! 种排列等概率出现。

---

四、Las Vegas 算法

核心思想：一次运行可能找不到解，但找到的解一定正确。反复运行直到找到解为止。

特点

• ❌ 一次运行可能得不到解
• ✅ 得到的解一定是正确的
• ✅ 改进确定型算法的平均情况下复杂度
• 🔧 改进途径：与确定型算法相结合

例 3：n 后问题的 Las Vegas 算法

基本算法 BoolQueen(n)：

• 逐行放皇后，每行在所有相容列中随机选一列
• 如果某行没有相容列，算法失败（返回放好的皇后数 count）
• 如果放完 n 个皇后，成功

重复调用 QueenLV(n)：

p ← BoolQueen(n)
while p < n:
    p ← BoolQueen(n)

改进：LV + 回溯混合

设 stopVegas ≤ n，表示用 LV 算法放置前 stopVegas 个皇后， 剩下 n - stopVegas 个用回溯法放置。

• stopVegas = 0：完全回溯
• stopVegas = n：完全 Las Vegas

n=12 时的统计数据：

stopVegas	成功概率 p	成功平均结点 s	失败平均结点 e	平均时间 t
0（纯回溯）	1.0000	262.00	—	262.00
5	0.5039	33.88	10.20	80.39
12（纯LV）	0.0465	13.00	—	222.11

结论：混合算法效率最高。stopVegas=5 时平均时间仅为纯回溯的 1/3。

平均时间公式：

t = p·s + (1-p)·(e + t)

解得：t = s + e·(1-p)/p

直觉：每次尝试成本是 s（成功）或 e（失败），失败了重来，期望次数 1/p。

---

五、Monte Carlo 算法

核心思想：总是给出解，但解不一定正确。通过多次运行可将出错概率降到任意小。

特点

• ✅ 一定给出解（有解）
• ❌ 解不一定正确
• 🔧 改进途径：多次执行，取多数/任何一次正确
• 📊 单次正确概率 > 1/2，k 次后错误概率 ≤ (1/2)ᵏ

Sherwood 和 Las Vegas 都保证解的正确性，Monte Carlo 不保证——但用概率换时间，能解决目前困难的问题。

例 4：主元素测试

主元素：出现次数超过一半的元素。

算法 Majority(T, n)：

1. i ← Random(1, n)
2. x ← T(i)
3. 计数 x 在 T 中出现的个数 k
4. if k > n/2: return true
5. else: return false

正确性分析：

• 回答 true → 一定正确（计数超过半数才返回 true）
• 回答 false → 可能出错（可能恰好随机选到了非主元素）
• 如果存在主元素，选到它的概率 > 1/2 → 偏真 1/2 正确

重复调用改进：

调用 k 次，只要有一次返回 true 就返回 true：

MCMajority(T, n, ε):
    k ← ⌈log(1/ε)⌉
    for i ← 1 to k:
        if Majority(T, n): return true
    return false

正确概率：

• 存在主元素时，每次回答 false 的概率 < 1/2
• k 次都回答 false 的概率 < (1/2)ᵏ
• 总正确率 > 1 - (1/2)ᵏ

调用次数 k	1	2	3	4	5	6
正确概率 >	0.5	0.75	0.875	0.938	0.969	0.985

对任意 ε > 0，取 k ≥ ⌈log(1/ε)⌉ 可使错误率 ≤ ε。

例 5：串相等测试（指纹法）

问题：A 有长串 x，B 有长串 y，比较 x = y?

方法一（直接传）：A 把 x 发给 B，B 比较。→ 通信量大。

方法二（指纹法）：

• A 用 x 导出短串 f(x)（fingerprint / 指纹）
• A 发送 f(x) 给 B
• B 比较 f(x) 与 f(y)
• f(x) ≠ f(y) → x ≠ y（一定正确）
• f(x) = f(y) → 可能出错（哈希碰撞）

指纹函数（基于模素数）：

设 I(x), I(y) 为串对应的二进制整数，随机选素数 p， Ip(x) = I(x) mod p

发送 p 和 Ip(x)，当 p 不大时，只传一个短串。

出错条件：x ≠ y 但 p | (I(x) - I(y))

出错概率估计（基于素数定理）：

• π(t)：小于 t 的素数个数 ≈ t / ln t
• 若 k < 2ⁿ，整除 k 的素数个数 < π(n)

取 M ≥ 2n²，则出错概率：

P(错误) ≤ π(n) / π(M) ≈ (n/ln n) / (2n²/ln n²) ≈ 1/n

即随机选一个素数，错误概率不超过 1/n。

重复 j 次改进：

令 j = ⌈log log n⌉，每次选不同素数，只要有一次不等就返回不等：

出错概率 ≤ (1/n)^j = 1/n^{⌈log log n⌉}

实例（n = 10⁶ 位）：

• M = 2·10¹² ≈ 2
• 素数 p 的二进制位数：约 41 位
• Ip(x) 的位数：约 41 位
• 总共只传送 82 位，而原串有 100 万位！

例 6：模式匹配的随机算法

问题：文本串 X（长 n）中找模式串 Y（长 m）的首次出现位置。

确定型算法：

• 朴素算法：O(mn)
• KMP 算法：O(m+n)

随机算法思想：

• 不直接比较每个 X(j) 与 Y
• 而是比较指纹 Ip(Y) 与 Ip(X(j))

关键递推公式（滑动窗口）：

X(j) = X[j..j+m-1] 对应的整数值 X(j+1) = 2·X(j) - 2ᵐ·xⱼ + x_{j+m}

模 p 下：

Ip(X(j+1)) = (2·Ip(X(j)) - Wp·xⱼ + x_{j+m}) mod p 其中 Wp = 2ᵐ mod p

算法 PatternMatching：

1. 随机选素数 p < M
2. 计算 Wp = 2ᵐ mod p，Ip(Y)，Ip(X(1))
3. 对 j = 1..n-m+1：
   • if Ip(X(j)) = Ip(Y): return j
   • 用递推公式算 Ip(X(j+1))
4. return 0

时间复杂度：O(m + n)（与 KMP 同阶）

出错概率：

Y ≠ X(j) 但 Ip(Y) = Ip(X(j)) 的总概率：

• 所有不匹配位置的 |I(Y) - I(X(j))| 乘积 ≤ (2ᵐ)ⁿ
• 整除它的素数 ≤ π(mn)
• 取 M = 2mn²，出错概率 < 1/n

例 7：素数测试（Miller-Rabin 算法）

预备：快速幂

求 x 的 m 次幂（二分法）：

Exp(x, m):  // m = b_kb_{k-1}...b_0
    y ← 1
    for j ← k downto 0:
        y ← y²
        if b_j = 1: y ← x·y
    return y

时间：O(log m) 次乘法

模 n 的 m 次幂：

ExpMod(a, m, n):
    c ← 1
    for j ← k downto 0:
        c ← c² mod n
        if b_j = 1: c ← a·c mod n
    return c

按位乘算：T(n) = O(log³ n)

Fermat 小定理

如果 n 为素数，则对所有正整数 a ≠ 0 (mod n)，有 a^{n-1} ≡ 1 (mod n)

朴素素数测试 Ptest1(n)：

• 测试 2^{n-1} ≡ 1 (mod n)，是则返回素数
• 问题：基 2 的伪素数（如 341）会误判

改进 Ptest2(n)：

• 随机选 a ∈ [2, n-2] 测试
• 合数但不是 Carmichael 数时，错误概率至少 1/2
• 无法解决 Carmichael 数问题（如 561, 1105, 1729）

Miller-Rabin 算法

基于另一个素数必要条件：

定理：如果 n 为素数，则方程 x² ≡ 1 (mod n) 的根只有两个：x = 1 和 x = -1（即 x = n-1）。 如果存在非平凡的根（既不是 1 也不是 n-1），则 n 为合数。

核心思路：

• 设 n-1 = 2^q · m（m 为奇数）
• 计算序列：a^m, a^{2m}, a^{4m}, …, a^{2^q m} = a
• 如果后项为 1 但前项不是 ±1 → 存在非平凡根 → 合数

算法 Witness(n)：

1. findq-m(n)：找 q, m 使得 n-1 = 2
2. test(n, q, m)：
   • a ← Random(2, n-1)
   • x₀ = a^m mod n
   • 对 i = 1..q:
     • xᵢ = xᵢ₋₁² mod n
     • if xᵢ = 1 且 xᵢ₋₁ ≠ 1 且 xᵢ₋₁ ≠ n-1 → composite
   • if x_q ≠ 1 → composite
   • return prime

单次出错概率 ≤ 1/2。

Miller-Rabin 算法：

• 重复 k = ⌈log n⌉ 次测试
• 出错概率 ≤ 2^{-k} ≤ 1/n
• 时间：O(log⁴ n)（按位乘统计）

换句话说：n 是素数时一定返回素数；n 是合数时以 1-1/n 的概率正确判定。

---

六、三类随机算法对比总结

维度	Sherwood	Las Vegas	Monte Carlo
一定有解	✅ 是	❌ 不一定	✅ 是
解一定正确	✅ 是	✅ 是	❌ 不一定
改进方向	最坏情况的预期复杂性	平均情况复杂性	解决困难问题
设计要点	随机选择	与确定算法结合	概率 > 1/2，多次执行
典型例子	随机快排、随机选择	n后问题混合算法	主元素、串相等、模式匹配、素数测试

---

七、关键知识点提炼

1. 伪随机数：线性同余法是基础，乘同余法（16807 / 2³¹-1）是经典实现
2. Sherwood = 随机选择 + 确定性算法：消除最坏实例，拉平到平均性能
3. Las Vegas = 随机尝试 + 失败重试：解一定对，但可能要试多次
4. Monte Carlo = 概率正确 + 多次放大置信度：用错误率换时间，k 次运行错误率从 1/2 降到 2
5. 指纹/哈希 + 随机素数：串相等、模式匹配等问题的标准随机化技术，核心是基于素数定理控制碰撞概率
6. Miller-Rabin：目前最实用的概率素数测试算法，基于 Fermat 小定理 + 非平凡平方根检测
7. n后问题混合策略：随机放前几个 + 回溯放后几个，效果远好于纯回溯或纯随机

---

相关链接

• 第1讲 算法基础
• 第2讲 数学基础
• 第3讲 分治策略
• 第4-5讲 动态规划
• 第6讲 贪心法
• 第7讲 回溯法
• 《算法导论》CLRS（更深入的随机算法分析）