第三章数据结构
图
- 邻接矩阵创建无向图：时间复杂度/空间复杂度O(
)
- 邻接表创建无向图：时间复杂度O(n+e)
- 拓扑排序：时间复杂度为O(n+e)
- 构造最小生成树的算法
- 普里姆算法：适合求稠密网的最小生成树
- 克鲁斯卡尔算法：适合求稀疏网的最小生成树。
- 求最短路径的算法
- 迪杰斯特拉算法用于求源点到各顶点的最短路径
- 弗洛供德算法用于求每一对顶点之间的最短路径。
查找
折半查找（二分查找）的时间复杂度为 O ()
查找方法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 |
| 顺序查找（线性查找） | O(n) | O(n) | O(1) |
| 二分查找（有序数组） | O(log n) | O(log n) | O(1) |
| 哈希查找（理想情况） | O(1) | O(n)(冲突时) | O(1) |
| 二叉搜索树查找 | O(log n)（平衡时） | O(n)（退化时） | O(1) |
| 平衡二叉搜索树查找 | O(log n) | O(log n) | O(1) |
| B树查找 | O(log n) | O(log n) | O(1) |
| B+树查找 | O(log n) | O(log n) | O(1) |
排序
| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
直接插入排序 | 稳定 | ||||
| 冒泡排序 | 稳定 | ||||
| 简单选择排序 | 不稳定 | ||||
| 希尔排序 | 不稳定 | ||||
| 快速排序 | 不稳定 | ||||
| 堆排序 | 不稳定 | ||||
| 归并排序 | 稳定 |
复杂度
常见复杂度
- 常数阶 O(1)：操作次数固定，与输入规模无关
- 线性阶 O(n)：操作次数与 n 成正比
- 对数阶 O(logn)：每次操作将问题规模减半（如二分查找）
- 平方阶 O(n2)：嵌套循环，操作次数与 n2 成正比
- 指数阶 O(2n)：递归调用次数随 n 指数增长（如斐波那契数列递归解法）
层级关系
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)
