速查：数据结构全书复杂度总表
速查表：全书复杂度汇总。1.2.2 的推导方法与 6 道复杂度真题见 1.2 算法和算法评价；第 5~8 章的完整复杂度见各章名词库。
渐进符号（1.2.2）
| 符号 | 含义 |
|---|
| 渐进上界：存在正常数 和 ，当 时 |
| 渐进下界 |
| 同时是上界和下界 |
常见量级由小到大：
空间复杂度指算法所需的辅助空间，不含输入数据本身占的空间。递归算法的空间复杂度通常是递归深度。
查找（第 7 章）
| 方法 | | | 时间 |
|---|
| 一般顺序查找 | | | |
| 有序线性表顺序查找 | | | |
| 折半查找 | | 判定树上数到父结点 | |
| 分块查找 | ，最优 | — | |
| 二叉排序树 | 平均 | 最坏 | 最坏 |
| 平衡二叉树 | — | — | |
| B 树 | — | — | 层次数决定磁盘存取次数 |
| 散列表 | | | 理想 |
分母三件套：成功除 ，不成功除失败结点数（散列表除值域大小 ），装填因子除表长 。
排序（第 8 章，表 8.1）
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 |
|---|
| 直接插入排序 | | | | | 是 |
| 冒泡排序 | | | | | 是 |
| 简单选择排序 | | | | | 否 |
| 希尔排序 | — | — | — | | 否 |
| 快速排序 | | | | | 否 |
| 堆排序 | | | | | 否 |
| 二路归并排序 | | | | | 是 |
| 基数排序 | | | | | 是 |
希尔那三格是空的（教材：依赖增量函数，无法准确给出）。空间列只写平均（快排最坏 ）。
图（第 6 章）
| 操作 | 邻接矩阵 | 邻接表 |
|---|
| BFS / DFS | | |
| 拓扑排序 | | |
| 空间 | | 无向 / 有向 |
| 算法 | 时间 |
|---|
| Prim | （与边数无关，适合稠密图） |
| Kruskal | （适合稀疏图） |
| Dijkstra | |
| Floyd | |
树（第 5 章）
| 结构 | 结论 |
|---|
| 二叉树 | ；第 层至多 ；高 至多 |
| 完全二叉树 | 高度 |
| 二叉链表 | 空链域 |
| 哈夫曼树 | 结点总数 ， |
| 并查集 | Find 、Union ；按大小合并后深度 |
| 遍历 | 时间 、空间 |
线性结构（第 2~3 章）
| 操作 | 顺序表 | 链表 |
|---|
| 按序号查找 | （随机存取） | |
| 按值查找（无序） | | |
| 按值查找（有序） | （折半） | |
| 插入 / 删除 | （平均移动半个表长） | （已定位时，只改指针） |
链接