算法概论

序言

时间复杂度

  1. 常数项可忽略
  2. 当 a > b 时,nan^a 支配nbn^b
  3. 任何指数项支配任何多项式项
  4. 任何多项式项支配对数项:n 支配(logn)3(logn)^3

e12lnne^{\frac{1}{2}\ln{n}}5lnn5^{\ln{n}}

一个事实:在大Θ\Theta 符号意义下,当几何级数(ckc^k)严格递减(c<1)时,几何级数的可以简化为首项;当级数严格递增(c>1)时,几何级数的和可以简化为末项;当级数保持不变时(c为1),几何级数的和可以简化为项数。

复杂度分析小窍门

  • 若两段算法分别有复杂度T1(n)=O(f1(n))T_1(n)=O(f_1(n))T2(n)=O(f2(n))T_2(n)=O(f_2(n)),则
    • T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))T_1(n)+T_2(n)=max(O(f_1(n)), O(f_2(n)))
    • T1(n)×T2(n)=O(f1(n)×f2(n))T_1(n){\times}T_2(n)=O(f_1(n){\times}f_2(n))
  • T(n)T(n) 是关于nnkk 阶多项式,那么T(n)=Θ(nk)T(n)=\Theta(n^k)
  • 一个 for 循环的时间复杂度等于循环次数乘以循环体代码的复杂度
  • if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分支部分的复杂度,总体复杂度取三者中最大

通常,将问题整体数学化后再进行算法设计,可以极大地优化复杂度

数字的算法

常见运算的复杂度

  • 加法:O(n)O(n)
  • 乘法:日常:O(n2)O(n^2),分治+Gauss:O(n1.59O(n^{1.59},快速 FT
  • 模:
    • 模的加法:O(n)O(n)
    • 模的乘法:O(n2)O(n^2)
    • 模的除法:O(n3)O(n^3):先用辗转相除法求出除数的逆元,再乘之
    • 模的指数:O(n3)O(n^3)xymodz=(xy/2)2modzx^y mod z=(x^{y/2})^2 mod z
  • 最大公因数:O(n3)O(n^3):更相减损法:gcd(x,y)=gcd(xy,y)gcd(x, y)=gcd(x-y, y)

数论

替代准则

若有xx(modN)x{\equiv}x'(mod N)yy(modN)y{\equiv}y'(mod N) 成立,
则有:x+yx+y(modN)x+y{\equiv}x'+y'(mod N)xyxy(modN)xy{\equiv}x'y'(mod N)

Euclid 规则(更相减损法)

xxyy 是正整数,且有xyx{\geq}y,则gcd(x,y)=gcd(xmody,y)gcd(x, y)=gcd(x mod y, y)

故:gcd(x,y)=gcd(xy,y)gcd(x, y)=gcd(x-y, y)

扩展 Euclid 规则(辗转相除法)

dd 整除aabb,同时存在整数xxyy,使得d=sx+byd=sx+by 成立,
那么一定有d=gcd(a,b)d=gcd(a,b)

d=gcd(a,b)=gcd(b,amodb)=bx+(amodb)yd=gcd(a,b)=gcd(b,a mod b)=bx'+(a mod b)y'

=bx+(aabb)y=ay+b(xaby)=bx'+(a-\lfloor\frac{a}{b}\rfloor{b})y'=ay'+b(x'-\lfloor\frac{a}{b}\rfloor{y'})

d=ax+byd=ax+by,其中x=yx=y'y=xabyy=x'-\lfloor\frac{a}{b}\rfloor{y'}

模的除法定理

对于任意的amodNa mod Naa 有一个模NN 的乘法逆元,当且仅当aaNN 互素。

Fermat 小定理

pp 为一个素数,则对任意1a<p1\leq{a}<p,有ap11(modp)a^{p-1}\equiv1(mod p)

如果把后面的结论作为条件,则pp 大概率为素数

Lagrange 素数定理

π(x)\pi(x)x\leq{x} 的素数的个数,则有π(x)xln(x)\pi(x)\approx\frac{x}{ln(x)}

一个随机 n 位长的数字为素数的概率约为1ln(2n)1.44n\frac{1}{ln(2^n)}\approx\frac{1.44}{n}

随机算法

许多算法依赖于概率,其输出不一定准确,但是大概率准确。

可以分为两类:

  1. Monte Carlo 算法:运行快,结果大概率正确
  2. Las Vegas 算法:结果准确,运行大概率快

通用散列表

对于任意四个系数a1,,a4{0,1,,n1}a_1,\dots,a_4\in\{0,1,\dots,n-1\},记a=(a1,a2,a3,a4)a=(a_1,a_2,a_3,a_4)
定义散列函数ha(x1,,x4)=i=14aiximodnh_a(x_1,\dots,x_4)=\sum^4_{i=1}a_i\cdot{x_i}mod n

若系数a=(a1,a2,a3,a4)a=(a_1,a_2,a_3,a_4) 为随机均匀选取,则有

Pr{ha(x1,,x4)=ha(y1,,y4)}=1nPr\{h_a(x_1,\dots,x_4)=h_a(y_1,\dots,y_4)\}=\frac{1}{n}

,即两个数据别名相同的概率

通常把ha(x1,,x4)h_a(x_1,\dots,x_4) 称为xx 的别名

散列表应用步骤:

  1. 将散列表的大小 n 定为一个素数,其比将要存在该表中的期望数据项数目稍大,一般为两倍左右
  2. 设所有数据项取值范围为N=nkN=n^k
  3. 每个数据项可以视为一个关于模 n 操作的 k 元组,而H={ha:a{0,,n1}k}H=\{h_a:a\in\{0,\dots,n-1\}^k\} 即为一个通用散列函数族

由于系数(即散列函数族)为随机均匀选取时,两个数据别名相同的概率很小,
故散列表性能很好,几乎为线性,而且空间复杂度也很小

插播一条高数:n!n!(n/2)!n2n2n!\geq\frac{n!}{(n/2)!}\geq\frac{n}{2}^\frac{n}{2}

分治算法

乘法

xy:O(n2)xy: O(n^2)

xy=(2n/2xH+xL)(2n/2yH+yL)=2nxHyH+2n/2(xHyL+xLyH)+xLyL:O(nln3),withxHyL+xLyH=(xH+xL)(yH+yL)xHyHxLyLxy=(2^{n/2}x_H+x_L)(2^{n/2}y_H+y_L)\\ =2^nx_Hy_H+2^{n/2}(x_Hy_L+x_Ly_H)+x_Ly_L:\\O(n^{ln3}),\\ with x_Hy_L+x_Ly_H=(x_H+x_L)(y_H+y_L)-x_Hy_H-x_Ly_L

插播一条高数:O(3log2n)=O(nlog23)O(3^{\log_2n})=O(n^{\log_23})

递推式

分治算法通常遵循:

  • 对于规模为 n 的问题,先递归地求解 a 个规模为 n/b 的子问题
  • 然后在O(nd)O(n^d) 时间内将子问题的解合并起来
  • 故运行时间为T(n)=aT(n/b)+O(nd)T(n)=aT(\lceil{n/b}\rceil)+O(n^d)
    1. d>logba,T(n)=O(nd)d>\log_ba, T(n)=O(n^d)
    2. d=logba,T(n)=O(ndlogn)d=\log_ba, T(n)=O(n^d\log{n})
    3. d<logba,T(n)=O(nlogba)d<\log_ba, T(n)=O(n^{\log_ba})
    • 又称 主定理

合并排序

O(nlogn)O(n\log{n})

  1. 将数列分为前后两部分,递归地对每一部分进行排序(最终每部分都为单元素数列)
  2. 将两个排好的有序数列x[1...k],y[1...l]x[1...k], y[1...l] 合并为新数列zz
    1. 新数列的第 1 个为x[1],y[1]x[1], y[1] 中小的
    2. 类似第一步进行递归

寻找中项

将寻找中位数抽象为更一般的:寻找第 k 小的数

在数列中,随机选取一个数 v,并将数列分为>v,=v,<v>v, =v, <v 三个子列,则第 k 小的数一定落在其中一个子列中,且每个子列的长度已知。故只需搜索一个子列即可。

该算法依赖于 v 的好坏,平均为O(n)O(n),最差为Θ(n2)\Theta(n^2)

快排与之思路一致

矩阵乘法

XY=[ABCD][EFGH]=[AE+BGAF+BHCE+DGCF+DH]=[P5+P4P2+P6P1+P2P3+P4P1+P5P3P7]XY=\begin{bmatrix}A&B\\C&D\end{bmatrix}\begin{bmatrix}E&F\\G&H\end{bmatrix}\\ =\begin{bmatrix}AE+BG&AF+BH\\CE+DG&CF+DH\end{bmatrix}\\ =\begin{bmatrix}P_5+P_4-P_2+P_6&P_1+P_2\\P_3+P_4&P_1+P_5-P_3-P_7\end{bmatrix}

其中

  • P1=A(FH)P_1=A(F-H)
  • P2=(A+B)HP_2=(A+B)H
  • P3=(C+D)EP_3=(C+D)E
  • P4=D(GE)P_4=D(G-E)
  • P5=(A+D)(E+H)P_5=(A+D)(E+H)
  • P6=(BD)(G+H)P_6=(B-D)(G+H)
  • P7=(AC)(E+F)P_7=(A-C)(E+F)

T(n)=7T(n/2)+O(n2)T(n)=7T(n/2)+O(n^2),最终复杂度为O(nlog27)O(n^{\log_27})

快速 Fourier 变换

以多项式相乘为出发点

性质

一个 d 次 多项式被其在任意 d+1 个不同点处的取值所唯一确定。

常见例子:两点确定一条直线

多项式相乘的分治实现

  • 要计算 d 次多项式A(x)A(x)B(x)B(x) 的乘积C(x)C(x),先选取 n 个点x0,x1,,xn1x_0, x_1,\dots,x_{n-1},其中n2d+1n\geq2d+1;
  • 对每个点xkx_k,计算A(xk)A(x_k)B(xk)B(x_k)
  • 对每个点xkx_k,计算C(xk)=A(xk)B(xk)C(x_k)=A(x_k)B(x_k)
  • 插值得到C(x)=c0+c1x++c2dx2dC(x)=c_0+c_1x+\dots+c_{2d}x^{2d}

快速 Fourier 中,将这 n 个点选取为:

±x0,±x1,,±xn21\pm{x_0},\pm{x_1},\dots,\pm{x_{\frac{n}{2}-1}}

这利用了xix_i 的偶次幂 等于xi-x_i 的偶次幂来减少运算

A(xi)=Ae(xi2)+xiAo(xi2)A(xi)=Ae(xi2)xiAo(xi2)A(x_i)=A_e(x_i^2)+x_iA_o(x_i^2)\\A(-x_i)=A_e(x_i^2)-x_iA_o(x_i^2)

如此,计算时间缩短一半

若能递归使用,即 使用同样的方法计算AeA_eAoA_o,则能得到O(nlogn)O(n\log{n}),其中须取复数xix_i,则生成的新的自变量中存在相反对,可以作为下次的自变量

这就得到了快速 Fourier 算法:

  • functionFFT(A,ω)FFT(A,\omega)
  • Input: n 次A(x)A(x) 的系数表达,其中 n 是 2 的幂,ω\omega 是单位元 1 的 n 次方根
  • Output:A(x)A(x) 的值表达:A(ω0),,A(ωn1)A(\omega^0),\dots,A(\omega^{n-1})
  • 算法见书 P74

插值

FFT:从系数表达到值表达:

  • <值> = FFT(<系数>,ω\omega)

插值:从值表达到系数表达:

  • <系数> =1n\frac{1}{n}FFT(<系数>,ω1\omega^{-1})

学不下去了,下一章!