复杂度对比总表
线性表操作
| 操作 | 顺序表 | 单链表 |
|---|---|---|
| 按位查找 | O(1) | O(n) |
| 按值查找 | O(n) | O(n) |
| 已知位置插入 | O(n) | O(1)，已知前驱 |
| 已知位置删除 | O(n) | O(1)，已知前驱 |
栈与队列
| 结构 | 入栈/入队 | 出栈/出队 | 取栈顶/队头 |
|---|---|---|---|
| 顺序栈 | O(1) | O(1) | O(1) |
| 链栈 | O(1) | O(1) | O(1) |
| 顺序循环队列 | O(1) | O(1) | O(1) |
| 链队列 | O(1) | O(1) | O(1) |
树与查找结构
| 结构 | 平均查找 | 最坏查找 | 备注 |
|---|---|---|---|
| 顺序查找 | O(n) | O(n) | 无序表 |
| 折半查找 | O(log n) | O(log n) | 有序顺序表 |
| BST | O(log n) | O(n) | 极端退化成链 |
| AVL | O(log n) | O(log n) | 严格平衡 |
| 散列表 | O(1) | O(n) | 受装填因子影响 |
图算法
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| BFS | O(V + E) 邻接表 | 无权最短路、层次遍历 |
| DFS | O(V + E) 邻接表 | 连通性、遍历、回溯 |
| Prim | O(V^2) 邻接矩阵 | 稠密图最小生成树 |
| Kruskal | O(E log E) | 稀疏图最小生成树 |
| Dijkstra | O(V^2) 或 O((V+E)logV) | 单源最短路，非负权 |
| Floyd | O(V^3) | 多源最短路 |
| Topo Sort | O(V + E) | DAG 拓扑序 |
排序算法
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | O(n^2) | O(n^2) | O(1) | 稳定 |
| 冒泡 | O(n^2) | O(n^2) | O(1) | 稳定 |
| 简单选择 | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔 | 依增量而定 | 通常写 O(n^2) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n^2) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 |
最常被问的三类比较
1. BST vs AVL
- BST 平均快，但最坏会退化。
- AVL 始终保持
O(log n)，但插删要调整。
2. 邻接矩阵 vs 邻接表
- 邻接矩阵判边快，适合稠密图。
- 邻接表省空间，适合稀疏图。
3. 快排 vs 归并
- 快排常数小、平均快、原地，但最坏可能退化且不稳定。
- 归并稳定、时间稳，但要额外空间。