本文最后更新于 2026年11月5日 晚上
北京大学信息科学技术学院
算法设计与分析(2026春)的课程笔记
第十一章:随机算法
在经历了复杂度下限分析、NP完全、近似算法等一系列抽象内容的洗礼后,我们终于苦尽甘来,熬到了比较简单的一章:随机算法
Las Vegas型随机算法
随机快排
顾名思义,就是在选择pivot时随机选择一个元素,而不是每次固定选择某一个元素,然后递归的方式和普通快排相同
随机选取pivot,其位于排序后第i i i 个位置(i = 0 , 1 , . . . , n − 1 i=0,1,...,n-1 i = 0 , 1 , ... , n − 1 )的概率为1 n \dfrac{1}{n} n 1 ,故
T ( n ) = n − 1 + 1 n ( Σ i = 0 n − 1 T ( i ) + T ( n − i − 1 ) ) = n − 1 + 2 n Σ i = 1 n − 1 T ( 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 ) = n − 1 + n 1 ( Σ i = 0 n − 1 T ( i ) + T ( n − i − 1 )) = n − 1 + n 2 Σ i = 1 n − 1 T ( i )
我们归纳证明T ( n ) ≤ 2 n l n n T(n) \le 2n ln n T ( n ) ≤ 2 n l nn
n = 1 n=1 n = 1 时显然,假设对于1 , 2 , . . . n − 1 1,2,...n-1 1 , 2 , ... n − 1 时都成立,则n n n 时
T ( n ) ≤ n − 1 + 2 n Σ i = 1 n − 1 2 i l n i ≤ n − 1 + 2 n ∫ 1 n 2 x l n x d x T(n)\le n-1+\dfrac{2}{n}\Sigma_{i=1}^{n-1}2ilni\le n-1+\dfrac{2}{n} \int_1^{n} 2xlnx \ dx T ( n ) ≤ n − 1 + n 2 Σ i = 1 n − 1 2 i l ni ≤ n − 1 + n 2 ∫ 1 n 2 x l n x d x
≤ n − 1 + 2 n l n n − n + 1 n ≤ 2 n l n n \le n-1+2n lnn-n+\dfrac{1}{n} \le 2nlnn ≤ n − 1 + 2 n l nn − n + n 1 ≤ 2 n l nn
所以上界可以从Θ ( n l o g n ) \Theta(n logn) Θ ( n l o g n ) 精确到2 n l n n 2nlnn 2 n l nn
随机选择
从数组A A A 的p p p 到r r r 下标选第k k k 小的数
if p = r p=r p = r return;
否则在p , r p,r p , r 之中随机选出下标i i i ,假设有j j j 个数小于等于A [ i ] A[i] A [ i ]
若k ≤ j k\le j k ≤ j ,就从p p p 到p + j − 1 p+j-1 p + j − 1 下标选第k k k 小的数
否则就从p + j p+j p + j 到r r r 下标选第k − j k-j k − j 小的数
递归调用即可
假设1 , 2 , . . . n 1,2,...n 1 , 2 , ... n 中每个数被选到概率相同,且第k k k 个数总是出现在被划分后两个数组中较大者,则
T ( n ) ≤ 2 n Σ i = n 2 n − 1 T ( i ) + O ( n ) T(n)\le \dfrac{2}{n}\Sigma_{i=\dfrac{n}{2}}^{n-1}T(i)+O(n) T ( n ) ≤ n 2 Σ i = 2 n n − 1 T ( i ) + O ( n )
类似地我们可归纳证明T ( n ) ≤ c n T(n) \le cn T ( n ) ≤ c n
n皇后随机放置
对于每一行,先筛选出所有合法位置,再随机选一个位置放置皇后
改进:与回溯相结合
s t o p V e g a s stopVegas s t o p V e g a s 个用随机放,剩下n − s t o p V e g a s n-stopVegas n − s t o p V e g a s 仍用经典的回溯
对于不同的$ stopVegas 值,设 值,设
值,设 p 为算法成功概率 为算法成功概率
为算法成功概率 s 为一次成功搜索访问的结点数的平均值 为一次成功搜索访问的结点数的平均值
为一次成功搜索访问的结点数的平均值 e 为一次不成功搜索访问的结点数的平均值 为一次不成功搜索访问的结点数的平均值
为一次不成功搜索访问的结点数的平均值 t 为算法找到一个解的平均时间则 为算法找到一个解的平均时间
则 为算法找到一个解的平均时间则 t=ps+(1-p)(e+t) \rightarrow t=s+e\dfrac{1-p}{p}$
Monte Calo型随机随机算法
主元素测试
我们将出现次数超过一半以上的元素称为主元素
输入n n n 个元素的数组T T T ,判断其是否存在主元素
我们定义算法M ( T , n ) M(T,n) M ( T , n )
在1 , 2 , . . . n 1,2,...n 1 , 2 , ... n 中随机选取下标i i i ,x = T [ i ] x=T[i] x = T [ i ]
统计x x x 在T T T 中出现次数,若> n 2 > \dfrac{n}{2} > 2 n return true,否则return false
显然这个算法是不准确的,如果回答true那倒好,说明确实有主元素,但如果回答false,难以断言就一定没有主元素
我们调用时,如果回答true就结束,回答false就再调用
那么调用k k k 次正确的概率为
p + ( 1 − p ) p + . . . + ( 1 − p ) k − 1 p = 1 − ( 1 − p ) k p+(1-p)p+...+(1-p)^{k-1}p=1-(1-p)^{k} p + ( 1 − p ) p + ... + ( 1 − p ) k − 1 p = 1 − ( 1 − p ) k
由于当回答true时,数组里至少n 2 \dfrac{n}{2} 2 n 个元素都是x x x ,所以选中x x x 的概率p > 1 2 p> \dfrac{1}{2} p > 2 1
因此1 − ( 1 − p ) k > 1 − 2 − k 1-(1-p)^{k} > 1-2^{-k} 1 − ( 1 − p ) k > 1 − 2 − k
改进:对于任意给定ϵ > 0 \epsilon>0 ϵ > 0 ,要使出错概率不超过ϵ \epsilon ϵ
则2 − k ≤ ϵ 2^{-k} \le \epsilon 2 − k ≤ ϵ
两边取以2为底的对数,有
− k ≤ l o g ϵ -k \le log \epsilon − k ≤ l o g ϵ
k ≥ − l o g ϵ k \ge -log \epsilon k ≥ − l o g ϵ
故k ≥ ⌈ l o g 1 ϵ ⌉ k \ge \lceil log\dfrac{1}{\epsilon} \rceil k ≥ ⌈ l o g ϵ 1 ⌉
我们取k = ⌈ l o g 1 ϵ ⌉ k=\lceil log\dfrac{1}{\epsilon} \rceil k = ⌈ l o g ϵ 1 ⌉ ,调用k k k 次算法,即可保证出错概率不超过ϵ \epsilon ϵ
串相等测试
A A A 有一个长串x x x ,B B B 也有一个长串y y y ,A , B A,B A , B 两人希望知道x , y x,y x , y 是否相等
那你说,这不简单吗,直接让A A A 把x x x 发给B B B ,B B B 进行一个比较就好,然而由于串过长,发送时占用资源过多,A , B A,B A , B 希望你找到更好的办法
于是你打算让A A A 对x x x 采用f f f 操作,导出一个f ( x ) f(x) f ( x ) 发给B B B ,B B B 也用相同操作导出f ( y ) f(y) f ( y ) ,若f ( x ) ≠ f ( y ) f(x) \neq f(y) f ( x ) = f ( y ) 即可断言x ≠ y x \neq y x = y ,但是当f ( x ) = f ( y ) f(x)=f(y) f ( x ) = f ( y ) 时依然无法断言x = y x=y x = y
我们假设x , y x,y x , y 二进制表示分别为I ( x ) , I ( y ) I(x),I(y) I ( x ) , I ( y )
令I p ( x ) = I ( x ) m o d p I_p(x)= I(x ) \ mod \ p I p ( x ) = I ( x ) m o d p
A A A 将素数p p p 和I p ( x ) I_p(x) I p ( x ) 传给B B B ,当p p p 不太大时,传的就是短串
问题还是如上面所说,而且这里还有新问题,what if p ∣ ( I ( x ) − I ( y ) ) p | (I(x)-I(y)) p ∣ ( I ( x ) − I ( y )) ?
我们选择随机选择素数p p p 进行测试
出错的必要条件:x , y x,y x , y 位数相同,p ∣ ( I ( x ) − I ( y ) ) p | (I(x)-I(y)) p ∣ ( I ( x ) − I ( y ))
下面我们介绍关于素数的一些性质
函数π ( t ) \pi(t) π ( t ) 定义为小于t t t 的不同素数个数
例如π ( 20 ) = 8 ( 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 ) \pi(20)=8 \ (2,3,5,7,11,13,17,19) π ( 20 ) = 8 ( 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 )
于是我们有素数定理:π ( t ) ≈ t l n t \pi(t)\approx \dfrac{t}{lnt} π ( t ) ≈ l n t t
如果k < 2 n k<2^n k < 2 n ,n n n 不太小,则整除k k k 的不同素数个数小于π ( n ) \pi(n) π ( n )
由此,我们可以估计出错概率
我们重复执行j j j 次,每次都随机选择小于M M M 的素数
令j = ⌈ l o g l o g n ⌉ j=\lceil loglogn \rceil j = ⌈ l o g l o g n ⌉ ,则出错概率
( 1 n ) j ≤ 1 n ⌈ l o g l o g n ⌉ (\dfrac{1}{n})^j \le \dfrac{1}{n^{\lceil loglogn \rceil}} ( n 1 ) j ≤ n ⌈ l o g l o g n ⌉ 1
模式匹配
输入:二进制串x , y x,y x , y ,长度分别为n , m n,m n , m ,n ≥ m n \ge m n ≥ m
输入:若y y y 在x x x 中,输入y y y 出现的第一个位置,否则输出0
这个东西很眼熟对不对?本质上就是数算中学的字符串匹配(简化版)
不必多说,朴素匹配复杂度O ( m n ) O(mn) O ( mn ) ,KMP算法复杂度O ( m + n ) O(m+n) O ( m + n )
但是今天!我们要尝试用随机算法
设x ( j ) = x j x j + 1 . . . x j + m − 1 x(j)=x_jx_{j+1}...x_{j+m-1} x ( j ) = x j x j + 1 ... x j + m − 1
我们将x ( j ) x(j) x ( j ) 和y y y 逐字符比较改为I p ( x ( j ) ) I_p(x(j)) I p ( x ( j )) 和I p ( y ) I_p(y) I p ( y ) 的比较
由二进制性质,x ( j + 1 ) = 2 x ( j ) − 2 m x j + x j + m x(j+1)=2x(j)-2^mx_j+x_{j+m} x ( j + 1 ) = 2 x ( j ) − 2 m x j + x j + m
令W p = 2 m ( m o d p ) W_p=2^m(mod \ p) W p = 2 m ( m o d p )
则I p ( x ( j + 1 ) ) = ( 2 I p ( x ( j ) ) − W p x j + x j + m ) ( m o d p ) I_p(x(j+1))=(2I_p(x(j))-W_px_j+x_{j+m})(mod \ p) I p ( x ( j + 1 )) = ( 2 I p ( x ( j )) − W p x j + x j + m ) ( m o d p )
由此公式,从I p ( x ( j ) ) I_p(x(j)) I p ( x ( j )) 计算I p ( x ( j + 1 ) ) I_p(x(j+1)) I p ( x ( j + 1 )) 只需要常数时间
于是我们有如下算法:
从随机选取小于M M M 的素数p p p
然后取j j j 从1 1 1 开始,一直循环到n − m + 1 n-m+1 n − m + 1
采取上面的迭代方式,如果出现了I p ( x ( j ) ) = I p ( y ) I_p(x(j))=I_p(y) I p ( x ( j )) = I p ( y ) 就return j
否则如果循环完了还没结果就return 0
时间复杂度O ( m + n ) O(m+n) O ( m + n )
出错条件和出错概率如下:
素数测试
首先我们来学习一下,如何“优雅”地求x x x 的m m m 次幂
其中x x x 为实数,m = d k d k − 1 . . . d 1 m=d_kd_{k-1}...d_1 m = d k d k − 1 ... d 1 为二进制自然数
算法如下:
1 2 3 4 5 6 y=1for j in range(k,0): y=y*y if d_j==1: y=x*yreturn y
接下来我们更进一步,计算a m o d n a \ mod \ n a m o d n 的m m m 次幂,这就是所谓的快速幂
输入a , m , n a,m,n a , m , n 均为正整数,m ≤ n m \le n m ≤ n ,m = d k d k − 1 . . . d 1 m=d_kd_{k-1}...d_1 m = d k d k − 1 ... d 1 为二进制自然数
算法如下:
1 2 3 4 5 6 y=1for j in range(k,0): y=y*y%n if b_j==1: y=a*y%nreturn y
可以看出其实就加了mod n 这一步
以位乘为基本运算,T ( n ) = O ( k l o g 2 n ) = O ( l o g 3 n ) T(n)=O(k log^{2} n)=O(log^{3} n) T ( n ) = O ( k l o g 2 n ) = O ( l o g 3 n )
接下来我们终于可以开始素数测试了
首先回顾一下高中学过的费马小定理:
若n n n 为素数,则对于所有正整数a m o d n ≠ 0 a \ mod \ n \neq 0 a m o d n = 0 ,有:
a n − 1 ≡ 1 ( m o d n ) a^{n-1} \equiv 1 (\ mod \ n) a n − 1 ≡ 1 ( m o d n )
于是我们有了一个粗糙算法:
计算2 n − 1 ≡ 1 ( m o d n ) 2^{n-1} \equiv 1 (\ mod \ n) 2 n − 1 ≡ 1 ( m o d n ) ,如果满足则n n n 为素数,否则为合数
问题在于这里只对于a = 2 a=2 a = 2 进行了测试,容易出反例,比如n = 341 n=341 n = 341 就是一个,满足上述条件且为合数,此时称n n n 为基2的“伪素数”
于是我们进行改进,随机选取for a in range(2,n),例如取a = 3 a=3 a = 3 就可以否定341
然而我们必须指出,费马小定理只是必要条件而非充分条件
这意味着即使所有与n n n 互质的正整数a a a 都满足定理,n n n 也不一定就是素数
这种n n n 很特殊,我们称其为Carmichael数,如 561,1105,1729,2465 等
Carmichael数非常少,小于 10 8 10^8 1 0 8 的只有 255 个
由初等数论可以证明:如果n为合数,但不是Carmichael数,那么上面的算法测试n为合数的概率至少为1/2
在费马小定理之外,我们给出另一个必要条件:
如果n n n 为素数,则x 2 ≡ 1 ( m o d n ) x^{2} \equiv 1 (\ mod \ n) x 2 ≡ 1 ( m o d n ) 的根只有两个
即x = 1 x=1 x = 1 和x = − 1 x=-1 x = − 1 (mod n 意义下)
我们称不是1或-1的根为非平凡的,如果方程有非平凡的根,则n n n 为合数
于是我们给出测试方法:
设n n n 为奇素数,则n − 1 n-1 n − 1 为偶数,设n − 1 = 2 q m ( q ≥ 1 ) n-1=2^qm(q \ge 1) n − 1 = 2 q m ( q ≥ 1 )
在mod n 意义下,我们构造序列a m , a 2 m , a 4 m , . . . , a 2 q m a^m,a^{2m},a^{4m},...,a^{2^qm} a m , a 2 m , a 4 m , ... , a 2 q m
其中最后一项即为a n − 1 a^{n-1} a n − 1 ,并且每一项是前面一项的平方
测试方法:
随机选取a ∈ [ 2 , 3 , . . . , n − 1 ] a \in [2,3,...,n-1] a ∈ [ 2 , 3 , ... , n − 1 ] 进行测试
对于任意i = 0 , 1 , . . . q − 1 i=0,1,...q-1 i = 0 , 1 , ... q − 1 判断a 2 i m m o d n a^{2^im} \ mod \ n a 2 i m m o d n 是否为1和n-1,且它后一项是否为1
如果其后项为1,但它本身不为1和n-1,则它就是非平凡根,从而知道n n n 不是素数
上面为一个实例,该算法被称为Miller-Rabin算法
首先找q , m q,m q , m 使得n − 1 = 2 q m n-1=2^qm n − 1 = 2 q m ,复杂度O ( l o g n ) O(log n) O ( l o g n )
然后检测序列是否存在非平凡根,复杂度O ( l o g 3 n ) O(log^3 n) O ( l o g 3 n )
可证明每次测试出错概率最多1/2,重复测试k k k 次出错概率最多2 − k 2^{-k} 2 − k
令k = ⌈ l o g n ⌉ k= \lceil logn \rceil k = ⌈ l o g n ⌉ ,则2 − k ≤ 1 n 2^{-k} \le \dfrac{1}{n} 2 − k ≤ n 1 ,正确率为1 − 1 n 1-\dfrac{1}{n} 1 − n 1
换言之,若n n n 为素数,算法输出“素数”,若n n n 为合数,算分以1 − 1 n 1-\dfrac{1}{n} 1 − n 1 概率输出“合数”
由于测试需要k k k 次,按位乘统计,总时间复杂度O ( l o g 4 n ) O(log^4 n) O ( l o g 4 n )
两种算法的对比与总结
Las Vegas型
Las Vegas型随机算法主要是修改确定性算法得到,一般把某一步确定性选择变为随机选择,可以与确定性算法相结合使用,有可能改进确定性算法的平均时间复杂度
这种算法的特点是要么得不到解,如果有解,解一定是正确的,但运行时间时短时长,本身是一个随机变量,因此我们更关心它的平均运行时间
我们把期望运行时间是输入规模的多项式 且总是给出正确答案的 随机算法称为有效的 Las Vegas型随机算法
Monte Calo型
Monte Calo型随机算法不但运行时间是随机变量,而且计算结果也是随机事件
我们把总是在多项式时间内运行 且出错概率不超过1 3 \dfrac{1}{3} 3 1 的随机算法称为有效的Monte Calo型随机算法
当然其实只要算法执行足够多次,出错概率可以变得任意小,也不需要这个1 3 \dfrac{1}{3} 3 1
单侧错误和双侧错误
弃真型单侧错误:当算法宣布接受时结果一定对,宣布拒绝时不一定对,例如主元素测试
取伪型单侧错误:算法宣布拒绝时结果一定对,宣布接受时不一定对,例如素数测试
双侧错误:在所有输入上同时出现上述两种不同的错误
随机算法的分类与局限性
Las Vegas型中,我们有零错误概率多项式时间算法(有效的),称为ZPP
Monte Calo型中,错误概率有界的有效算法(多项式时间)称为BPP
在此基础上,如果是弃真型单侧错误概率有界,称为RP,取伪型称为coRP
局限性在于:错误概率有界的多项式时间随机算法不太可能解决NP完全问题
处理难解问题的策略
严格来说这是第十二章的内容了,不过老师也没细讲,在此就并入十一章中,简单带过
对问题施加限制
例如SAT问题,限制成2SAT,它就是P类问题了
或者限制成HornSAT(输入限制为霍恩公式,析取式中正文字,即不带否定号的变量,至多出现一次),那么也变成了P类问题
再比如说各类图的问题,也可以限制参数如下:
固定参数算法
通常把优化问题转化为判定问题时,都会在输入中引入一个参数
例如顶点覆盖问题:给定图G G G ,正整数K K K (小于等于G G G 的顶点数),问是否存在不超过K K K 的顶点覆盖?
我们固定常数k k k ,输入为( G , k ) (G,k) ( G , k ) ,从而穷举所有k k k 元顶点子集,看是否存在顶点覆盖,复杂度约为O ( k n k + 1 ) = O ( 2 k k n ) O(kn^{k+1})=O(2^k kn) O ( k n k + 1 ) = O ( 2 k k n )
所以在O ( 2 k k n ) O(2^k kn) O ( 2 k k n ) 时间内能够正确解决大小不超过k k k 的顶点覆盖问题
改进的指数时间算法
我们用O ∗ O^{\ast} O ∗ 表述忽略多项式因子,例如O ∗ ( 2 n ) = O ( n O ( 1 ) 2 n ) O^{\ast}(2^n)=O(n^{O(1)}2^n) O ∗ ( 2 n ) = O ( n O ( 1 ) 2 n )
当一个问题,暴力算法时间O ∗ ( 2 n ) O^{\ast}(2^n) O ∗ ( 2 n ) 时,则∀ 1 < c < 2 \forall 1<c<2 ∀1 < c < 2 ,时间复杂度为O ∗ ( c n ) O^{\ast}(c^n) O ∗ ( c n ) 的指数时间算法称为 非平凡(改进)的指数时间算法
例如我们可证明,SAT可以在O ∗ ( 1.8393 n ) O^{\ast}(1.8393^n) O ∗ ( 1.839 3 n ) 时间内正确求解
指数时间假设:对于任意正整数k k k ,都存在c k > 0 c_k>0 c k > 0 ,使得求解kSAT的精确算法复杂度大于等于2 c k n 2^{c_kn} 2 c k n ,当然这仅限于一个猜想,认为指数时间算法改进的底数不能任意的小
实际上,改进NPC问题的指数时间精确算法,在近期取得了许多突破:
任意色数图的顶点着色问题都有O ∗ ( 3 n ) O^{\ast}(3^n) O ∗ ( 3 n ) 的算法
背包问题有比O ∗ ( 2 n 2 ) O^{\ast}(2^{\dfrac{n}{2}}) O ∗ ( 2 2 n ) 更好的算法
货郎问题有比O ∗ ( 2 n ) O^{\ast}(2^n) O ∗ ( 2 n ) 更好的算法
其他处理难解问题的策略
启发式方法:无法从理论上给出任何性能保证,但在实践中偏偏效果良好,就统称为启发式方法,常用的有回溯与分支限界法、局部搜索法(随机化策略、重启策略、模拟退火)、遗传算法等
平均复杂度:有些NPC问题在考虑平均复杂度时是易解的,例如哈密顿回路的平均情况对图G ( n , 1 2 ) G(n,\dfrac{1}{2}) G ( n , 2 1 ) 有O ( n 3 ) O(n^3) O ( n 3 ) 的算法
此处的1 2 \dfrac{1}{2} 2 1 为概率,实际算法设为G ( n , p ) G(n,p) G ( n , p ) ,即让图顶点数为n n n ,然后在任何两个不同顶点之间独立地以概率p p p 连一条边
难解算例生成:确定紧实例
笔者按:这一讲ppt内容和课本大有不同,不过本质上都不难理解,属于是在前面四章超高强度之后一个非常好的放松……最后还小小补充了第十二章,终于是将算分后半学期的笔记更新完毕了,准备好迎接无情的期末吧