分析方法

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

一般法

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

主定理 (Master Theorem)

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

＋

那么

均摊复杂度

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

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

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

势能分析

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

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

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

假设存在从状态到数的函数 ，且对于任何状态 ，，则有以下推论：

设 为从 开始连续做 次操作所得的状态序列， 为第 次操作的时间开销。

记 ，则 次操作的总时间花销为

（正负相消，证明显然）

又因为 ，所以有

因此，若 ，则 是均摊复杂度的一个上界。

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

应用

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

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

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

一些算法的复杂度

基础算法
快速排序 归并排序 二分
双指针 数组元素目标和
排序算法
平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 稳定
直接选择排序 不稳定
直接插入排序 稳定
快速排序 不稳定
堆排序 不稳定
希尔排序 不稳定
归并排序 稳定
计数排序 稳定
基数排序 稳定
数据结构
单链表 栈 (插入 删除操作)
单调栈 单调队列
KMP
Trie字符串统计
并查集 (路径压缩)
堆排序
模拟散列表
搜索与图论
排列数字（全排列）
dfs bfs
Dijkstra
Bellman_ford
SPFA
Floyd
Prim
Kruskal
染色法判定二分图
匈牙利算法

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

数学知识
试除法判定质数 分解质因数
筛质数
最大公约数
快速幂

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

动态规划
背包问题 重循环，算法时间复杂度就是
最长上升子序列 II
蒙德里安的梦想
没有上司的舞会

空间复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

递归需要消耗空间，快速排序使用了递归，所以空间复杂度是

参考