速查表：常用算法和数据结构的复杂度
常用算法和数据结构的复杂度速查表，
搜索
| 算法 | 数据结构 | 时间复杂度 | 空间复杂度 | |||
|---|---|---|---|---|---|---|
| 平均 | 最差 | 最差 | ||||
| 深度优先搜索 (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|) |
本文由用户 jopen 自行上传分享，仅供网友学习交流。所有权归原作者，若您的权利被侵害，请联系管理员。
转载本站原创文章，请注明出处，并保留原始链接、图片水印。
本站是一个以用户分享为主的开源技术平台，欢迎各类分享！