算法复习总结
第一节 时间复杂度计算
Akra-Bazzi定理：常数$a_i>0, 0<b_i<1$，
别忘了等差数列和等比数列的求和公式
扩展二项式定理：
$\binom{n}{m}=C_n^m(0\leq m\leq n)$，
当$\alpha<0$时：
第二节 最小生成树
Prim 和 Kruskal
第三节 最短路
三角不等式：$d_w(s, v) = d_w(s, u) + w(u, v)$
松弛操作：$d_w(s, v) = \min\left\{d_w(s, u) + w(u, v), d_w(s, v)\right\}$
单源最短路
- DAG上的单源最短路：$O(n+m)$（拓扑排序$O(n+m)$，初始化$O(n)$，拓扑序枚举点松弛$O(n+m)$）
- Bellman-Ford：$O(nm)$
- Dijkstra：$O(n\log{n}+m)$
多源最短路
- Floyd-Warshall：$O(n^3)$
- Johnson’s：先建到所有点距离为$0$的超级源点，用B-F求出超级源点的单源最短路作为势能$h$，让图中每条边的边权$w’(u,v)=w(u,v)+h(u)-h(v)$，再对新图跑$n$遍Dijkstra，再变换回去就行，$O(n(n\log{n}+m))$
第四节 分治
快速傅里叶变换
欧拉公式（背！）：$e^{i\theta} = \cos{\theta} + i\sin{\theta}$
卷积定理：
- 时域卷积$=$频域乘积 $f(t)\otimes g(t) = F(\omega)\odot G(\omega)$
- 时域乘积$=$频域卷积 $f(t)\odot g(t) = F(\omega)\otimes G(\omega)$
周期函数$c_n=\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}{f(t)\cdot e^{-i\cdot (n\omega_0)t}}\dd{t}$，非周期函数$F(\omega)=\int_{-\infty}^{\infty}{f(t)\cdot e^{-i\omega t}}\dd{t}$
积分不收敛时用拉普拉斯变换$F(\omega)=\int_{0}^{+\infty}{f(t)\cdot e^{-(\sigma \cdot i\omega t)}}\dd{t}$（$\sigma$足够小就收敛）
DFT：$y[K]=\sum\limits_{n=0}^{N-1}{x[n]\cdot e^{-\frac{2\pi}{N}Kn\cdot i}}, K=0,1,\cdots,N-1\quad(\text{默认}T=N,也就是周期函数)$
FFT：分奇偶，递归…
时间复杂度$T(N) = 2T(\frac{N}{2})+O(N)=O(N\log{N})$，空间复杂度$O(\frac{N}{B}\log_M{N})$
vEB树
第五节 动态规划
Subproblem 定义子问题
Relate Subprob 关联子问题
Topological order 拓扑序
Base cases 边界情况
Original 原始问题
Time Analysis 时间复杂度分析
第六节 均摊分析
聚合分析
零存整取
势能法
第七节 P/NP问题
P：多项式时间算法、弱多项式时间（$\log_n{U}$）、伪多项式时间（$nU$）
NP：确定性时间算法猜一个解，再用确定性图灵机多项式时间内验证
EXP：只能在指数时间内解决的问题
R(ecursive)：能在有限时间内解决的问题
第九节 哈希
全域哈希：$A$为一系列哈希函数$h$的集合，每个$h\in H$映射$U$到${1, 2, \cdots, M-1}$，如果对所有的$x\neq y\in U，Pr[h(x)=h(y)] \leq \frac1M \Leftrightarrow \frac{|\{h\in H|h(x)=h(y)\}|}{|H|} \leq \frac1M$，那么称它为全域的。
