目录
算法概论
序言
时间复杂度
- 常数项可忽略
- 当 a > b 时,\(n^a\) 支配 \(n^b\)
- 任何指数项支配任何多项式项
- 任何多项式项支配对数项:n 支配 \((logn)^3\)
\(e^{\frac{1}{2}\ln{n}}\) 比 \(5^{\ln{n}}\) 小
一个事实:在大 \(\Theta\) 符号意义下,当几何级数(\(c^k\))严格递减(c<1)时,几何级数的可以简化为首项;当级数严格递增(c>1)时,几何级数的和可以简化为末项;当级数保持不变时(c为1),几何级数的和可以简化为项数。
复杂度分析小窍门
- 若两段算法分别有复杂度\(T_1(n)=O(f_1(n))\)和\(T_2(n)=O(f_2(n))\),则
- \(T_1(n)+T_2(n)=max(O(f_1(n)), O(f_2(n)))\)
- \(T_1(n){\times}T_2(n)=O(f_1(n){\times}f_2(n))\)
- 若 \(T(n)\) 是关于 \(n\) 的 \(k\) 阶多项式,那么 \(T(n)=\Theta(n^k)\)
- 一个
for
循环的时间复杂度等于循环次数乘以循环体代码的复杂度 if-else
结构的复杂度取决于if
的条件判断复杂度和两个分支部分的复杂度,总体复杂度取三者中最大
==通常,将问题整体数学化后再进行算法设计,可以极大地优化复杂度==
数字的算法
常见运算的复杂度
- 加法:\(O(n)\)
- 乘法:日常:\(O(n^2)\),分治+Gauss:\(O(n^{1.59}\),快速 FT
- 模:
- 模的加法:\(O(n)\)
- 模的乘法:\(O(n^2)\)
- 模的除法:\(O(n^3)\):先用辗转相除法求出除数的逆元,再乘之
- 模的指数:\(O(n^3)\):\(x^y mod z=(x^{y/2})^2 mod z\)
- 最大公因数:\(O(n^3)\):更相减损法:\(gcd(x, y)=gcd(x-y, y)\)
数论
替代准则
若有 \(x{\equiv}x'(mod N)\) 和 \(y{\equiv}y'(mod N)\) 成立, 则有:\(x+y{\equiv}x'+y'(mod N)\) 和 \(xy{\equiv}x'y'(mod N)\)
Euclid 规则(更相减损法)
若 \(x\) 和 \(y\) 是正整数,且有 \(x{\geq}y\),则 \(gcd(x, y)=gcd(x mod y, 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,a mod b)=bx'+(a mod b)y'\] \[=bx'+(a-\lfloor\frac{a}{b}\rfloor{b})y'=ay'+b(x'-\lfloor\frac{a}{b}\rfloor{y'})\]
即 \(d=ax+by\),其中 \(x=y'\) 且 \(y=x'-\lfloor\frac{a}{b}\rfloor{y'}\)
模的除法定理
对于任意的 \(a mod N\),\(a\) 有一个模 \(N\) 的乘法逆元,当且仅当 \(a\) 与 \(N\) 互素。
Fermat 小定理
若 \(p\) 为一个素数,则对任意 \(1\leq{a}<p\),有 \(a^{p-1}\equiv1(mod p)\)
如果把后面的结论作为条件,则 \(p\) 大概率为素数
Lagrange 素数定理
令 \(\pi(x)\) 为 \(\leq{x}\) 的素数的个数,则有 \(\pi(x)\approx\frac{x}{ln(x)}\)
一个随机 n 位长的数字为素数的概率约为 \(\frac{1}{ln(2^n)}\approx\frac{1.44}{n}\)
随机算法
许多算法依赖于概率,其输出不一定准确,但是大概率准确。
可以分为两类: 1. Monte Carlo 算法:运行快,结果大概率正确 2. Las Vegas 算法:结果准确,运行大概率快
通用散列表
对于任意四个系数 \(a_1,\dots,a_4\in\{0,1,\dots,n-1\}\),记 \(a=(a_1,a_2,a_3,a_4)\), 定义散列函数 \(h_a(x_1,\dots,x_4)=\sum^4_{i=1}a_i\cdot{x_i}mod n\)
若系数 \(a=(a_1,a_2,a_3,a_4)\) 为随机均匀选取,则有 \[Pr\{h_a(x_1,\dots,x_4)=h_a(y_1,\dots,y_4)\}=\frac{1}{n}\] ,即两个数据别名相同的概率
通常把 \(h_a(x_1,\dots,x_4)\) 称为 \(x\) 的别名
散列表应用步骤: 1. 将散列表的大小 n 定为一个素数,其比将要存在该表中的期望数据项数目稍大,一般为两倍左右 2. 设所有数据项取值范围为 \(N=n^k\) 3. 每个数据项可以视为一个关于模 n 操作的 k 元组,而 \(H=\{h_a:a\in\{0,\dots,n-1\}^k\}\) 即为一个通用散列函数族
由于系数(即散列函数族)为随机均匀选取时,两个数据别名相同的概率很小, 故散列表性能很好,几乎为线性,而且空间复杂度也很小
插播一条高数:\(n!\geq\frac{n!}{(n/2)!}\geq\frac{n}{2}^\frac{n}{2}\)
分治算法
乘法
\[xy: O(n^2)\] \[xy=(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(3^{\log_2n})=O(n^{\log_23})\)
递推式
分治算法通常遵循: - 对于规模为 n 的问题,先递归地求解 a 个规模为 n/b 的子问题 - 然后在 \(O(n^d)\) 时间内将子问题的解合并起来 - 故运行时间为 \(T(n)=aT(\lceil{n/b}\rceil)+O(n^d)\) 1. 若 \(d>\log_ba, T(n)=O(n^d)\) 2. 若 \(d=\log_ba, T(n)=O(n^d\log{n})\) 3. 若 \(d<\log_ba, T(n)=O(n^{\log_ba})\) - 又称 主定理
合并排序
\(O(n\log{n})\)
- 将数列分为前后两部分,递归地对每一部分进行排序(最终每部分都为单元素数列)
- 将两个排好的有序数列 \(x[1...k], y[1...l]\) 合并为新数列 \(z\)
- 新数列的第 1 个为 \(x[1], y[1]\) 中小的
- 类似第一步进行递归
寻找中项
将寻找中位数抽象为更一般的:寻找第 k 小的数
在数列中,随机选取一个数 v,并将数列分为 \(>v, =v, <v\) 三个子列,则第 k 小的数一定落在其中一个子列中,且每个子列的长度已知。故只需搜索一个子列即可。
该算法依赖于 v 的好坏,平均为 \(O(n)\),最差为 \(\Theta(n^2)\)
快排与之思路一致
矩阵乘法
\[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}\]
其中 - \(P_1=A(F-H)\) - \(P_2=(A+B)H\) - \(P_3=(C+D)E\) - \(P_4=D(G-E)\) - \(P_5=(A+D)(E+H)\) - \(P_6=(B-D)(G+H)\) - \(P_7=(A-C)(E+F)\)
则 \(T(n)=7T(n/2)+O(n^2)\),最终复杂度为 \(O(n^{\log_27})\)
快速 Fourier 变换
以多项式相乘为出发点
性质
一个 d 次 多项式被其在任意 d+1 个不同点处的取值所唯一确定。
常见例子:两点确定一条直线
多项式相乘的分治实现
- 要计算 d 次多项式 \(A(x)\) 与 \(B(x)\) 的乘积 \(C(x)\),先选取 n 个点 \(x_0, x_1,\dots,x_{n-1}\),其中 \(n\geq2d+1\);
- 对每个点 \(x_k\),计算 \(A(x_k)\) 和 \(B(x_k)\)
- 对每个点 \(x_k\),计算 \(C(x_k)=A(x_k)B(x_k)\)
- 插值得到 \(C(x)=c_0+c_1x+\dots+c_{2d}x^{2d}\)
快速 Fourier 中,将这 n 个点选取为: \[\pm{x_0},\pm{x_1},\dots,\pm{x_{\frac{n}{2}-1}}\]
这利用了 \(x_i\) 的偶次幂 等于 \(-x_i\) 的偶次幂来减少运算
故 \[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)\]
如此,计算时间缩短一半
若能递归使用,即 使用同样的方法计算 \(A_e\) 和 \(A_o\),则能得到 \(O(n\log{n})\),其中须取复数 \(x_i\),则生成的新的自变量中存在相反对,可以作为下次的自变量
这就得到了快速 Fourier 算法:
- function \(FFT(A,\omega)\)
- Input: n 次 \(A(x)\) 的系数表达,其中 n 是 2 的幂,\(\omega\) 是单位元 1 的 n 次方根
- Output: \(A(x)\) 的值表达:\(A(\omega^0),\dots,A(\omega^{n-1})\)
- 算法见书 P74
插值
FFT:从系数表达到值表达: - <值> = FFT(<系数>, \(\omega\))
插值:从值表达到系数表达: - <系数> = \(\frac{1}{n}\)FFT(<系数>, \(\omega^{-1}\))
学不下去了,下一章!