11 · 随机算法

← 返回课程目录
本文目录

本文最后更新于 2026年11月5日 晚上

北京大学信息科学技术学院
算法设计与分析(2026春)的课程笔记

第十一章:随机算法

在经历了复杂度下限分析、NP完全、近似算法等一系列抽象内容的洗礼后,我们终于苦尽甘来,熬到了比较简单的一章:随机算法

Las Vegas型随机算法

随机快排

顾名思义,就是在选择pivot时随机选择一个元素,而不是每次固定选择某一个元素,然后递归的方式和普通快排相同

随机选取pivot,其位于排序后第ii个位置(i=0,1,...,n−1i=0,1,...,n-1)的概率为1n\dfrac{1}{n},故
T(n)=n−1+1n(Σi=0n−1 T(i)+T(n−i−1))=n−1+2nΣi=1n−1T(i)T(n)=n-1+\dfrac{1}{n}(\Sigma_{i=0}^{n-1} \ T(i)+T(n-i-1))=n-1+\dfrac{2}{n}\Sigma_{i=1}^{n-1}T(i)
我们归纳证明T(n)≤2nlnnT(n) \le 2n ln n
n=1n=1时显然,假设对于1,2,...n−11,2,...n-1时都成立,则nn时
T(n)≤n−1+2nΣi=1n−12ilni≤n−1+2n∫1n2xlnx dxT(n)\le n-1+\dfrac{2}{n}\Sigma_{i=1}^{n-1}2ilni\le n-1+\dfrac{2}{n} \int_1^{n} 2xlnx \ dx
≤n−1+2nlnn−n+1n≤2nlnn\le n-1+2n lnn-n+\dfrac{1}{n} \le 2nlnn
所以上界可以从Θ(nlogn)\Theta(n logn)精确到2nlnn2nlnn

随机选择

从数组AA的pp到rr下标选第kk小的数
if p=rp=r return;
否则在p,rp,r之中随机选出下标ii,假设有jj个数小于等于A[i]A[i]
若k≤jk\le j,就从pp到p+j−1p+j-1下标选第kk小的数
否则就从p+jp+j到rr下标选第k−jk-j小的数
递归调用即可

假设1,2,...n1,2,...n中每个数被选到概率相同,且第kk个数总是出现在被划分后两个数组中较大者,则
T(n)≤2nΣi=n2n−1T(i)+O(n)T(n)\le \dfrac{2}{n}\Sigma_{i=\dfrac{n}{2}}^{n-1}T(i)+O(n)
类似地我们可归纳证明T(n)≤cnT(n) \le cn

n皇后随机放置

对于每一行,先筛选出所有合法位置,再随机选一个位置放置皇后
改进:与回溯相结合
stopVegasstopVegas个用随机放,剩下n−stopVegasn-stopVegas仍用经典的回溯

对于不同的$ stopVegas 值,设值,设 p 为算法成功概率为算法成功概率 s 为一次成功搜索访问的结点数的平均值为一次成功搜索访问的结点数的平均值 e 为一次不成功搜索访问的结点数的平均值为一次不成功搜索访问的结点数的平均值 t 为算法找到一个解的平均时间则为算法找到一个解的平均时间 则t=ps+(1-p)(e+t) \rightarrow t=s+e\dfrac{1-p}{p}$

Monte Calo型随机随机算法

主元素测试

我们将出现次数超过一半以上的元素称为主元素
输入nn个元素的数组TT,判断其是否存在主元素
我们定义算法M(T,n)M(T,n)

  • 在1,2,...n1,2,...n中随机选取下标ii,x=T[i]x=T[i]
  • 统计xx在TT中出现次数,若>n2> \dfrac{n}{2} return true,否则return false

显然这个算法是不准确的,如果回答true那倒好,说明确实有主元素,但如果回答false,难以断言就一定没有主元素
我们调用时,如果回答true就结束,回答false就再调用
那么调用kk次正确的概率为
p+(1−p)p+...+(1−p)k−1p=1−(1−p)kp+(1-p)p+...+(1-p)^{k-1}p=1-(1-p)^{k}
由于当回答true时,数组里至少n2\dfrac{n}{2}个元素都是xx,所以选中xx的概率p>12p> \dfrac{1}{2}
因此1−(1−p)k>1−2−k1-(1-p)^{k} > 1-2^{-k}

改进:对于任意给定ϵ>0\epsilon>0,要使出错概率不超过ϵ\epsilon
则2−k≤ϵ2^{-k} \le \epsilon
两边取以2为底的对数,有
−k≤logϵ-k \le log \epsilon
k≥−logϵk \ge -log \epsilon
故k≥⌈log1ϵ⌉k \ge \lceil log\dfrac{1}{\epsilon} \rceil
我们取k=⌈log1ϵ⌉k=\lceil log\dfrac{1}{\epsilon} \rceil,调用kk次算法,即可保证出错概率不超过ϵ\epsilon

串相等测试

AA有一个长串xx,BB也有一个长串yy,A,BA,B两人希望知道x,yx,y是否相等
那你说,这不简单吗,直接让AA把xx发给BB,BB进行一个比较就好,然而由于串过长,发送时占用资源过多,A,BA,B希望你找到更好的办法
于是你打算让AA对xx采用ff操作,导出一个f(x)f(x)发给BB,BB也用相同操作导出f(y)f(y),若f(x)≠f(y)f(x) \neq f(y)即可断言x≠yx \neq y,但是当f(x)=f(y)f(x)=f(y)时依然无法断言x=yx=y

我们假设x,yx,y二进制表示分别为I(x),I(y)I(x),I(y)
令Ip(x)=I(x) mod pI_p(x)= I(x ) \ mod \ p
AA将素数pp和Ip(x)I_p(x)传给BB,当pp不太大时,传的就是短串
问题还是如上面所说,而且这里还有新问题,what if p∣(I(x)−I(y))p | (I(x)-I(y))?
我们选择随机选择素数pp进行测试
出错的必要条件:x,yx,y位数相同,p∣(I(x)−I(y))p | (I(x)-I(y))

下面我们介绍关于素数的一些性质
函数π(t)\pi(t)定义为小于tt的不同素数个数
例如π(20)=8 (2,3,5,7,11,13,17,19)\pi(20)=8 \ (2,3,5,7,11,13,17,19)
于是我们有素数定理:π(t)≈tlnt\pi(t)\approx \dfrac{t}{lnt}
如果k<2nk<2^n,nn不太小,则整除kk的不同素数个数小于π(n)\pi(n)

由此,我们可以估计出错概率

我们重复执行jj次,每次都随机选择小于MM的素数
令j=⌈loglogn⌉j=\lceil loglogn \rceil,则出错概率
(1n)j≤1n⌈loglogn⌉(\dfrac{1}{n})^j \le \dfrac{1}{n^{\lceil loglogn \rceil}}

模式匹配

输入:二进制串x,yx,y,长度分别为n,mn,m,n≥mn \ge m
输入:若yy在xx中,输入yy出现的第一个位置,否则输出0
这个东西很眼熟对不对?本质上就是数算中学的字符串匹配(简化版)
不必多说,朴素匹配复杂度O(mn)O(mn),KMP算法复杂度O(m+n)O(m+n)

但是今天!我们要尝试用随机算法
设x(j)=xjxj+1...xj+m−1x(j)=x_jx_{j+1}...x_{j+m-1}
我们将x(j)x(j)和yy逐字符比较改为Ip(x(j))I_p(x(j))和Ip(y)I_p(y)的比较
由二进制性质,x(j+1)=2x(j)−2mxj+xj+mx(j+1)=2x(j)-2^mx_j+x_{j+m}
令Wp=2m(mod p)W_p=2^m(mod \ p)
则Ip(x(j+1))=(2Ip(x(j))−Wpxj+xj+m)(mod p)I_p(x(j+1))=(2I_p(x(j))-W_px_j+x_{j+m})(mod \ p)
由此公式,从Ip(x(j))I_p(x(j))计算Ip(x(j+1))I_p(x(j+1))只需要常数时间

于是我们有如下算法:
从随机选取小于MM的素数pp
然后取jj从11开始,一直循环到n−m+1n-m+1
采取上面的迭代方式,如果出现了Ip(x(j))=Ip(y)I_p(x(j))=I_p(y)就return j
否则如果循环完了还没结果就return 0

时间复杂度O(m+n)O(m+n)
出错条件和出错概率如下:

素数测试

首先我们来学习一下,如何“优雅”地求xx的mm次幂
其中xx为实数,m=dkdk−1...d1m=d_kd_{k-1}...d_1为二进制自然数

算法如下:

1
2
3
4
5
6
y=1
for j in range(k,0):
y=y*y
if d_j==1:
y=x*y
return y

接下来我们更进一步,计算a mod na \ mod \ n的mm次幂,这就是所谓的快速幂
输入a,m,na,m,n均为正整数,m≤nm \le n,m=dkdk−1...d1m=d_kd_{k-1}...d_1为二进制自然数
算法如下:

1
2
3
4
5
6
y=1
for j in range(k,0):
y=y*y%n
if b_j==1:
y=a*y%n
return y

可以看出其实就加了mod n 这一步
以位乘为基本运算,T(n)=O(klog2n)=O(log3n)T(n)=O(k log^{2} n)=O(log^{3} n)

接下来我们终于可以开始素数测试了
首先回顾一下高中学过的费马小定理:
若nn为素数,则对于所有正整数a mod n≠0a \ mod \ n \neq 0,有:
an−1≡1( mod n)a^{n-1} \equiv 1 (\ mod \ n)

于是我们有了一个粗糙算法:
计算2n−1≡1( mod n)2^{n-1} \equiv 1 (\ mod \ n),如果满足则nn为素数,否则为合数
问题在于这里只对于a=2a=2进行了测试,容易出反例,比如n=341n=341就是一个,满足上述条件且为合数,此时称nn为基2的“伪素数”

于是我们进行改进,随机选取for a in range(2,n),例如取a=3a=3就可以否定341
然而我们必须指出,费马小定理只是必要条件而非充分条件
这意味着即使所有与nn互质的正整数aa都满足定理,nn也不一定就是素数
这种nn很特殊,我们称其为Carmichael数,如 561,1105,1729,2465 等
Carmichael数非常少,小于 10810^8 的只有 255 个
由初等数论可以证明:如果n为合数,但不是Carmichael数,那么上面的算法测试n为合数的概率至少为1/2

在费马小定理之外,我们给出另一个必要条件:
如果nn为素数,则x2≡1( mod n)x^{2} \equiv 1 (\ mod \ n)的根只有两个
即x=1x=1和x=−1x=-1(mod n 意义下)
我们称不是1或-1的根为非平凡的,如果方程有非平凡的根,则nn为合数
于是我们给出测试方法:
设nn为奇素数,则n−1n-1为偶数,设n−1=2qm(q≥1)n-1=2^qm(q \ge 1)
在mod n 意义下,我们构造序列am,a2m,a4m,...,a2qma^m,a^{2m},a^{4m},...,a^{2^qm}
其中最后一项即为an−1a^{n-1},并且每一项是前面一项的平方
测试方法:

  • 随机选取a∈[2,3,...,n−1]a \in [2,3,...,n-1]进行测试
  • 对于任意i=0,1,...q−1i=0,1,...q-1 判断a2im mod na^{2^im} \ mod \ n是否为1和n-1,且它后一项是否为1
  • 如果其后项为1,但它本身不为1和n-1,则它就是非平凡根,从而知道nn不是素数

上面为一个实例,该算法被称为Miller-Rabin算法
首先找q,mq,m使得n−1=2qmn-1=2^qm,复杂度O(logn)O(log n)
然后检测序列是否存在非平凡根,复杂度O(log3n)O(log^3 n)
可证明每次测试出错概率最多1/2,重复测试kk次出错概率最多2−k2^{-k}
令k=⌈logn⌉k= \lceil logn \rceil,则2−k≤1n2^{-k} \le \dfrac{1}{n},正确率为1−1n1-\dfrac{1}{n}
换言之,若nn为素数,算法输出“素数”,若nn为合数,算分以1−1n1-\dfrac{1}{n}概率输出“合数”
由于测试需要kk次,按位乘统计,总时间复杂度O(log4n)O(log^4 n)

两种算法的对比与总结

Las Vegas型

Las Vegas型随机算法主要是修改确定性算法得到,一般把某一步确定性选择变为随机选择,可以与确定性算法相结合使用,有可能改进确定性算法的平均时间复杂度
这种算法的特点是要么得不到解,如果有解,解一定是正确的,但运行时间时短时长,本身是一个随机变量,因此我们更关心它的平均运行时间
我们把期望运行时间是输入规模的多项式 且总是给出正确答案的 随机算法称为有效的 Las Vegas型随机算法

Monte Calo型

Monte Calo型随机算法不但运行时间是随机变量,而且计算结果也是随机事件
我们把总是在多项式时间内运行 且出错概率不超过13\dfrac{1}{3}的随机算法称为有效的Monte Calo型随机算法
当然其实只要算法执行足够多次,出错概率可以变得任意小,也不需要这个13\dfrac{1}{3}

单侧错误和双侧错误

  • 弃真型单侧错误:当算法宣布接受时结果一定对,宣布拒绝时不一定对,例如主元素测试
  • 取伪型单侧错误:算法宣布拒绝时结果一定对,宣布接受时不一定对,例如素数测试
  • 双侧错误:在所有输入上同时出现上述两种不同的错误

随机算法的分类与局限性

Las Vegas型中,我们有零错误概率多项式时间算法(有效的),称为ZPP
Monte Calo型中,错误概率有界的有效算法(多项式时间)称为BPP
在此基础上,如果是弃真型单侧错误概率有界,称为RP,取伪型称为coRP
局限性在于:错误概率有界的多项式时间随机算法不太可能解决NP完全问题

处理难解问题的策略

严格来说这是第十二章的内容了,不过老师也没细讲,在此就并入十一章中,简单带过

对问题施加限制

例如SAT问题,限制成2SAT,它就是P类问题了
或者限制成HornSAT(输入限制为霍恩公式,析取式中正文字,即不带否定号的变量,至多出现一次),那么也变成了P类问题
再比如说各类图的问题,也可以限制参数如下:

固定参数算法

通常把优化问题转化为判定问题时,都会在输入中引入一个参数
例如顶点覆盖问题:给定图GG,正整数KK(小于等于GG的顶点数),问是否存在不超过KK的顶点覆盖?
我们固定常数kk,输入为(G,k)(G,k),从而穷举所有kk元顶点子集,看是否存在顶点覆盖,复杂度约为O(knk+1)=O(2kkn)O(kn^{k+1})=O(2^k kn)
所以在O(2kkn)O(2^k kn)时间内能够正确解决大小不超过kk的顶点覆盖问题

改进的指数时间算法

我们用O∗O^{\ast}表述忽略多项式因子,例如O∗(2n)=O(nO(1)2n)O^{\ast}(2^n)=O(n^{O(1)}2^n)
当一个问题,暴力算法时间O∗(2n)O^{\ast}(2^n)时,则∀1<c<2\forall 1<c<2,时间复杂度为O∗(cn)O^{\ast}(c^n)的指数时间算法称为 非平凡(改进)的指数时间算法
例如我们可证明,SAT可以在O∗(1.8393n)O^{\ast}(1.8393^n)时间内正确求解

指数时间假设:对于任意正整数kk,都存在ck>0c_k>0,使得求解kSAT的精确算法复杂度大于等于2ckn2^{c_kn},当然这仅限于一个猜想,认为指数时间算法改进的底数不能任意的小
实际上,改进NPC问题的指数时间精确算法,在近期取得了许多突破:
任意色数图的顶点着色问题都有O∗(3n)O^{\ast}(3^n)的算法
背包问题有比O∗(2n2)O^{\ast}(2^{\dfrac{n}{2}})更好的算法
货郎问题有比O∗(2n)O^{\ast}(2^n)更好的算法

其他处理难解问题的策略

启发式方法:无法从理论上给出任何性能保证,但在实践中偏偏效果良好,就统称为启发式方法,常用的有回溯与分支限界法、局部搜索法(随机化策略、重启策略、模拟退火)、遗传算法等
平均复杂度:有些NPC问题在考虑平均复杂度时是易解的,例如哈密顿回路的平均情况对图G(n,12)G(n,\dfrac{1}{2})有O(n3)O(n^3)的算法
此处的12\dfrac{1}{2}为概率,实际算法设为G(n,p)G(n,p),即让图顶点数为nn,然后在任何两个不同顶点之间独立地以概率pp连一条边
难解算例生成:确定紧实例

笔者按:这一讲ppt内容和课本大有不同,不过本质上都不难理解,属于是在前面四章超高强度之后一个非常好的放松……最后还小小补充了第十二章,终于是将算分后半学期的笔记更新完毕了,准备好迎接无情的期末吧

随机算法
https://yjyxfcy.github.io/2026/06/03/sf5/
作者
Yjy
发布于
2026年6月3日
更新于
2026年11月5日
许可协议