算法概论笔记

算法概论

序言

时间复杂度

1. 常数项可忽略
2. 当 a > b 时，$n^a$ 支配 $n^b$
3. 任何指数项支配任何多项式项
4. 任何多项式项支配对数项：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})$

1. 将数列分为前后两部分，递归地对每一部分进行排序（最终每部分都为单元素数列）
2. 将两个排好的有序数列 $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}$)

学不下去了，下一章！