ALG-10 综合复习与术语表
10 · 综合复习与术语表（Comprehensive Review & Glossary）
📅 预计 150 分钟 | ⭐ 本章主题：把全课程串成一张地图，对照自查、查漏补缺
10.0 从地图说起
学完一门课，最重要的是手里有张地图——知道学了哪些板块、每块的核心问题是什么、哪个算法解决哪个问题、彼此怎么联系。本章把前九章的内容压成一张知识结构图，再给你三样工具：考点汇总表、混淆点对比、全课程术语表。
复习的打开方式是：先看结构图回忆「每章讲什么」，再看对比表辨析「容易混的算法有什么不同」，最后用术语表自测「术语能不能对上中文解释」。
10.1 全课程知识结构图（文字版）
算法设计与分析
├── 1. 算法基础
│ ├── 算法的特性：有穷性、确定性、可行性、输入、输出
│ ├── 复杂度分析：大 O、时间/空间、平均/最坏
│ └── 递归与递推：递归树、递归转迭代
├── 2. 分治策略
│ ├── 三步：分解 → 解决 → 合并
│ ├── 归并排序、快速排序、二分查找
│ └── 递推式求解：主定理
├── 3. 排序算法
│ ├── O(n²)：冒泡、选择、插入
│ ├── O(n log n)：归并、快排、堆排序
│ └── 稳定性：相等元素相对顺序是否保持
├── 4. 贪心算法
│ ├── 局部最优 → 全局最优（需证明）
│ ├── 活动选择、哈夫曼编码、部分背包
│ └── 反例意识：不是所有问题都能贪心
├── 5. 动态规划
│ ├── 最优子结构 + 重叠子问题
│ ├── 四问：状态 → 转移方程 → 边界 → 遍历顺序
│ ├── 0-1 背包、最长公共子序列、最长递增子序列
│ └── 与贪心 / 分治的边界
├── 6. 回溯与分支限界
│ ├── 解空间树、DFS + 剪枝、选/探/撤
│ ├── 八皇后、子集和、全排列
│ └── 分支限界：上界函数 + BFS / 优先队列
├── 7. 图算法
│ ├── 存储：邻接矩阵 / 邻接表
│ ├── 遍历：DFS（栈/递归）、BFS（队列）
│ ├── 连通分量、拓扑排序（DAG）
│ └── 复杂度 O(V+E)
├── 8. 最短路径与最小生成树
│ ├── 最短路：Dijkstra / Bellman-Ford / Floyd
│ └── MST：Prim（堆）、Kruskal（并查集）
└── 9. 查找与字符串
├── 顺序 / 二分 / 哈希
└── 朴素匹配 / KMP（next 数组）
看这张图能顺下来多少，基本就是你的掌握度。每个分支下面的点，都是能独立写出代码的「动作」。
10.2 各章考点汇总表
| 章 | 核心问题 | 必会代码 | 关键复杂度 |
|---|---|---|---|
| 1 算法基础 | 怎么衡量算法好坏 | 大 O 化简、求递推式 | O(1) ~ O(2ⁿ) |
| 2 分治 | 大问题拆小问题 | 归并排序 | O(n log n) |
| 3 排序 | 把序列排好 | 快排、归并、堆排序 | 见 10.4 |
| 4 贪心 | 局部最优能否全局最优 | 活动选择、哈夫曼 | 看具体问题 |
| 5 动态规划 | 重叠子问题怎么递推 | 0-1 背包、LCS、LIS | O(n·W) / O(n²) |
| 6 回溯 / 分支限界 | 穷举 + 剪枝 | 八皇后、全排列、子集和 | O(2ⁿ) ~ O(n!) |
| 7 图算法 | 在图上遍历 | DFS、BFS、拓扑排序 | O(V+E) |
| 8 最短路 / MST | 图上的优化 | Dijkstra、Kruskal | O((V+E)log V)、O(E log E) |
| 9 查找 / 字符串 | 快速找、高效配 | 二分、KMP | O(log n)、O(n+m) |
10.3 常见混淆点对比
贪心 vs 动态规划
| 维度 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 每步选当前最优，不回退 | 枚举所有子结构，取全局最优 |
| 依赖信息 | 只需局部 | 需要子问题全部结果 |
| 正确性 | 需要证明贪心选择性质 | 靠最优子结构保证 |
| 典型 | 活动选择、哈夫曼、Dijkstra、Prim | 0-1 背包、LCS、LIS |
| 反例 | 0-1 背包不能贪（部分背包可以） | 几乎都能正确 |
一句话：贪心赌「当前最优就是全局最优」，DP 用「子问题的所有可能性」做保证。发现某个问题可以贪心但不放心，先试着构造反例；构造不出又证不出，用 DP 兜底。
DFS vs BFS
| 维度 | DFS | BFS |
|---|---|---|
| 结构 | 栈 / 递归 | 队列 |
| 特点 | 一路到底再回头 | 层层扩散 |
| 无权最短步数 | 不保证 | 首次访问即最短 |
| 用途 | 连通分量、环检测、拓扑排序 | 无权最短路、分层 |
Dijkstra vs Bellman-Ford vs Floyd
| 维度 | Dijkstra | Bellman-Ford | Floyd |
|---|---|---|---|
| 类型 | 单源 | 单源 | 多源 |
| 边权 | 非负 | 可负 | 可负（无负环） |
| 负环检测 | 不能 | 能 | 能（对角为负） |
| 复杂度 | O((V+E)log V) | O(VE) | O(V³) |
回溯 vs 分支限界
回溯是 DFS + 约束剪枝，找「有没有 / 有几个」解；分支限界是 BFS / 优先队列 + 界限剪枝，求「最优解」。
Prim vs Kruskal
Prim 从一点生长（堆，稠密图好）；Kruskal 全局选边（并查集，稀疏图好）。结果总权值相同。
顺序查找 vs 二分 vs 哈希
| 前提 | 平均 | 适用 | |
|---|---|---|---|
| 顺序 | 无 | O(n) | 无序小数据 |
| 二分 | 有序 | O(log n) | 有序只查 |
| 哈希 | 键可哈希 | O(1) | 快速精确查找 |
10.4 复杂度速查表
| 算法 / 结构 | 平均时间 | 最坏时间 | 额外空间 | 备注 |
|---|---|---|---|---|
| 冒泡 / 选择 / 插入排序 | O(n²) | O(n²) | O(1) | 小数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 平均最优 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 二分查找 | O(log n) | O(log n) | O(1) | 需有序 |
| 哈希表 | O(1) | O(n) | O(n) | 需可哈希 |
| DFS / BFS | O(V+E) | O(V+E) | O(V) | 图遍历 |
| Dijkstra | O((V+E)log V) | 同左 | O(V) | 非负权 |
| Bellman-Ford | O(VE) | O(VE) | O(V) | 可负权 |
| Floyd | O(V³) | O(V³) | O(V²) | 多源 |
| Kruskal | O(E log E) | 同左 | O(V) | 稀疏图 |
| Prim | O((V+E)log V) | 同左 | O(V) | 稠密图 |
| KMP | O(n+m) | O(n+m) | O(m) | 字符串 |
10.5 刷题路线建议
路线按「从地基到组合」推进，每个阶段在同一主题上做够数量再进下一阶段：
- 复杂度与简单题（约 10 题）：大 O 化简、双指针、滑动窗口——练手速和基本功。
- 分治与排序（约 10 题）：手写归并 / 快排，理解「分解-解决-合并」；二分查找及其变体。
- 贪心（约 8 题）：活动选择、区间覆盖、跳跃游戏——练习「贪心选择 + 反例意识」。
- 动态规划（约 15 题，全课程重头）：先做一维（爬楼梯、打家劫舍），再做二维（0-1 背包、LCS、编辑距离），最后区间 / 树形。每道题问自己四件事：状态是什么？转移方程？边界？遍历顺序？
- 回溯 / 搜索（约 8 题）：子集、组合、全排列、N 皇后——统一「选-探-撤」模板。
- 图（约 10 题）：DFS / BFS 各 5 道，然后连通分量、拓扑排序、最短路径、MST 各 2~3 道。
- 字符串（约 8 题）：回文、公共前缀、频次、KMP 各来几道。
两条通用原则：
- 先模板后变式：把各章的通用模板（回溯三件套、二分边界、DP 四问）写熟，再挑战变式。
- 分类限时：同一类题集中做、记录用时和思路卡点；每道题做完在笔记里写一句「这题考的是哪个知识点、坑在哪」。
10.6 分析问题的通用步骤
无论题目属于哪一章，按这条流水线走，能避免「上来就写代码」：
- 读题定性：输入规模多大？要求最优解还是任意解？有无特殊约束（有序、无环、非负）？
- 判断题型：单点决策递推（DP）？局部最优即全局（贪心）？穷举 + 剪枝（回溯）？图上的遍历 / 最短路（图算法）？找数据（查找）？
- 想复杂度：先定目标复杂度（如要求 O(n log n)），排除明显不合适的算法。
- 写核心逻辑：先写算法骨架（转移方程 / 递归模板 / 遍历框架），再补边界。
- 验证边界：空输入、单元素、最大规模、不连通、负权、有环，各测一遍。
🧠 记忆口诀
- 五章主线：分治拆、贪心赌、DP 递、回溯搜、图走遍。
- 复杂度梯队：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
- 选算法先看前提：有序 → 二分；可哈希 → 哈希；非负权 → Dijkstra；负权 → Bellman-Ford；全点对 → Floyd。
- 每章一句话（见各章口诀），复习时先把九句话背出来再展开。
⭐ 全课程考点清单
- 复杂度分析：大 O 定义、化简规则、常见复杂度排序
- 分治三步、递归树、递推式求解
- 三大 O(n log n) 排序原理与稳定性
- 贪心选择性质与反例意识（0-1 背包 vs 部分背包）
- DP 四问：状态、转移、边界、顺序（0-1 背包 / LCS / LIS）
- 回溯模板与剪枝；八皇后、全排列、子集和
- 图存储与 DFS / BFS 实现与复杂度 O(V+E)
- 拓扑排序 Kahn 与有环判定
- Dijkstra / Bellman-Ford / Floyd 的选择与实现
- Prim / Kruskal 与并查集
- 二分边界、哈希冲突、KMP 的 next 数组
- 混淆点对比表（贪心 vs DP、DFS vs BFS 等）
📌 全课程中英术语表（60 条）
| 中文 | English | 说明 |
|---|---|---|
| 算法 | algorithm | 解决问题的有限步骤描述 |
| 复杂度 | complexity | 时间 / 空间开销的度量 |
| 大 O 记号 | big O notation | 渐近上界 |
| 时间复杂度 | time complexity | 运行时间的增长量级 |
| 空间复杂度 | space complexity | 内存占用的增长量级 |
| 递归 | recursion | 函数调用自身 |
| 递推式 | recurrence | 用前项表达后项的等式 |
| 分治 | divide and conquer | 分解-解决-合并 |
| 归并排序 | merge sort | 稳定的 O(n log n) 排序 |
| 快速排序 | quick sort | 平均 O(n log n) 排序 |
| 堆排序 | heap sort | 基于二叉堆的排序 |
| 稳定排序 | stable sort | 相等元素相对顺序不变 |
| 贪心算法 | greedy algorithm | 每步局部最优 |
| 贪心选择性质 | greedy choice property | 局部最优组合成全局最优 |
| 哈夫曼编码 | Huffman coding | 贪心构造最优前缀码 |
| 动态规划 | dynamic programming | 最优子结构 + 重叠子问题 |
| 最优子结构 | optimal substructure | 全局最优含局部最优 |
| 重叠子问题 | overlapping subproblems | 子问题被重复计算 |
| 状态 | state | DP 中描述局面的变量 |
| 转移方程 | transition equation | 状态间的关系式 |
| 0-1 背包 | 0-1 knapsack | 物品整体取 / 不取 |
| 最长公共子序列 | longest common subsequence (LCS) | 两序列最长公共子序列 |
| 最长递增子序列 | longest increasing subsequence (LIS) | 最长递增子序列 |
| 回溯法 | backtracking | 穷举 + 撤销 + 剪枝 |
| 解空间树 | solution space tree | 所有候选解的树 |
| 剪枝 | pruning | 排除无用分支 |
| 分支限界 | branch and bound | 上界函数剪枝求最优 |
| 上界 | upper bound | 某分支结果的天花板 |
| 图 | graph | 顶点与边的集合 |
| 顶点 / 边 | vertex / edge | 图的点 / 线 |
| 有向图 / 无向图 | directed / undirected graph | 边有无方向 |
| 邻接矩阵 / 邻接表 | adjacency matrix / list | 两种图的存储 |
| 深度优先搜索 | depth-first search (DFS) | 栈，走到底再回头 |
| 广度优先搜索 | breadth-first search (BFS) | 队列，层层扩散 |
| 连通分量 | connected component | 极大连通子图 |
| 强连通分量 | strongly connected component | 有向图中两两互达的极大子图 |
| 拓扑排序 | topological sort | DAG 上的依赖序 |
| 有向无环图 | directed acyclic graph (DAG) | 无环有向图 |
| 最短路径 | shortest path | 两点间权值和最小的路径 |
| 松弛 | relaxation | 尝试用更短路径更新 |
| 优先队列 | priority queue | 每次取最小 / 最大元素 |
| Dijkstra 算法 | Dijkstra's algorithm | 非负权单源最短路 |
| Bellman-Ford 算法 | Bellman-Ford algorithm | 可负权单源最短路 |
| 负权环 | negative cycle | 总权为负的环 |
| Floyd-Warshall 算法 | Floyd-Warshall algorithm | 多源最短路 |
| 最小生成树 | minimum spanning tree (MST) | 总权最小的生成树 |
| 生成树 | spanning tree | n 点 n-1 条边连通无环 |
| 切割性质 | cut property | 跨切割最小边必在某个 MST |
| 回路性质 | cycle property | 环上最大边必不在 MST |
| Prim 算法 | Prim's algorithm | 从点生长，稠密图 |
| Kruskal 算法 | Kruskal's algorithm | 全局选边，稀疏图 |
| 并查集 | union-find | 判断连通、合并集合 |
| 路径压缩 | path compression | 并查集的加速技巧 |
| 顺序查找 | linear search | 挨个比较 |
| 二分查找 | binary search | 有序数据砍半查找 |
| 哈希表 | hash table | 键映射下标的查找结构 |
| 哈希冲突 | collision | 不同键映射到同一位置 |
| 链地址法 | chaining | 冲突挂链表 |
| 装填因子 | load factor | 元素数 / 桶数 |
| 字符串匹配 | string matching | 文本中找模式 |
| 朴素匹配 | naive matching | 逐位对齐 |
| KMP 算法 | Knuth-Morris-Pratt | 线性字符串匹配 |
| next 数组 | prefix function | 最长相等前后缀长度 |
| 回文 | palindrome | 正反读一样 |
| 异位词 | anagram | 字母构成相同 |