| 常用算法和数据结构的复杂度 |
| 算法 |
数据结构 |
时间复杂度 |
空间复杂度 |
| |
|
平均 |
最差 |
最差 |
| 深度优先搜索 (DFS) |
Graph of |V| vertices and |E| edges |
- |
O(|E| + |V|) |
O(|V|) |
| 广度优先搜索 (BFS) |
Graph of |V| vertices and |E| edges |
- |
O(|E| + |V|) |
O(|V|) |
| 二分查找 |
Sorted array of n elements |
O(log(n)) |
O(log(n)) |
O(1) |
| 穷举查找 |
Array |
O(n) |
O(n) |
O(1) |
| 最短路径-Dijkstra，用小根堆作为优先队列 |
Graph with |V| vertices and |E| edges |
O((|V| + |E|) log |V|) |
O((|V| + |E|) log |V|) |
O(|V|) |
| 最短路径-Dijkstra，用无序数组作为优先队列 |
Graph with |V| vertices and |E| edges |
O(|V|^2) |
O(|V|^2) |
O(|V|) |
| 最短路径-Bellman-Ford |
Graph with |V| vertices and |E| edges |
O(|V||E|) |
O(|V||E|) |
O(|V|) |
| 排序 |
| 算法 |
数据结构 |
时间复杂度 |
最坏情况下的辅助空间复杂度 |
| 最佳 |
平均 |
最差 |
最差 |
| 快速排序 |
数组 |
O(n log(n)) |
O(n log(n)) |
O(n^2) |
O(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) |
O(n^2) |
O(n^2) |
O(1) |
| 插入排序 |
数组 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
| 选择排序 |
数组 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
| 桶排序 |
数组 |
O(n+k) |
O(n+k) |
O(n^2) |
O(nk) |
| 基数排序 |
数组 |
O(nk) |
O(nk) |
O(nk) |
O(n+k) |
| 数据结构 |
| 数据结构 |
时间复杂度 |
空间复杂度 |
| |
平均 |
最差 |
最差 |
| |
索引 |
查找 |
插入 |
删除 |
索引 |
查找 |
插入 |
删除 |
| 基本数组 |
O(1) |
O(n) |
- |
- |
O(1) |
O(n) |
- |
- |
O(n) |
| 动态数组 |
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| 单链表 |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| 双链表 |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| 跳表 |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
| 哈希表 |
- |
O(1) |
O(1) |
O(1) |
- |
O(n) |
O(n) |
O(n) |
O(n) |
| 二叉搜索树 |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| 笛卡尔树 |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
O(n) |
O(n) |
O(n) |
O(n) |
| B-树 |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| 红黑树 |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| 伸展树 |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| AVL 树 |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| 堆 |
| Heaps |
时间复杂度 |
| |
建堆 |
查找最大值 |
提取最大值 |
Increase Key |
插入 |
删除 |
合并 |
| 链表（已排序） |
- |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(m+n) |
| 链表（未排序） |
- |
O(n) |
O(n) |
O(1) |
O(1) |
O(1) |
O(1) |
| 二叉堆 |
O(n) |
O(1) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(m+n) |
| 二项堆 |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
| 斐波那契堆 |
- |
O(1) |
O(log(n))* |
O(1)* |
O(1) |
O(log(n))* |
O(1) |
| 图 |
|
|
| 节点 / 边 管理 |
Storage |
Add Vertex |
Add Edge |
Remove Vertex |
Remove Edge |
Query |
| 邻接表 |
O(|V|+|E|) |
O(1) |
O(1) |
O(|V| + |E|) |
O(|E|) |
O(|V|) |
| 关联表 |
O(|V|+|E|) |
O(1) |
O(1) |
O(|E|) |
O(|E|) |
O(|E|) |
| 邻接矩阵 |
O(|V|^2) |
O(|V|^2) |
O(1) |
O(|V|^2) |
O(1) |
O(1) |
| 关联矩阵 |
O(|V| ⋅ |E|) |
O(|V| ⋅ |E|) |
O(|V| ⋅ |E|) |
O(|V| ⋅ |E|) |
O(|V| ⋅ |E|) |
O(|E|) |
