⚡ 复杂度速查表
面试必背。重点是:为什么是这个复杂度,能现场推导。
常用数据结构操作复杂度(平均)
| 数据结构 |
查找 |
插入 |
删除 |
备注 |
| 数组(按索引) |
O(1) |
O(n) |
O(n) |
顺序访问快 |
| 有序数组(二分) |
O(log n) |
O(n) |
O(n) |
插入/删除要移动 |
| 链表 |
O(n) |
O(1)* |
O(1)* |
*已知节点位置时 |
| 双向链表 |
O(n) |
O(1) |
O(1) |
LRU 的基础 |
| 栈 / 队列 |
O(1)(顶/端) |
O(1) |
O(1) |
— |
| 哈希表 |
O(1) |
O(1) |
O(1) |
最坏 O(n)(冲突) |
| 二叉搜索树(平衡) |
O(log n) |
O(log n) |
O(log n) |
AVL/红黑树 |
| 堆 |
O(1) 取最值 |
O(log n) |
O(log n) |
Top-K 神器 |
| 并查集 |
≈O(α(n)) |
— |
— |
α(n) 近似常数 |
| Trie |
O(len) |
O(len) |
O(len) |
字符串前缀查询 |
排序算法对比
| 算法 |
平均 |
最坏 |
空间 |
稳定性 |
备注 |
| 冒泡排序 |
O(n²) |
O(n²) |
O(1) |
稳定 |
实际不用 |
| 选择排序 |
O(n²) |
O(n²) |
O(1) |
不稳定 |
交换次数少 |
| 插入排序 |
O(n²) |
O(n²) |
O(1) |
稳定 |
近乎有序时快 |
| 希尔排序 |
O(n^1.3) |
O(n²) |
O(1) |
不稳定 |
插入排序改进 |
| 归并排序 |
O(n log n) |
O(n log n) |
O(n) |
稳定 |
外部排序基础 |
| 快速排序 |
O(n log n) |
O(n²) |
O(log n) |
不稳定 |
随机 pivot 规避最坏 |
| 堆排序 |
O(n log n) |
O(n log n) |
O(1) |
不稳定 |
原地 Top-K |
| 计数排序 |
O(n+k) |
O(n+k) |
O(k) |
稳定 |
值域小 |
| 桶排序 |
O(n) |
O(n²) |
O(n) |
稳定 |
分布均匀时 |
| 基数排序 |
O(d·(n+k)) |
O(d·(n+k)) |
O(n+k) |
稳定 |
按位排 |
背口诀:快排不稳、堆排不稳、选择不稳;归并稳定但空间 O(n);希尔/快排/堆排平均都是 O(n log n)。
常见算法复杂度
| 算法 |
时间复杂度 |
说明 |
| 二分查找 |
O(log n) |
有序数组 |
| DFS / BFS(图) |
O(V + E) |
邻接表 |
| Dijkstra |
O((V+E) log V) |
堆优化 |
| Floyd |
O(V³) |
全源最短路 |
| Kruskal |
O(E log E) |
并查集 |
| Prim |
O(E log V) |
堆优化 |
| 快排分治 / 归并 |
O(n log n) |
— |
| DP(背包) |
O(n·W) |
伪多项式 |
| 回溯(全排列) |
O(n!) |
剪枝可优化 |
复杂度增长对比(n = 10⁶ 时)
O(1) < 10⁻⁹ s 级 常数
O(log n) ≈ 20 步 二分
O(n) ≈ 1e6 步 一次扫描
O(n log n)≈ 2e7 步 排序
O(n²) ≈ 1e12 步 勉强(10⁴ 上限)
O(2ⁿ) ≈ 天文数字 n 上限 ~25
O(n!) ≈ 更夸张 n 上限 ~10
刷题自查
- [ ] 能背出表并解释"为什么归并稳定而快排不稳定"
- [ ] 能推导二分、快排、堆排的复杂度
- [ ] 看到题能 30 秒内判断数据规模 → 允许的复杂度 → 该用哪个算法
教程来源:Akun-python/autumn-recruitment。
MIT 许可证全文。