第 05 课2 小时
算法
排序、查找、动态规划、贪心等高频算法。
| O(1) |
| 不稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n) | O(n) | O(m) | 稳定 |
| 基数排序 | O(k*n) | O(n2) | 稳定 |
- 均按从小到大排列
- k：代表数值中的 “数位” 个数
- n：代表数据规模
- m：代表数据的最大值减最小值
- 来自：wikipedia . 排序算法
| 查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 |
|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无序或有序 |
| 二分查找（折半查找） | O(log2n) | O(1) | 有序 |
| 插值查找 | O(log2(log2n)) | O(1) | 有序 |
| 斐波那契查找 | O(log2n) | O(1) | 有序 |
| 哈希查找 | O(1) | O(n) | 无序或有序 |
| 二叉查找树（二叉搜索树查找） | O(log2n) | ||
| 红黑树 | O(log2n) | ||
| 2-3树 | O(log2n - log3n) | ||
| B树/B+树 | O(log2n) |
| 图搜索算法 | 数据结构 | 遍历时间复杂度 | 空间复杂度 |
|---|---|---|---|
| BFS广度优先搜索 | 邻接矩阵 邻接链表 | O(|v|2) O(|v|+|E|) | O(|v|2) O(|v|+|E|) |
| DFS深度优先搜索 | 邻接矩阵 邻接链表 | O(|v|2) O(|v|+|E|) | O(|v|2) O(|v|+|E|) |