外观
《算法设计与分析》期末突击知识体系
本知识体系是干什么的：把
data/review/期末复习题汇总.md里的历年原题，拆成一套"从零基础也能看懂、能照着做对"的复习资料。它的定位：不追求让你成为算法专家，只追求一件事——考场上看到题，你知道它在考什么、能套用模板把它做对。
使用对象：默认你不知道任何前置知识，所有专业术语第一次出现都会解释，所有公式都用 LaTeX 写清楚并配代入数字的例子，所有解法都给出"可照抄的答题模板"。
整理人：ZR with Claude Code
一、先搞清楚：这门考试到底考什么
这门课叫"算法设计与分析"。**"算法"就是解决某个问题的一套固定步骤；"设计"就是想出这套步骤；"分析"**就是判断这套步骤快不快、占内存多不多、对不对。
考试的核心就两件事，反复换着花样考：
- 给你一个问题，让你用指定的某种"策略"设计出算法（写思路、写伪代码、算复杂度，有时还要手算一个小例子）。
- 考你一堆概念性的判断和简答（这些概念在判断题、选择题、简答题里高频重复出现）。
关键情报：根据已知信息，考试题目大部分是历年原题，小部分是改动不大的新题，题型与历年高度一致。所以本知识体系的策略很明确——把历年每一类题彻底吃透、练到能默写模板，新题也能照葫芦画瓢。
二、典型试卷结构与分值（综合历年）
不同年份卷面构成略有差异，但题型范围稳定。下面是综合历年试卷归纳出的典型构成（分值为各年常见取值，仅供参考，以实际卷面为准）：
| 题型 | 大致分值 | 考查内容 | 对应文档 |
|---|---|---|---|
| 判断题（打 √/×） | 15～30 分 | 渐进记号、复杂度、各策略概念、概率算法、P/NP、近似算法 | 11、01、09 |
| 选择题 | 0～24 分 | 回溯/分支限界、解空间树、概率算法、复杂度 | 11、06 |
| 填空题 | 0～20 分 | 算法性质、评价标准、判定树、棋盘覆盖、性能比 | 11、01 |
| 简答/问答题 | 10～20 分 | 拟阵、P/NP、伪多项式、下界、性能比、各策略适用条件、智能优化 | 00、05、08、09、10 |
| 递推式求解 | 5～10 分 | 主定理 / 迭代展开 / 课件"定理 1" | 01 |
| 分治大题 | 10～20 分 | 逆序对、股票买卖、网球循环赛、假币 | 02 |
| 动态规划大题 | 15～20 分 | 矩阵链乘、LCS、投资/生产/货车/货物分配、广告牌 | 04 |
| 贪心大题 | 15 分 | 多机调度、方格阵路径、任务指派 | 05 |
| 回溯大题 | 10～15 分 | SAT（画搜索树） | 06 |
| 分支限界大题 | 6～8 分 | 中转贸易、通信网络、最短路径、电路布线 | 06 |
| 概率算法大题 | 5～15 分 | 近似取大值、指纹法、Huffman 提问 | 07 |
| NP 完全性证明 | 15～25 分 | TSP、SAT 的 NP 完全证明 | 09 |
| 遗传算法大题 | 8 分 | TSP 遗传算法手算 | 10 |
注意：并非每年都考全部题型。例如选择题、填空题主要出现在 2002 年卷（
试卷5）；遗传算法、智能优化主要出现在 2020 年卷。但判断题、五大策略大题、P/NP 与概率算法概念几乎年年都考。
三、文档导航（按学习顺序）
| 编号 | 文档 | 学什么 | 覆盖的题库题 |
|---|---|---|---|
00 | 算法策略总论与通用解题法 | 先读这篇。九大算法策略全景、怎么判断该用哪种策略、解空间树、各类大题的"万能答题模板"、易混概念总表 | 简答 Q19（各策略适用条件）等通用题 |
01 | 数学基础：渐进记号与递推式求解 | 判断 1～11、选择 10、Q14、Q15、T1～T5 | |
02 | 分治算法 | 分治三步、归并排序框架、用递推式算复杂度 | D1 逆序对、D2 股票、D3 网球赛、D4 假币 |
03 | 减治与变治算法 | 减治 vs 变治、二分查找类、预排序、摩尔投票、BST/AVL/2-3 树 | V1 多数元素、V2 求 |
04 | 动态规划 | 重点。状态/决策/转移方程四件套、填表手算、各类资源分配题 | P1 矩阵链乘、P2 LCS、P3～P6 分配题、P7 广告牌 |
05 | 贪心算法与拟阵 | 贪心的套路与局限、近似比、Huffman、拟阵（Prim/Kruskal） | G1～G4、Q8 拟阵、R3 Huffman 提问 |
06 | 回溯法与分支限界法 | 解空间树、DFS 剪枝、界函数、二叉搜索树构造、四问答题模板 | B1/B2 SAT、BB1～BB4、选择 1～5、11、12 |
07 | 概率与随机算法 | 四类概率算法、拉斯维加斯 vs 蒙特卡罗、指纹法概率计算 | R1 取大值、R2 指纹法、Q3、Q4、选择 6～8 |
08 | 下界、近似算法与性能比 | 求下界的方法、判定树、对手论证、性能比定义与陷阱、FPTAS | Q9～Q13、Q16 称球、判断 16～19、43～45 |
09 | P/NP 理论与 NP 完全性证明 | P/NP/NPC/NP-hard、判定问题、归约 vs 转化、TSP/SAT 证明 | Q5～Q7、N1/N2、判断 32～42 |
10 | 智能优化算法 | 邻域搜索、模拟退火、遗传算法（含 TSP 遗传手算） | Q18、遗传算法大题、Q17 前沿搜索 |
11 | 判断/选择/填空专项与高频陷阱 | 全部判断题逐条速记、选择填空套路、易错概念对照 | 判断 1～45、选择 1～12、填空 1～5 |
四、考前突击路线（按剩余时间选）
如果只剩 1～2 天（保及格）
- 判断题专项（文档
11）——背熟答案和"为什么"，这是最稳的分。 - 五大策略的答题模板（文档
00第 8 节）——记住分治题、DP 题、贪心题、回溯题、分支限界题各自怎么开头、写什么。 - 动态规划填表（文档
04）——DP 大题分值最高且最套路化，练 2～3 道资源分配题的手算表。 - 高频简答（文档
00、05、09）——拟阵、P/NP 定义、Las Vegas/Monte Carlo 区别、各策略适用条件。
如果剩 3～5 天（争取中高分）
按 00 → 01 → 11 → 04 → 05 → 02 → 06 → 09 → 07 → 03 → 08 → 10 顺序逐篇过，每篇末尾都有"自测清单"，做不出来就回看正文。
复习优先级总结（源资料建议 + 本体系补充）
判断题（必考、陷阱多）→ 简答概念（拟阵、P/NP、伪多项式、下界与性能比）→ 五大策略大题（分治逆序对/股票、DP 矩阵链乘/LCS/资源分配、贪心调度、回溯 SAT、分支限界中转贸易）。这些在 2011–2020 各卷反复出现，是得分核心。
五、阅读约定
- 术语：每个专业词第一次出现都用加粗并紧跟一句话解释。
- 公式：行内公式写成
这种形式，独立公式单独成行。每个公式都会说明"每个符号是什么意思"和"怎么套用"，并给一个代入数字的例子。 - 伪代码：用代码块写出，可以直接照抄到卷子上（考试不要求特定编程语言，写清逻辑即可）。
- ⚠️ 标记：表示这里是历年高频陷阱或最容易丢分的地方，务必停下来看。
- 【答题模板】：表示这是考场上可以直接套用的固定写法。
- 交叉引用：写作"（详见
04_动态规划.md）"，按编号去对应文档查。
本知识体系基于 data/review/期末复习题汇总.md 构建。原题文字一律以该汇总文件为准。