算法概论
序言
时间复杂度
- 常数项可忽略
- 当 a > b 时,na 支配nb
- 任何指数项支配任何多项式项
- 任何多项式项支配对数项:n 支配(logn)3
e21lnn 比5lnn 小
一个事实:在大Θ 符号意义下,当几何级数(ck)严格递减(c<1)时,几何级数的可以简化为首项;当级数严格递增(c>1)时,几何级数的和可以简化为末项;当级数保持不变时(c为1),几何级数的和可以简化为项数。
复杂度分析小窍门
- 若两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n)),则
- T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))
- T1(n)×T2(n)=O(f1(n)×f2(n))
- 若T(n) 是关于n 的k 阶多项式,那么T(n)=Θ(nk)
- 一个
for
循环的时间复杂度等于循环次数乘以循环体代码的复杂度 if-else
结构的复杂度取决于 if
的条件判断复杂度和两个分支部分的复杂度,总体复杂度取三者中最大
通常,将问题整体数学化后再进行算法设计,可以极大地优化复杂度
数字的算法
常见运算的复杂度
- 加法:O(n)
- 乘法:日常:O(n2),分治+Gauss:O(n1.59,快速 FT
- 模:
- 模的加法:O(n)
- 模的乘法:O(n2)
- 模的除法:O(n3):先用辗转相除法求出除数的逆元,再乘之
- 模的指数:O(n3):xymodz=(xy/2)2modz
- 最大公因数:O(n3):更相减损法:gcd(x,y)=gcd(x−y,y)
数论
替代准则
若有x≡x′(modN) 和y≡y′(modN) 成立,
则有:x+y≡x′+y′(modN) 和xy≡x′y′(modN)
Euclid 规则(更相减损法)
若x 和y 是正整数,且有x≥y,则gcd(x,y)=gcd(xmody,y)
故:gcd(x,y)=gcd(x−y,y)
扩展 Euclid 规则(辗转相除法)
若d 整除a 和b,同时存在整数x 和y,使得d=sx+by 成立,
那么一定有d=gcd(a,b)
故
d=gcd(a,b)=gcd(b,amodb)=bx′+(amodb)y′
=bx′+(a−⌊ba⌋b)y′=ay′+b(x′−⌊ba⌋y′)
即d=ax+by,其中x=y′ 且y=x′−⌊ba⌋y′
模的除法定理
对于任意的amodN,a 有一个模N 的乘法逆元,当且仅当a 与N 互素。
Fermat 小定理
若p 为一个素数,则对任意1≤a<p,有ap−1≡1(modp)
如果把后面的结论作为条件,则p 大概率为素数
Lagrange 素数定理
令π(x) 为≤x 的素数的个数,则有π(x)≈ln(x)x
一个随机 n 位长的数字为素数的概率约为ln(2n)1≈n1.44
随机算法
许多算法依赖于概率,其输出不一定准确,但是大概率准确。
可以分为两类:
- Monte Carlo 算法:运行快,结果大概率正确
- Las Vegas 算法:结果准确,运行大概率快
通用散列表
对于任意四个系数a1,…,a4∈{0,1,…,n−1},记a=(a1,a2,a3,a4),
定义散列函数ha(x1,…,x4)=∑i=14ai⋅ximodn
若系数a=(a1,a2,a3,a4) 为随机均匀选取,则有
Pr{ha(x1,…,x4)=ha(y1,…,y4)}=n1
,即两个数据别名相同的概率
通常把ha(x1,…,x4) 称为x 的别名
散列表应用步骤:
- 将散列表的大小 n 定为一个素数,其比将要存在该表中的期望数据项数目稍大,一般为两倍左右
- 设所有数据项取值范围为N=nk
- 每个数据项可以视为一个关于模 n 操作的 k 元组,而H={ha:a∈{0,…,n−1}k} 即为一个通用散列函数族
由于系数(即散列函数族)为随机均匀选取时,两个数据别名相同的概率很小,
故散列表性能很好,几乎为线性,而且空间复杂度也很小
插播一条高数:n!≥(n/2)!n!≥2n2n
分治算法
乘法
xy:O(n2)
xy=(2n/2xH+xL)(2n/2yH+yL)=2nxHyH+2n/2(xHyL+xLyH)+xLyL:O(nln3),withxHyL+xLyH=(xH+xL)(yH+yL)−xHyH−xLyL
插播一条高数:O(3log2n)=O(nlog23)
递推式
分治算法通常遵循:
- 对于规模为 n 的问题,先递归地求解 a 个规模为 n/b 的子问题
- 然后在O(nd) 时间内将子问题的解合并起来
- 故运行时间为T(n)=aT(⌈n/b⌉)+O(nd)
- 若d>logba,T(n)=O(nd)
- 若d=logba,T(n)=O(ndlogn)
- 若d<logba,T(n)=O(nlogba)
合并排序
O(nlogn)
- 将数列分为前后两部分,递归地对每一部分进行排序(最终每部分都为单元素数列)
- 将两个排好的有序数列x[1...k],y[1...l] 合并为新数列z
- 新数列的第 1 个为x[1],y[1] 中小的
- 类似第一步进行递归
寻找中项
将寻找中位数抽象为更一般的:寻找第 k 小的数
在数列中,随机选取一个数 v,并将数列分为>v,=v,<v 三个子列,则第 k 小的数一定落在其中一个子列中,且每个子列的长度已知。故只需搜索一个子列即可。
该算法依赖于 v 的好坏,平均为O(n),最差为Θ(n2)
快排与之思路一致
矩阵乘法
XY=[ACBD][EGFH]=[AE+BGCE+DGAF+BHCF+DH]=[P5+P4−P2+P6P3+P4P1+P2P1+P5−P3−P7]
其中
- P1=A(F−H)
- P2=(A+B)H
- P3=(C+D)E
- P4=D(G−E)
- P5=(A+D)(E+H)
- P6=(B−D)(G+H)
- P7=(A−C)(E+F)
则T(n)=7T(n/2)+O(n2),最终复杂度为O(nlog27)
快速 Fourier 变换
以多项式相乘为出发点
性质
一个 d 次 多项式被其在任意 d+1 个不同点处的取值所唯一确定。
常见例子:两点确定一条直线
多项式相乘的分治实现
- 要计算 d 次多项式A(x) 与B(x) 的乘积C(x),先选取 n 个点x0,x1,…,xn−1,其中n≥2d+1;
- 对每个点xk,计算A(xk) 和B(xk)
- 对每个点xk,计算C(xk)=A(xk)B(xk)
- 插值得到C(x)=c0+c1x+⋯+c2dx2d
快速 Fourier 中,将这 n 个点选取为:
±x0,±x1,…,±x2n−1
这利用了xi 的偶次幂 等于−xi 的偶次幂来减少运算
故
A(xi)=Ae(xi2)+xiAo(xi2)A(−xi)=Ae(xi2)−xiAo(xi2)
如此,计算时间缩短一半
若能递归使用,即 使用同样的方法计算Ae 和Ao,则能得到O(nlogn),其中须取复数xi,则生成的新的自变量中存在相反对,可以作为下次的自变量
这就得到了快速 Fourier 算法:
- functionFFT(A,ω)
- Input: n 次A(x) 的系数表达,其中 n 是 2 的幂,ω 是单位元 1 的 n 次方根
- Output:A(x) 的值表达:A(ω0),…,A(ωn−1)
- 算法见书 P74
插值
FFT:从系数表达到值表达:
插值:从值表达到系数表达:
- <系数> =n1FFT(<系数>,ω−1)
学不下去了,下一章!