搜索算法(来源)
| 算法 | 数据结构 | 时间复杂度 | 空间复杂度 | |||
|---|---|---|---|---|---|---|
| 平均 | 最差 | 最差 | ||||
| 深度优先搜索 | 图G(V,E), V为顶点集, E为边集 | - |
O(|E| + |V|) |
O(|V|) |
||
| 广度优先搜索 | 图G(V,E), V为顶点集, E为边集 | - |
O(|E| + |V|) |
O(|V|) |
||
| 二分搜索 | n元已排数组 | O(log(n)) |
O(log(n)) |
O(1) |
||
| 线性搜索(暴力法) | 数组 | O(n) |
O(n) |
O(1) |
||
| Dijkstra最短路径算法(最小堆作为优先队列) | 图G(V,E), V为顶点集, E为边集 | O((|V| + |E|) log |V|) |
O((|V| + |E|) log |V|) |
O(|V|) |
||
| Dijkstra最短路径算法(未排数组作为优先队列) | 图G(V,E), V为顶点集, E为边集 | O(|V|^2) |
O(|V|^2) |
O(|V|) |
||
| Bellman-Ford最短路径算法 | 图G(V,E), V为顶点集, E为边集 | O(|V||E|) |
O(|V||E|) |
O(|V|) |
||
排序算法(来源)
| 算法 | 数据结构 | 时间复杂度 | 辅助空间复杂度 | ||||
|---|---|---|---|---|---|---|---|
| 最优 | 平均 | 最差 | 最差 | ||||
| 快速排序 | 数组 | O(n log(n)) |
O(n log(n)) |
O(n^2) |
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) |
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(1) |
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(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(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(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(n) |
堆(来源)
| 堆 | 时间复杂度 | ||||||
|---|---|---|---|---|---|---|---|
| 堆调整 | 最大值查找 | Extract Max | 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(log(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) |
图(来源)
| 表示方法 | 存储 | 增加顶点 | 增加边 | 移除顶点 | 移除边 | 查询 |
|---|---|---|---|---|---|---|
| 邻接表 | O(|V|+|E|) |
O(1) |
O(1) |
O(|V| + |E|) |
O(|E|) |
O(|V|) |
| Incidence list | 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|) |
渐近符号(来源)
| letter | 界限 | growth | 性能 |
|---|---|---|---|
| (theta) Θ | upper and lower, tight | equal | = n |
| (big-oh) O | upper, tightness unknown | less than or equal | ≤ n |
| (small-oh) o | upper, not tight | less than | < n |
| (big omega) Ω | lower, tightness unknown | greater than or equal | ≥ n |
| (small omega) ω | lower, not tight | greater than | > n |
大O复杂度图表(来源)
有C++难题，加我！