时间复杂度梳理

⚠️ 符号说明

• : 问题规模（数组长度、物品数量、节点数量等）。

• : 第二个序列长度（LCS）或 颜色数量（m着色）。

• : 背包容量。

• : 图的顶点数 (Vertices)。

• : 图的边数 (Edges)。

---

第一部分：递归与分治 (第2章)

这一章的重点在于“如何切分问题”。

算法名称	最好情况	最坏情况	平均情况	备注/关键点
二分搜索	(中间就是要找的)			必须是有序数组
合并排序				稳定，但需 额外空间
快速排序		(数组已有序/逆序)		原地排序，不稳定，常数项小
线性时间选择		(Pivot选得烂)		找第 小元素

---

第二部分：动态规划 (第3章)

DP 的复杂度通常 = 状态数量 × 状态转移花费。

(DP算法通常由输入规模决定计算量，因此最好/最坏/平均通常是一样的，除非有特殊剪枝)。

算法名称	时间复杂度 (统一)	空间复杂度	备注/关键点
矩阵连乘			三层循环 ()
最长公共子序列 (LCS)			填满 的二维表
最大子段和			扫描一遍即可 (Kadane算法)
0-1 背包 (DP版)			伪多项式时间 (取决于容量 )

---

第三部分：贪心法 (第4章)

贪心法的时间主要消耗在排序上（除了 Dijkstra）。

算法名称	时间复杂度	关键步骤	备注
活动安排		排序 + 遍历	按结束时间排序
最优装载		排序 + 遍历	按重量从小到大排序
分数背包		排序 + 遍历	按性价比 () 排序
Dijkstra (数组版)		每次遍历节点找最小值	适合稠密图 (边多)
Dijkstra (堆优化)		堆操作每次	适合稀疏图 (边少)

---

第四部分：回溯法 (第5章)

回溯法是暴力搜索的优化，最坏复杂度取决于解空间树的叶子节点数量。

(最好情况通常是很快找到第一个解或第一层就被剪枝，很难量化，考试主要考最坏情况)。

算法名称	解空间树类型	最坏时间复杂度	备注
n 皇后问题	排列树		搜所有排列
TSP (旅行商)	排列树		搜所有路径排列
0-1 背包 (回溯版)	子集树		选或不选，深度
图的 m 着色	m 叉树		每个节点试 种色

---

💡 考试速记口诀

1. 最坏会退化的： 快速排序 ()、线性时间选择 ()。

2. 雷打不动的 ： 合并排序。

3. 两个背包的区别：

   • 0-1 背包 (DP): (看容量)。

   • 0-1 背包 (回溯): (看数量)。

   • 分数背包 (贪心): (看排序)。

4. Dijkstra： 稠密图用数组 ，稀疏图用堆 。

5. 回溯法： 全排列问题是 ，选不选问题是 。