演算手稿ALGORITHM NOTES

复杂度手册

COMPLEXITY REFERENCE · 速查

常见数据结构操作常见排序算法图算法递推式推导

常见数据结构操作

同一结构的不同操作复杂度并不对称;均摊复杂度标注了「均摊」。

结构 / 操作最好平均最坏空间适用条件
动态数组 · 按下标访问O(1)O(1)O(1)O(n)内存连续,缓存友好
动态数组 · 尾部追加O(1)O(1) 均摊O(n)O(n)扩容时整体搬迁
动态数组 · 中间插入 / 删除O(1)O(n)O(n)O(n)需要搬移后续元素
链表 · 头插 / 头删O(1)O(1)O(1)O(n)已知结点位置时 O(1)
链表 · 按下标访问O(1)O(n)O(n)O(n)只能顺序走
哈希表 · 插入 / 查找 / 删除O(1)O(1)O(n)O(n)最坏出现在全体冲突
平衡二叉搜索树 · 插入 / 查找 / 删除O(log n)O(log n)O(log n)O(n)有序遍历、前驱后继
二叉堆 · 取最值O(1)O(1)O(1)O(n)只维护偏序
二叉堆 · 插入 / 弹出O(1)O(log n)O(log n)O(n)自底向上建堆 O(n)
栈 / 队列 · 入 / 出O(1)O(1)O(1)O(n)只操作端部
并查集 · find / unionO(1)O(α(n))O(α(n))O(n)路径压缩 + 按秩合并

动态数组 · 按下标访问

最好/平均/最坏
O(1) / O(1) / O(1)
空间
O(n)
适用
内存连续,缓存友好

动态数组 · 尾部追加

最好/平均/最坏
O(1) / O(1) 均摊 / O(n)
空间
O(n)
适用
扩容时整体搬迁

动态数组 · 中间插入 / 删除

最好/平均/最坏
O(1) / O(n) / O(n)
空间
O(n)
适用
需要搬移后续元素

链表 · 头插 / 头删

最好/平均/最坏
O(1) / O(1) / O(1)
空间
O(n)
适用
已知结点位置时 O(1)

链表 · 按下标访问

最好/平均/最坏
O(1) / O(n) / O(n)
空间
O(n)
适用
只能顺序走

哈希表 · 插入 / 查找 / 删除

最好/平均/最坏
O(1) / O(1) / O(n)
空间
O(n)
适用
最坏出现在全体冲突

平衡二叉搜索树 · 插入 / 查找 / 删除

最好/平均/最坏
O(log n) / O(log n) / O(log n)
空间
O(n)
适用
有序遍历、前驱后继

二叉堆 · 取最值

最好/平均/最坏
O(1) / O(1) / O(1)
空间
O(n)
适用
只维护偏序

二叉堆 · 插入 / 弹出

最好/平均/最坏
O(1) / O(log n) / O(log n)
空间
O(n)
适用
自底向上建堆 O(n)

栈 / 队列 · 入 / 出

最好/平均/最坏
O(1) / O(1) / O(1)
空间
O(n)
适用
只操作端部

并查集 · find / union

最好/平均/最坏
O(1) / O(α(n)) / O(α(n))
空间
O(n)
适用
路径压缩 + 按秩合并

常见排序算法

稳定性指相等元素相对次序是否保持;下表均按升序约定。

算法最好平均最坏空间稳定性适用条件
冒泡排序O(n)O(n²)O(n²)O(1)◎ 稳定提前退出可优化最好情况
选择排序O(n²)O(n²)O(n²)O(1)△ 不稳定交换次数最少,比较次数固定
插入排序O(n)O(n²)O(n²)O(1)◎ 稳定小规模或近乎有序时极快
希尔排序O(n log n)取决于增量O(n²)O(1)△ 不稳定插入排序的分组改进
归并排序O(n log n)O(n log n)O(n log n)O(n)◎ 稳定稳定且性能可预测,适合外排
快速排序O(n log n)O(n log n)O(n²)O(log n)△ 不稳定常数小;需随机化避免最坏
堆排序O(n log n)O(n log n)O(n log n)O(1)△ 不稳定原地且最坏有保证,但缓存不友好
计数排序O(n + k)O(n + k)O(n + k)O(k)◎ 稳定k 为值域大小,仅限整数
基数排序O(d(n + k))O(d(n + k))O(d(n + k))O(n + k)◎ 稳定d 为最大位数,逐位稳定排序

冒泡排序

最好/平均/最坏
O(n) / O(n²) / O(n²)
空间
O(1)
稳定性
◎ 稳定
适用
提前退出可优化最好情况

选择排序

最好/平均/最坏
O(n²) / O(n²) / O(n²)
空间
O(1)
稳定性
△ 不稳定
适用
交换次数最少,比较次数固定

插入排序

最好/平均/最坏
O(n) / O(n²) / O(n²)
空间
O(1)
稳定性
◎ 稳定
适用
小规模或近乎有序时极快

希尔排序

最好/平均/最坏
O(n log n) / 取决于增量 / O(n²)
空间
O(1)
稳定性
△ 不稳定
适用
插入排序的分组改进

归并排序

最好/平均/最坏
O(n log n) / O(n log n) / O(n log n)
空间
O(n)
稳定性
◎ 稳定
适用
稳定且性能可预测,适合外排

快速排序

最好/平均/最坏
O(n log n) / O(n log n) / O(n²)
空间
O(log n)
稳定性
△ 不稳定
适用
常数小;需随机化避免最坏

堆排序

最好/平均/最坏
O(n log n) / O(n log n) / O(n log n)
空间
O(1)
稳定性
△ 不稳定
适用
原地且最坏有保证,但缓存不友好

计数排序

最好/平均/最坏
O(n + k) / O(n + k) / O(n + k)
空间
O(k)
稳定性
◎ 稳定
适用
k 为值域大小,仅限整数

基数排序

最好/平均/最坏
O(d(n + k)) / O(d(n + k)) / O(d(n + k))
空间
O(n + k)
稳定性
◎ 稳定
适用
d 为最大位数,逐位稳定排序

图算法

V 为点数,E 为边数;邻接表存储下的复杂度。

算法时间空间适用条件
广度优先 BFSO(V + E)O(V)无权图最短路、层次遍历
深度优先 DFSO(V + E)O(V)连通性、环检测、割点
拓扑排序(Kahn)O(V + E)O(V)DAG 依赖顺序;可判环
Dijkstra(二叉堆)O((V + E) log V)O(V)单源最短路,要求非负权边
Bellman-FordO(VE)O(V)允许负权边,可检测负环
Floyd-WarshallO(V³)O(V²)多源最短路,点少边密
KruskalO(E log E)O(V)最小生成树,配合并查集
Prim(二叉堆)O(E log V)O(V)最小生成树,适合稠密图

广度优先 BFS

时间
O(V + E)
空间
O(V)
适用
无权图最短路、层次遍历

深度优先 DFS

时间
O(V + E)
空间
O(V)
适用
连通性、环检测、割点

拓扑排序(Kahn)

时间
O(V + E)
空间
O(V)
适用
DAG 依赖顺序;可判环

Dijkstra(二叉堆)

时间
O((V + E) log V)
空间
O(V)
适用
单源最短路,要求非负权边

Bellman-Ford

时间
O(VE)
空间
O(V)
适用
允许负权边,可检测负环

Floyd-Warshall

时间
O(V³)
空间
O(V²)
适用
多源最短路,点少边密

Kruskal

时间
O(E log E)
空间
O(V)
适用
最小生成树,配合并查集

Prim(二叉堆)

时间
O(E log V)
空间
O(V)
适用
最小生成树,适合稠密图

递推式速查与推导

常见递推式的直觉解释;严格工具是递归树与主定理。

  1. 二分查找=

    每轮问题规模减半、只做常数工作,n 轮后规模到 1,共 \log_2 n 轮。

  2. 归并排序=

    递归树每层总工作量 O(n),共 \log_2 n 层,相乘即得主定理 case 2。

  3. 树的遍历=

    每层常数工作摊到 2^k 个结点上仍是 O(1)/层?不——叶子数 O(n) 主导,总代价即结点总数。

  4. 快速排序(最坏)=

    每轮只减少一个元素,第 i 轮工作 n - i,求和 \sum_{i=1}^{n} i = O(n^2)。

  5. 朴素汉诺塔 / 子集枚举=

    递归树的结点数按 2 的幂增长,深度 n,总数 2^n - 1。

  6. 快速选择(平均)=

    每轮线性扫描一次,但只剩一半: n + n/2 + n/4 + \cdots < 2n。