时间复杂度
数组
- 添加：O(1)
- 删除：O(n）
- 修改：O(1)
- 查询：O(n)
- 尺寸：O(1)
链表
- 插入：O(1)，如果需要查找再插入则O(n)
- 删除：O(1)，如果需要查找再删除则O(n)
- 搜索：O(n)
栈
- 推：O（1）
- Pop：O（1）
- 上：O（1）
- 搜索（像查找，像一个特殊的操作）：O（n）
队列
- 插入：O（1）
- 删除：O（1）
- 尺寸：O（1）
排序
| 算法 | 最佳 | 平均 | 最差 | 最差情况下的空间复杂度 |
|---|---|---|---|---|
| 快速排序 | O(nlogn) | O(nlogn) | O(n*n) | O(n) |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) |
| 冒泡排序 | O(n) | O(n*n) | O(n*n) | O(1) |
| 插入排序 | O(n) | O(n*n) | O(n*n) | O(1) |
| 选择排序 | O(n*n) | O(n*n) | O(n*n) | O(1) |
| 桶排序 | O(n+k) | O(n+k) | O(n*n) | O(nk) |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n+k) |
搜索
| 算法 | 平均 | 最差 | 最差空间复杂度 |
|---|---|---|---|
| 深度优先搜索(DFS) | - | O(E+V) | O(V) |
| 广度优先搜索(BFS) | - | O(E+V) | O(V) |
| 二分查找 | O(logn) | O(logn) | O(1) |
网友评论