13 · 复杂度速查表
快速参考数据结构和算法的时空复杂度。
面试中能分析复杂度是基本要求，也是优化思路的来源。
一、数据结构复杂度
| 数据结构 | 查找 | 插入 | 删除 | 随机访问 | 空间 |
|---|
| 数组 | O(n) | O(n) | O(n) | O(1) | O(n) |
| 有序数组 | O(log n) | O(n) | O(n) | O(1) | O(n) |
| 链表 | O(n) | O(1) | O(1) | O(n) | O(n) |
| 哈希表 | O(1) 平均 | O(1) 平均 | O(1) 平均 | — | O(n) |
| 栈 | — | O(1) | O(1) | — | O(n) |
| 队列 | — | O(1) | O(1) | — | O(n) |
| 二叉搜索树 | O(log n) 平均 | O(log n) 平均 | O(log n) 平均 | — | O(n) |
| 堆 | O(n) 建堆 | O(log n) | O(log n) | — | O(n) |
| Trie | O(k) | O(k) | O(k) | — | O(n×k) |
注： k 表示字符串长度或树的深度
二、排序算法复杂度
| 算法 | 平均时间 | 最坏时间 | 最好时间 | 空间 | 稳定 |
|---|
| 冒泡排序 | 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(n log n) | O(log n) | 否 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(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) | 是 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | O(n) | 是 |
三、算法思想复杂度速查
| 算法思想 | 典型场景 | 时间复杂度 | 空间复杂度 |
|---|
| 双指针 | 有序数组、链表 | O(n) | O(1) |
| 滑动窗口 | 子串/子数组 | O(n) | O(k) |
| 二分查找 | 有序数据 | O(log n) | O(1) |
| 回溯 | 排列、组合、子集 | O(指数级) | O(n) |
| 动态规划 | 最优化问题 | O(n)~O(n²)~O(n³) | 可优化 |
| 贪心 | 局部最优=全局最优 | O(n)~O(n log n) | O(1)~O(n) |
| DFS | 树/图/网格 | O(V+E) | O(V) |
| BFS | 最短路径、层序 | O(V+E) | O(V) |
| 拓扑排序 | 有向无环图 | O(V+E) | O(V) |
| 并查集 | 连通性 | O(α(n)) 近乎 O(1) | O(n) |
四、Python 常用操作复杂度
| 操作 | 时间复杂度 |
|---|
list.append(x) | O(1) 摊还 |
list.pop() | O(1) |
list.pop(i) | O(n) |
list.insert(i, x) | O(n) |
x in list | O(n) |
dict[key] / set.add | O(1) 平均 |
x in dict / x in set | O(1) 平均 |
len(obj) | O(1) |
sorted(list) | O(n log n) |
list.sort() | O(n log n) |
min(list) / max(list) | O(n) |
slicing list[i:j] | O(k)，k 为切片长度 |
str1 + str2 | O(n + m) |
', '.join(list) | O(n) |
五、数据量 → 允许的算法复杂度
| 数据规模 | 允许的复杂度 | 可选算法 |
|---|
| n ≤ 10 | O(n!) | 全排列暴力枚举 |
| n ≤ 20 | O(2ⁿ) | 子集枚举、状态压缩 |
| n ≤ 100 | O(n³) | Floyd、三重循环 DP |
| n ≤ 10³ | O(n²) | 双重循环 DP、朴素匹配 |
| n ≤ 10⁵ | O(n log n) | 排序、二分、分治 |
| n ≤ 10⁶ | O(n) | 线性扫描、哈希表 |
| n ≤ 10⁷ | O(n log n) | 注意常数因子 |
| n ≤ 10⁸ | O(n) | 需要极高效实现 |
| n > 10⁸ | O(log n) 或 O(1) | 数学公式、二分 |
面试中的经验法则
| 数据范围 | 算法方向 |
|---|
| n ≤ 100 | O(n³) 没问题，考虑 DP |
| n ≤ 1000 | O(n²) 可接受 |
| n ≤ 10⁵ | O(n log n) 是安全的，考虑排序/二分 |
| n ≤ 10⁶ | O(n) 线性算法 |
| n > 10⁶ | O(n log n) 也要谨慎 |
六、常见复杂度增长对比
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
n=10: 1 < 3 < 10 < 33 < 100 < 1024 < 3.6M
n=100: 1 < 7 < 100 < 664 < 10K < 1.3e30 < 9.3e157
n=1000: 1 < 10 < 1000 < 9966 < 1M < 很恐怖
n=10⁵: 1 < 17 < 100K < 1.7M < 10^10 < 不可能
面试要点： 能写出 O(n log n) 的算法通常就算合格，O(n²) 需要能分析出来并尝试优化。
七、参考