分析方法

详细见 算法复杂度之摊还分析

一般法

1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

主定理 (Master Theorem)

我们可以使用 Master Theorem 来快速求得关于递归算法的复杂度。 假设我们有递推关系式

$$T(n)=aT\left(\frac{n}{b}\right)＋f(n)\mathrm{\forall }n>b$$

那么

$$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(n^{{\log }_{b}a})& f(n)=O(n^{{\log }_{b}a-ϵ})\\ \mathrm{\Theta }(f(n))& f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})\\ \mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)& f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n),k\ge 0\end{array}$$

均摊复杂度

算法往往是会对内存中的数据进行修改的，而同一个算法的多次执行，就会通过对数据的修改而互相影响。

例如快速排序中的“按大小分类”操作，单次执行的最坏时间复杂度，看似是 $O(n)$ 的。 但是由于快排的分治过程，先前的“分类”操作每次都减小了数组长度，所以实际的总复杂度 $O(n\log n)$，分摊在每一次“分类”操作上，是 $O(\log n)$。

多次操作的总复杂度除以操作次数，就是这种操作的 均摊复杂度。

势能分析

势能分析，是一种求均摊复杂度上界的方法。 求均摊复杂度，关键是表达出先前操作对当前操作的影响。势能分析用一个函数来表达此种影响。

定义“状态”$S$：即某一时刻的所有数据。在快排的例子中，一个“状态”就是当前过程需要排序的下标区间

定义“初始状态”$S_0$：即未进行任何操作时的状态。在快排的例子中，“初始状态”就是整个数组

假设存在从状态到数的函数 $F$，且对于任何状态 $S$，$F(S)\ge F(S_0)$，则有以下推论：

设 $S_1,S_2,\cdots ,S_m$ 为从 $S_0$ 开始连续做 $m$ 次操作所得的状态序列，$c_i$ 为第 $i$ 次操作的时间开销。

记 $p_i=c_i+F(S_i)-F(S_{i-1})$，则 $m$ 次操作的总时间花销为

$$\sum _{i=1}^m{p}_i+F(S_0)-F(S_m)$$

（正负相消，证明显然）

又因为 $F(S)\ge F(S_0)$，所以有

$$\sum _{i=1}^m{p}_i\ge \sum _{i=1}^m{c}_i$$

因此，若 $p_i=O(T(n))$，则 $O(T(n))$ 是均摊复杂度的一个上界。

势能分析在实际应用中有很多技巧，在此不详细展开。

应用

由数据范围反推算法复杂度以及算法内容 ¹

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择:

1. $n\le 30$ , 指数级别, dfs + 剪枝，状态压缩dp
2. $n\le 100\Rightarrow O\left(n^3\right)$ , floyd， dp， 高斯消元
3. $n\le 1000\Rightarrow O\left(n^2\right),O(n^2\log n)$ ，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
4. $n\le 10000\Rightarrow O(n\ast \sqrt{n})$ ，块状链表、分块、莫队
5. $n\le 100000\Rightarrow O(n\log n)\Rightarrow$ 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、 prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
6. $n\le 1000000\Rightarrow O(n)$ , 以及常数较小的 $O(n\log n)$ 算法 $\Rightarrow$ 单调队列、hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 $O(n\log n)$ 的做法：sort、树状数组、heap、dijkstra、spfa
7. $n\le 10000000=O(n)$ ，双指针扫描、 kmp、AC自动机、线性筛素数
8. $n\le {10}^9\Rightarrow O(\sqrt{n})$ ， 判断质数
9. $n\le {10}^{18}\Rightarrow O(\log n)$ ，最大公约数，快速幂，数位DP
10. $n\le {10}^{1000}\Rightarrow O((\log n{)}^2)$ , 高精度加减乘除
11. $n\le {10}^{100000}\Rightarrow O(\log k\times \log \log k)$, $k$ 表示位数，高精度加减、FFT/NTT

一些算法的复杂度

基础算法
快速排序 归并排序 二分	$O(n\mathrm{l}\mathrm{o}\mathrm{g}n)$
双指针 数组元素目标和	$O(n)$

排序算法
	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
直接选择排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
直接插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
快速排序	$O(n\log n)$	$O(n^2)$	$O(n\log n)$	$O(n\log n)$	不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
希尔排序	$O(n\log n)$	$O(ns)$	$O(n)$	$O(1)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
基数排序	$O(N\cdot M)$	$O(N\cdot M)$	$O(N\cdot M)$	$O(M)$	稳定

数据结构
单链表 栈 (插入 删除操作)	$O(1)$
单调栈 单调队列	$O(n)$
KMP	$O(n)$
Trie字符串统计	$O(n)$
并查集 (路径压缩)	$O(n\mathrm{l}\mathrm{o}\mathrm{g}n)$
堆排序	$O(n\mathrm{l}\mathrm{o}\mathrm{g}n)$
模拟散列表	$O(1)$

搜索与图论
排列数字（全排列）	$O(n\cdot n!)$
dfs bfs	$O(n+m)$
Dijkstra	$O(m\mathrm{l}\mathrm{o}\mathrm{g}m)$
Bellman_ford	$O(nm)$
SPFA	$O(nm)$
Floyd	$O(n^3)$
Prim	$O(n^2)$
Kruskal	$O(m\mathrm{l}\mathrm{o}\mathrm{g}m)$
染色法判定二分图	$O(m\mathrm{l}\mathrm{o}\mathrm{g}m)$
匈牙利算法	$O(nm)$

spfa 算法，匈牙利算法，最大流算法时间复杂度理论值很大，但是实际运行速度很快

数学知识
试除法判定质数 分解质因数	$O(\sqrt{n})$
筛质数	$O(n\mathrm{l}\mathrm{o}\mathrm{g}n)$
最大公约数	$O(\mathrm{l}\mathrm{o}\mathrm{g}n)$
快速幂	$O(\mathrm{l}\mathrm{o}\mathrm{g}n)$

动态规划问题的计算量 = 状态数量$\times$状态转移的计算量

动态规划
背包问题	$k$重循环，算法时间复杂度就是$nk$
最长上升子序列 II	$O(n\mathrm{l}\mathrm{o}\mathrm{g}n)$
蒙德里安的梦想	$O(2^{2n}\cdot n)$
没有上司的舞会	$O(nm)$

空间复杂度分析

1 Byte = 8 bit

1 KB = 1024 Byte

1 MB = 1024*1024 Byte

1 GB = 1024 * 1024 * 1024 Byte

int -- 4 Byte

char -- 1 Byte

double, long long  -- 6 Byte

bool -- 1 Byte

$$\begin{array}{rl}64\mathrm{M}\mathrm{B}& =2^{26}\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}\\ \frac{2^{26}\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}}{4\frac{\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}}{\mathrm{i}\mathrm{n}\mathrm{t}}}& =2^{24}\mathrm{i}\mathrm{n}\mathrm{t}\\ & =1.6\times {10}^7\mathrm{i}\mathrm{n}\mathrm{t}\end{array}$$

递归需要消耗空间，快速排序使用了递归，所以空间复杂度是$O(\log n)$

参考

• [1] 由数据范围反推算法复杂度以及算法内容