复杂度速查表
所有数据结构的 Big O 时间复杂度与空间复杂度速查。
线性结构
| 结构 | 访问 | 搜索 | 插入 | 删除 | 空间 |
|---|---|---|---|---|---|
| 数组 Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| 栈 Stack | O(n) | O(n) | O(1)¹ | O(1)¹ | O(n) |
| 队列 Queue | O(n) | O(n) | O(1)¹ | O(1)¹ | O(n) |
| 优先级队列 | O(n) | O(n) | O(n) | O(1)¹ | O(n) |
| 双端队列 Deque | O(n) | O(n) | O(1)² | O(1)² | O(n) |
| 循环队列 | O(1) | O(n) | O(1) | O(1) | O(n) |
¹ 仅在端点操作。² 两端均可。
链式结构
| 结构 | 访问 | 搜索 | 插入 | 删除 | 空间 |
|---|---|---|---|---|---|
| 单向链表 | O(n) | O(n) | O(1)¹ | O(n) | O(n) |
| 双向链表 | O(n) | O(n) | O(1)¹ | O(1)² | O(n) |
| 跳表 | O(log n)³ | O(log n)³ | O(log n)³ | O(log n)³ | O(n log n) |
³ 平均情况，最差 O(n)。
散列与集合
| 结构 | 搜索 | 插入 | 删除 | 空间 |
|---|---|---|---|---|
| 字典/Map | O(1)¹ | O(1)¹ | O(1)¹ | O(n) |
| 集合/Set | O(1)¹ | O(1)¹ | O(1)¹ | O(n) |
| 哈希表 | O(1)¹ | O(1)¹ | O(1)¹ | O(n) |
| 布隆过滤器 | O(k)² | O(k) | O(m) |
¹ 平均 O(1)，最差 O(n)。² k = 哈希函数数量。
树
| 结构 | 搜索 | 插入 | 删除 | 空间 |
|---|---|---|---|---|
| BST（平衡） | O(log n) | O(log n) | O(log n) | O(n) |
| BST（倾斜） | O(n) | O(n) | O(n) | O(n) |
| AVL 树 | 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) |
¹ 堆不用于通用搜索，
peek()是 O(1)。² 提取最值是 O(log n)。³ k = 键长度。
图
| 表示方式 | 查边 | 遍历邻居 | 加顶点 | 加边 | 空间 |
|---|---|---|---|---|---|
| 邻接矩阵 | O(1) | O(V) | O(V²) | O(1) | O(V²) |
| 邻接表 | O(度数) | O(度数) | O(1) | O(1) | O(V+E) |
缓存
| 结构 | Get | Put | 淘汰 | 空间 |
|---|---|---|---|---|
| LRU 缓存 | O(1) | O(1) | O(1) | O(capacity) |
其他
| 结构 | 合并 | 查找 | 连通 | 空间 |
|---|---|---|---|---|
| 并查集 | O(α(n)) | O(α(n)) | O(α(n)) | O(n) |
α(n) = 反阿克曼函数 — 实际使用中相当于 O(1)。
** 速记**
- O(1) → 常数时间。最佳。哈希查找、数组索引。
- O(log n) → 非常快。二分搜索、树操作。
- O(n) → 线性。单次遍历。
- O(n log n) → 高效排序（归并排序、快速排序）。
- O(n²) → 平方。嵌套循环。大数据集避免。