本节对应原书 PDF 第 313–318 页（印刷 p298–p303）。定义、定理、引理、算法描述、公式及其推导逐字取自原书；解释性叙述为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。本节无插图。

本节要做什么：普通算法分析要先假设「输入服从某个分布」，这个假设往往与实际不符；随机算法把随机性放进算法自己的步骤里，于是分析不再依赖输入分布。本节给出四个随机算法，并区分两类随机策略——结果一定正确的拉斯维加斯法与允许出错的蒙特卡罗法。

随机算法又称概率算法，在计算过程中加入了随机操作. 随机操作产生随机数并根据随机数决定下一步的运算. 随机算法的运行具有某种不确定性. 对同一个输入，算法的执行可以不完全相同，运行时间可能不同，计算结果也可能不同，甚至可能得到错误的结果. 当然，只有保证犯错误的概率足够小，随机算法才有实际使用价值. 和普通算法相比，随机算法具有简单快速的优点. 随机算法已成功地运用于数据结构、计算数论、图论、计算几何、并行计算等领域. 本节介绍几个随机算法并分析它们的平均复杂度.

解读：随机算法的「随机」发生在算法内部，而不是在输入上. 因此对最坏输入它也不会退化——最坏情况被随机数「摊平」了. 这是它与普通算法平均复杂度分析最本质的区别.

13.4.1 随机快速排序算法

13.3 节分析了快速排序算法的平均时间复杂度，在那里假设输入服从均匀分布. 但是，实际面对的数据不一定服从均匀分布，在这种情况下平均复杂度失去了意义. 事实上快速排序算法有时表现得很好，有时令人很不满意. 普通算法平均复杂度分析的最大问题是很难确定输入的实际分布，通常只能人为地假设. 这种假设基本上是理想的情况，往往与实际情况相差甚远. 随机算法的分析与此不同，是相对于自身的随机操作而言的，与输入服从的分布无关，不需要假设输入服从什么分布. 随机快速排序算法与快速排序算法的唯一区别是随机地选取轴值. 算法描述如下.

算法 13.10 随机快速排序算法.

Random QuickSort(A)

  1. 设 n = |A|，if n = 1 then return A
  2. 产生一个 \{1, 2, \cdots, n\} 上均匀随机数 k
  3. 令 y \leftarrow A[k]，以 y 作轴值将 A 划分为 A_1 和 A_2
  4. Random QuickSort(A_1)
  5. Random QuickSort(A_2)
  6. 按下述顺序排列 A 的元素：A_1, y, A_2

考虑算法 13.10 的平均计算时间 T_n. 记 a_i 为 A 中秩为 i 的元素，即从小到大排列的第 i 个元素. 令

X_{ij} = \begin{cases} 1 & \text{若比较 } a_i \text{ 与 } a_j \\ 0 & \text{否则} \end{cases}
P\{\ X_{ij} = 1\ \} = p_{ij} \qquad 1 \leqslant i < j \leqslant n

于是，平均比较次数为

E\left( \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij} \right) = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}p_{ij}

比较 a_i 和 a_j（i < j）当且仅当在 \{a_i, a_{i+1}, \cdots, a_j\} 中第一次取轴值时恰好取到 a_i 或 a_j，在此之前 a_i, a_{i+1}, \cdots, a_j 一直被分在同一组内. 设在 \{a_i, a_{i+1}, \cdots, a_j\} 中第一次取轴值时，它们所在的组内有 m 个数，m \geqslant j - i + 1. 记 B 为对该组选取的轴值属于 \{a_i, a_{i+1}, \cdots, a_j\}，D 为轴值恰好是 a_i 或 a_j，因此，

p_{ij} = P\{\ D \mid B\ \} = \dfrac{2}{m}\Big/ \dfrac{j - i + 1}{m} = \dfrac{2}{j - i + 1}

于是，

\begin{aligned} \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}p_{ij} &= \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\dfrac{2}{j - i + 1} \\ &= 2\sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\dfrac{1}{k} \\ &\leqslant 2nH_n \end{aligned}

其中 H_n = 1 + \dfrac{1}{2} + \cdots + \dfrac{1}{n} 是第 n 个调和数，而 H_n = O(\log n)，得证

T_n = O(n\log n)

解读：这里的期望是对算法自己抛的随机数取的，而不是对输入取的平均——这正是随机算法分析比普通平均复杂度分析更可靠的原因. 关键一步是 p_{ij} = \dfrac{2}{j-i+1}：在 \{a_i,\cdots,a_j\} 这一批元素里，只要轴值落到 a_i 或 a_j 上，二者才会被比较一次；落到中间任何一个上，它们就被分到不同组、从此再也不会比较.

13.4.2 多项式恒零测试

问题：任给一个 n 元多项式 p(x_1, x_2, \cdots, x_n)，问 p(x_1, x_2, \cdots, x_n) 是否恒为零？

当很容易把 p 整理成标准的 x_1, x_2, \cdots, x_n 的幂的乘积（项）的线性组合时，问题很简单. 但是，p 可能以某种复杂的方式给出，如用行列式给出，行列式的元素中含有变量，计算这样的行列式需要采用符号演算.

任取 n 个数 a_1, a_2, \cdots, a_n，如果 p(x_1, x_2, \cdots, x_n) \equiv 0，则必有 p(a_1, a_2, \cdots, a_n) = 0. 但是，当 p(x_1, x_2, \cdots, x_n) \not\equiv 0 时，不一定有 p(a_1, a_2, \cdots, a_n) \not= 0. 换一种说法，如果 p(a_1, a_2, \cdots, a_n) \not= 0，则可以断言 p(x_1, x_2, \cdots, x_n) \not\equiv 0. 但是，如果 p(a_1, a_2, \cdots, a_n) = 0，尚不能断言 p(x_1, x_2, \cdots, x_n) \equiv 0. 下述引理给出当 p(x_1, x_2, \cdots, x_n) \not\equiv 0 时，p(a_1, a_2, \cdots, a_n) = 0 的概率.

引理 13.1 设 p(x_1, x_2, \cdots, x_n) 是域 F 上的 n 元 d 次多项式，S 是 F 的一个有穷子集. 随机变量 a_1, a_2, \cdots, a_n 相互独立且都服从 S 上的均匀分布，则

P\{\ p(a_1, a_2, \cdots, a_n) = 0 \mid p \not\equiv 0\ \} \leqslant \dfrac{d}{|S|}

证明 对 n 作归纳证明. 当 n = 1 时，一元 d 次多项式至多有 d 个不同的根，故

P\{\ p(a_1) = 0 \mid p \not\equiv 0\ \} \leqslant \dfrac{d}{|S|}

结论成立.

假设当 n - 1 时结论成立，设 p(x_1, x_2, \cdots, x_n) \not\equiv 0，则

p(x_1, x_2, \cdots, x_n) = \sum_{i=0}^{k}x_1^i q_i(x_2, \cdots, x_n)

其中 0 \leqslant k \leqslant d，q_k(x_2, \cdots, x_n) \not\equiv 0，其次数 \leqslant d - k. 记

p_1(x_1) = \sum_{i=0}^{k}x_1^i q_i(a_2, \cdots, a_n)

于是，

\begin{aligned} & P\{\ p(a_1, a_2, \cdots, a_n) = 0 \mid p \not\equiv 0\ \} \\ =\ & P\{\ q_k(a_2, \cdots, a_n) = 0 \mid q_k \not\equiv 0\ \} P\{\ p_1(a_1) = 0 \mid q_k(a_2, \cdots, a_n) = 0, q_k \not\equiv 0\ \} \\ & + P\{\ q_k(a_2, \cdots, a_n) \not= 0 \mid q_k \not\equiv 0\ \} P\{\ p_1(a_1) = 0 \mid q_k(a_2, \cdots, a_n) \not= 0, q_k \not\equiv 0\ \} \\ \leqslant\ & P\{\ q_k(a_2, \cdots, a_n) = 0 \mid q_k \not\equiv 0\ \} + P\{\ p_1(a_1) = 0 \mid q_k(a_2, \cdots, a_n) \not= 0\ \} \\ \leqslant\ & \dfrac{d - k}{|S|} + \dfrac{k}{|S|} = \dfrac{d}{|S|} \end{aligned}

得证结论对 n 也成立.

算法 13.11 多项式恒零测试随机算法.

Poly(p)

p 是一个 n 元 d 次多项式

  1. 产生 n 个相互独立的服从 \{0, 1, \cdots, 2d - 1\} 上均匀分布的随机数 a_1, a_2, \cdots, a_n
  2. if p(a_1, a_2, \cdots, a_n) \not= 0 then return「p \not\equiv 0」
  3. else return「p \equiv 0」

当 p \equiv 0 时，算法 13.11 必返回「p \equiv 0」，结论正确；当 p \not\equiv 0 时，算法 13.10 可能返回「p \not\equiv 0」，也可能返回「p \equiv 0」. 由引理 13.1，返回「p \equiv 0」的概率不超过 \dfrac{1}{2}，也就是说，算法 13.11 犯错误的概率不超过 \dfrac{1}{2}.

显然，\dfrac{1}{2} 的错误概率太大，不能实际使用. 通过重复执行，可以把错误概率降低到任意的小. 做法如算法 13.12.

算法 13.12 改进的多项式恒零测试随机算法.

Repeated Poly(p, k)

p 是一个 n 元 d 次多项式，k 是一个正整数

  1. for i \leftarrow 1 to k do
  2. \quad if Poly(p) =「p \not\equiv 0」then return「p \not\equiv 0」
  3. return「p \equiv 0」

当 p \equiv 0 时，算法 13.12 必返回「p \equiv 0」，结论正确；当 p \not\equiv 0 时，只有当 k 次调用 Poly(p) 都返回「p \equiv 0」，算法 13.12 才返回「p \equiv 0」. 也就是说，只有当 Poly k 次调用都犯错误，算法 13.12 才给出错误结论. 而 Poly 每次调用的错误概率不超过 \dfrac{1}{2}，k 次都犯错误的概率不超过 2^{-k}. 因此，当 p \not\equiv 0 时，算法 13.12 犯错误的概率不超过 2^{-k}.

只要取足够大的 k，比如 k = 100，算法 13.12 的错误概率在实际使用时是可以忽略不计的. 事实上，硬件和系统软件的故障率就可能要高于这个错误概率. 在实际使用时，通常取 k = 10 就够了，此时的错误概率小于 0.001. 总之，算法 13.12 是有实用价值的，是有效可行的. 这种通过重复运行来降低错误概率的做法是一种通用的策略，在设计随机算法时经常使用.

另外，算法 13.11 和算法 13.12 是单侧错误的，当 p \equiv 0 时错误概率为 0.

解读：这里的随机数只取 \{0, 1, \cdots, 2d-1\} 这 2d 个值，于是 \dfrac{d}{|S|} = \dfrac{d}{2d} = \dfrac{1}{2}——取值集合的大小恰好是多项式次数的两倍，正是为了让单次错误概率压到 \dfrac{1}{2}，重复 k 次后得到 2^{-k}.

13.4.3 素数测试

素数测试在密码学中有着重要的应用. M. Agrawal，N. Kayal 和 N. Saxena 于 2002 年给出时间复杂度为 O(\log^7 n) 的素数测试算法，其中 n 是待测试的数，从而证明这是一个 P 问题. 本小节介绍一个随机的素数测试算法.

算法的出发点基于费马小定理（定理 11.13）. 设 n > 1，任给 1 \leqslant a \leqslant n - 1，如果 a^{n-1} \not\equiv 1 \pmod n，可以断言 n 是合数. 把这样的 a 称作 n 的合数见证. 但是，当 n 是合数时，不一定有 a^{n-1} \not\equiv 1 \pmod n，或者说，当 a^{n-1} \equiv 1 \pmod n 时，n 不一定是素数. 例如，8^{10} \equiv (-1)^{10} \equiv 1 \pmod 9，而 9 是合数. 事实上，当 n 是合数时，如果 a 与 n 不互素，则必有 a^{n-1} \not\equiv 1 \pmod n. 但是，在 1 \sim n - 1 之间与 n 不互素的数所占比例可能太小. 例如，当 n = p^2，p 是素数时，在 1 \sim p^2 - 1 中与 p^2 不互素的数是 p, 2p, \cdots, (p - 1)p，共 p - 1 个，所占比例为 \dfrac{p - 1}{p^2 - 1} = \dfrac{1}{p + 1}. 当 p 很大时（有任意大的素数），这个比例很小. 因此，必须在与 n 互素的数中寻找更多的合数见证. 但是，存在这样的合数 c，对所有与它互素的 a，都有 a^{c-1} \equiv 1 \pmod c. 这样的数称作卡米切尔（Carmichael）数. 已知有无穷多个卡米切尔数，前 5 个是

\begin{aligned} 561 &= 3 \times 11 \times 17 \\ 1105 &= 5 \times 13 \times 17 \\ 1729 &= 7 \times 13 \times 19 \\ 2465 &= 5 \times 17 \times 29 \\ 2821 &= 7 \times 13 \times 31 \end{aligned}

不过卡米切尔数相对很稀少，例如在小于一亿的数中只有 255 个卡米切尔数. 下述引理提供了新的合数见证.

引理 13.2 设 p 是素数，1 \leqslant a \leqslant n - 1. 如果 a^{2k} \equiv 1 \pmod p，则 a^k \equiv 1 \pmod p 或 a^k \equiv -1 \pmod p.

证明 由 a^{2k} \equiv 1 \pmod p，存在整数 d 使得

a^{2k} = dp + 1

即

(a^k + 1)(a^k - 1) = dp

由于 p 是素数，必有 p \mid a^k - 1 或 p \mid a^k + 1，得证 a^k \equiv 1 \pmod p 或 a^k \equiv -1 \pmod p.

设 p 是素数，p - 1 = 2^s t，其中 s 是奇数. 根据引理 13.2，对任意的 1 \leqslant a \leqslant p - 1，如果 a^{2^s t} \bmod p，a^{2^{s-1} t} \bmod p，\cdots，a^t \bmod p 不全为 1，则第一个不等于 1 的数是 p - 1（x \bmod p = p - 1 等同于 x \equiv -1 \pmod p）. 于是，得到一类新的合数见证. 设 n 是奇数，n - 1 = 2^s t，1 \leqslant a \leqslant n - 1，其中 s 是奇数. 如果存在 0 \leqslant k < t，使得 a^{2^k t} \bmod n = 1，k + 1 \leqslant i \leqslant t 且 a^{2^i t} \bmod n \not= n - 1，则 n 是合数.

算法 13.13 素数测试.

Primality(n)

  1. if n 是偶数 \wedge n \not= 2 then return 合数
  2. if n = 2 then return 素数
  3. if n = 1 then return n = 1
  4. 计算 t 和 s 使得 n - 1 = 2^s t，其中 s 是奇数
  5. 产生一个 \{1, 2, \cdots, n - 1\} 上的均匀随机数 a
  6. for i = 0 to t do
  7. \quad 计算 b_i \leftarrow a^{2^i} \bmod n
  8. if b_t \not= 1 then return 合数
  9. if b_0 = 1 then return 素数
  10. j \leftarrow \max\{\ i \mid b_i \not= 1\ \}
  11. if b_j = n - 1 then return 素数
  12. else return 合数

算法 13.13 也是单侧错误的. 当 n 是素数时，必返回素数. 但是，当 n 是合数时，算法不一定返回合数. 可以证明，当 n 是合数时算法返回素数的概率，即错误概率不超过 \dfrac{1}{2}. （有兴趣的读者可参阅 R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995）类似算法 13.12，重复独立地运行 k 次算法 13.13，只要有一次返回合数就认为 n 是合数；只有 k 次都返回素数，才认为 n 是素数. 这样做可以把错误概率降低到 2^{-k}.

解读：费马小定理只给出「a^{n-1} \not\equiv 1 ⟹ 合数」这一个方向的判据，而卡米切尔数把所有与它互素的 a 都骗过去，所以单靠费马测试无法排除它们. 算法 13.13 换用引理 13.2：沿 a^{p-1} 的平方根链往回找，除了 1 之外只允许出现 -1；卡米切尔数在这条链上会露馅. 这就是 Miller–Rabin 测试的思路.

13.4.4 蒙特卡罗法和拉斯维加斯法

随机快速排序算法和多项式恒零测试（以及素数测试）的随机算法是两种不同类型的随机算法，随机快速排序算法的计算结果总是正确的，而多项式恒零测试随机算法可能给出错误的结果. 前者称作拉斯维加斯（Las Vegas）算法，后者称作蒙特卡罗（Monte Carlo）算法.

一般地，拉斯维加斯算法的结论总是正确的，但允许不作结论或拒绝回答. 而蒙特卡罗算法可能给出错误的结论. 蒙特卡罗算法又分两种，一种是单侧错误的，如多项式恒零测试和素数测试的随机算法. 另一种是双侧错误的，既可能把是说成非，也可能把非说成是.

前面已经看到，当单侧错误的蒙特卡罗算法的错误概率不超过 \dfrac{1}{2} 时（实际上，只要不超过一个小于 1 的常数），通过重复独立地运行可以把错误概率降低到任意的小且保持算法仍是多项式时间的. 这样的随机算法在实际中完全可以放心使用. 同样地，当拉斯维加斯算法不作结论的概率不超过一个小于 1 的常数时，也能通过重复独立地运行不作结论的概率降低到任意的小. 双侧错误的蒙特卡罗算法也有类似的性质，只是具体做法要复杂一点.

解读：一句话区分两类算法——拉斯维加斯法「要么对、要么不答」，蒙特卡罗法「一定答、但可能答错」. 判断一个随机算法属于哪一类，只看它在随机数不走运时是「拒绝回答」还是「给出错误答案」.