算法概论

序言

时间复杂度

常数项可忽略
当 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. 新数列的第 1 个为 \(x[1], y[1]\) 中小的
2. 类似第一步进行递归

寻找中项

将寻找中位数抽象为更一般的：寻找第 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}\))

学不下去了，下一章！