面试笔记 - 常见数据结构时间复杂度
时间复杂度
数组
- 添加：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(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) |
上一篇
下一篇
