算法期末复习

这份《算法期末考前 1 小时极速救命清单》专为你在考场外走廊上、或者发卷前最后 10 分钟冲刺记忆而设计。

虽然是“小清单”，但字字珠玑，浓缩了全部 10 章的计算公式、必考归类、状态转移方程和简答题万能话术。请务必把这些内容刻在脑子里！

---

🧮 模块一：必考公式与极限速查（选择/计算题）

1. 增长阶数排名（从小到大）

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

• 极限判定法：$\lim_{n \to \infty} \frac{T(n)}{g(n)}$
  • 结果 $= 0 \Rightarrow T(n) \in O(g(n))$ (上界)
  • 结果 $= C > 0 \Rightarrow T(n) \in \Theta(g(n))$ (同阶)
  • 结果 $= \infty \Rightarrow T(n) \in \Omega(g(n))$ (下界)
• 避坑提示：$(n-1)! \in o(n!)$（因为极限为0）；$\log_2 n \in \Theta(\log_3 n)$（对数换底只是常数倍，同阶）。

2. 👑 主定理 (Master Theorem) - 专解分治法

针对递推式：$T(n) = aT(n/b) + \Theta(n^k)$ 先算出 $b^k$，然后与 $a$ 比较：

1. 如果 $a < b^k \Rightarrow T(n) = \Theta(n^k)$ （合并代价占主导）
2. 如果 $a = b^k \Rightarrow T(n) = \Theta(n^k \log n)$ （完美平衡）
3. 如果 $a > b^k \Rightarrow T(n) = \Theta(n^{\log_b a})$ （子问题裂变占主导）
   • 特例注意：如果是 $T(n) = 2T(n-1)+1$ 这种减一递归，绝对不能用主定理，它是等比数列，结果是 $\Theta(2^n)$。

---

🏷️ 模块二：算法“流派”归类表（选择题防坑大杀器）

老师录音原话：“你必须知道这个算法属于哪一类！”

算法名称	归属流派	时间复杂度	备注 / 坑点
Karatsuba (大整数)	分治法	$O(n^{1.585})$	把4次乘法降到3次
Strassen (矩阵乘法)	分治法	$O(n^{2.807})$	把8次乘法降到7次
二分查找 / 快幂 / 假币	减治法	$O(\log n)$	千万别选分治！它不需要合并子解。
霍纳法则 (Horner’s)	变治法	$O(n)$	改变表现形式，多项式求值。
堆 / 堆排序	变治法	$O(n \log n)$	数组转换为完全二叉树结构。
高斯消去法	变治法	$O(n^3)$	实例化简，化为上三角矩阵。
Kruskal / Prim / Dijkstra	贪心算法	-	注意Dijkstra不能有负权边！
分数背包	贪心算法	$O(n \log n)$	0-1背包绝对不能用贪心！

---

🧩 模块三：动态规划 (DP) 状态转移方程库（应用大题/填空）

如果考大题，即使填表填错了，只要写出以下状态转移方程，过程分就能拿一大半！

1. 0-1 背包问题
   • $V[i, j] = \max(V[i-1, j], V[i-1, j-w_i] + v_i)$
   • (解释：不拿 vs 腾出 $w_i$ 空间拿第 $i$ 个，取最大值)
2. 矩阵链乘法 (Matrix Chain)
   • $m[i,j] = \min_{i \le k < j} {m[i,k] + m[k+1,j] + p_{i-1}p_kp_j}$
   • (解释：在 $k$ 处劈开，左半代价 + 右半代价 + 最后合并的标量乘法代价)
3. 最长公共子序列 (LCS)
   • 若 $x_i = y_j$：$C[i,j] = C[i-1, j-1] + 1$
   • 若 $x_i \ne y_j$：$C[i,j] = \max(C[i-1, j], C[i, j-1])$
4. Floyd 算法 (多源最短路径)
   • $D^{(k)}{ij} = \min(D^{(k-1)}{ij}, D^{(k-1)}{ik} + D^{(k-1)}{kj})$
   • (避坑：写代码或伪代码时，中转点 $k$ 的循环必须在最外层！)
5. 扔鸡蛋问题 (作业高阶拓展)
   • $f(n,m) = 1 + \min_{1 \le h \le n}(\max(f(h-1, m-1), f(n-h, m)))$

---

🗺️ 模块四：分支限界法 (B&B) 画树计算指南（应用大题核心）

如果大题考分支限界，一定会让你画解空间树，并计算上下界！

• 分支限界的原则：优先队列（最佳优先），算界，剪枝。

【套路 1】0-1背包的分支限界（找最大，算上限 Upper Bound）

1. 必做第一步：将物品按价值密度 $v/w$ 从大到小降序排列！
2. 公式：ub = 当前已装总价值 v + 剩余容量 * 剩下物品里的最高密度
3. 剪枝：如果一个节点的 ub $\le$ 目前已知的某条真实路线的价值，直接剪掉（打 $\times$）。

【套路 2】TSP 旅行商的分支限界（找最短，算下限 Lower Bound）

1. 公式：lb = 已经走过的确切距离 + 剩余未走城市的理论最短出入边之和
2. 操作：假设还没走的城市，每次都能神奇地挑到距离最短的两条边相连。算出的这个保底距离，如果比目前已知的随便一条完整路径还要长，直接剪掉。

---

🎤 模块五：简答题万能话术（防扣分神器）

老师强调：“简答题不要写小作文，答关键点！” 直接把以下对比默写上去：

1. 分治法 (Divide & Conquer) vs 减治法 (Decrease & Conquer)

• 分治法：划分为多个子问题，所有子问题都要解决，并且必须合并 (Combine) 子问题的解。（如：归并排序）
• 减治法：把问题规模缩小，通常只导向一个子问题，得出子问题的解后原问题即得解，不需要合并。（如：二分查找）

2. 动态规划 (DP) vs 贪心算法 (Greedy)

• 前提：DP需要“最优子结构”和“重叠子问题”；贪心只需“贪心选择性质”。
• 决策：DP 是自底向上，统揽全局，当前决策必须依赖子问题的最优解；贪心是自顶向下，只顾眼前局部最优，一旦选择不可撤销，不依赖子问题。
• 结果：DP 保证全局最优解；贪心不一定能得全局最优解（如0-1背包）。

3. 回溯法 (Backtracking) vs 分支限界法 (Branch & Bound)

• 目标：回溯法找所有解或一个解；分支限界法专找最优解。
• 搜索方式：回溯法是 DFS (深度优先)；分支限界是 BFS (广度优先) 或 优先队列 (最佳优先)。
• 空间消耗：回溯法空间极小 $O(h(n))$（内存受限时首选）；分支限界法需要维护大队列，空间消耗极大。

4. 算法 (Algorithm) vs 程序 (Program)

• 核心区别：算法具有有穷性，必须在有限步内结束；程序可以无限执行（如操作系统 Operating System 就不是算法，是程序）。

---

深呼吸！ 带着这套清单进考场，先秒选择题，再写简答题，最后留足 60 分钟画树填表攻克应用题。祝你下笔如有神，满分通关！💯