前言
这是一份算法设计与分析课程的复习大纲，涵盖了从基础概念到高级算法设计范式的六个章节。适合期末复习或面试前快速回顾。
第一章：算法基础
1. 算法概念
算法是求解问题的一系列有限步骤。
2. 算法的四大特性
- 有穷性：算法必须在有限步后终止
- 确定性：每一步必须有确切的定义
- 可行性：每一步都可以通过基本运算实现
- 输入/输出：有零个或多个输入，至少一个输出
3. 算法分析
算法分析是指对算法所需的计算机资源进行预测。
4. 复杂性测度
- 空间复杂度：算法运行所需的存储空间
- 时间复杂度：算法运行所需的时间
5. 渐近复杂性
当 \(n \to \infty\) 时，对于 \(T(n)\) 只保留其最高次幂项为 \(t(n)\)，\(t(n)\) 是 \(T(n)\) 的渐近复杂性。
6. 渐近分析记号
- 大 \(O\) 记号（上界）：\(f(n) = O(g(n))\) 表示 \(f(n)\) 的增长不超过 \(g(n)\)
- 大 \(\Omega\) 记号（下界）：\(f(n) = \Omega(g(n))\) 表示 \(f(n)\) 的增长不低于 \(g(n)\)
- 大 \(\Theta\) 记号（紧界）：\(f(n) = \Theta(g(n))\) 表示 \(f(n)\) 与 \(g(n)\) 同阶
- 小 \(o\) 记号（非紧上界）
7. 算法分类
多项式时间算法（常见复杂度关系）：
$$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)$$8. 算法分析基本法则
- 非递归算法：依次计算每条语句的执行次数
- 递归算法：写出递归方程，求解递归方程
第二章：递归与分治
9. 递归
- 优点：结构清晰、程序易读、正确性容易证明
- 缺点：运行效率较低、花费更多时间
- 数据结构：栈（Stack）
10. 解递归方程的三种方法
替换法：先猜测解的形式，再用数学归纳法证明。
递归树法：将递归展开成树状结构，逐层求和。适合可视化递归过程。
主方法/主定理（三种情况）：
对于 \(T(n) = aT(n/b) + f(n)\)：
- 情况一：若 \(f(n) = O(n^{\log_b a - \epsilon})\)，则 \(T(n) = \Theta(n^{\log_b a})\)
- 情况二：若 \(f(n) = \Theta(n^{\log_b a})\)，则 \(T(n) = \Theta(n^{\log_b a} \log n)\)
- 情况三：若 \(f(n) = \Omega(n^{\log_b a + \epsilon})\) 且满足正则条件，则 \(T(n) = \Theta(f(n))\)
11. 分治法
基本思想：将复杂大问题拆解为若干个相同或相似的、规模较小的子问题，递归解决，再将子问题的解合并。
三个步骤：分解 → 递归解决子问题 → 合并子问题的解
12. 经典分治算法
二分查找（Binary Search）：
- 在有序数组中查找特定元素
- 每次将搜索范围减半
- 复杂度：\(T(n) = T(n/2) + O(1)\)，由主方法得 \(O(\log n)\)
归并排序（Merge Sort）：
- \(T(n) = 2T(n/2) + O(n)\)
- 复杂度：\(O(n \log n)\)
- 改进方案：将递归改为两两一组的迭代写法
快速排序（Quick Sort）：
- 最好情况（均匀划分）：\(T(n) = 2T(n/2) + O(n)\) → \(O(n \log n)\)
- 最坏情况（极端不平衡）：\(T(n) = T(n-1) + O(n)\) → \(O(n^2)\)
- 平均情况：\(O(n \log n)\)
- 改进方案：随机化选择基准元素（pivot）
Strassen 矩阵乘法：
- 定义了 7 个特殊的矩阵乘积 \(P_1\) 到 \(P_7\)
- 将传统 8 次乘法减少为 7 次
- 递归方程：\(T(n) = 7T(n/2) + O(n^2)\)
- 复杂度：\(O(n^{\log_2 7}) \approx O(n^{2.81})\)
第三章：动态规划
13. 动态规划 vs 分治法
| 对比维度 | 分治法 | 动态规划 |
|---|---|---|
| 求解方向 | 自顶向下 | 自底向上 |
| 子问题 | 相互独立 | 有重叠子问题 |
| 重复计算 | 每个子问题计算一次 | 通过填表避免重复 |
14. 动态规划四步骤
- 刻画最优解的结构特征
- 递归地定义最优解的值
- 自底向上计算最优解的值
- 构造最优解
15. 基本要素
- 最优子结构：问题的最优解包含其子问题的最优解
- 重叠子问题：递归求解时相同子问题被重复计算，DP 通过填表避免
16. 备忘录方法
动态规划的自顶向下变形。采用分治法的递归结构，但维护一个表格记录子问题的解。每次递归前先查表，若已计算则直接返回。
17. 经典 DP 问题
矩阵链乘：
- 目标：确定矩阵相乘的最优顺序，最小化标量乘法次数
- 时间复杂度：\(O(n^3)\)
- 空间复杂度：\(O(n^2)\)
0-1 背包问题：
- 目标：在容量 \(W\) 的背包中放入总价值最大的物品
- 时间复杂度：\(O(n \times W)\)
- 空间复杂度（优化后）：\(O(W)\)
最长公共子序列（LCS）：
- 不要求连续，求两个序列的最长公共子序列
- 时间复杂度：\(O(m \times n)\)
- 空间复杂度：\(O(m \times n)\)，可优化至 \(O(\min(m, n))\)
图像压缩：通过动态规划确定最优分段策略。
第四章：贪心算法
18. 贪心算法概念
在对问题求解时，总是做出在当前看来是最好的选择。不从整体最优上考虑，得到的是局部最优解（在适用问题中恰是全局最优）。
19. 基本要素
- 贪心选择性质：整体最优解可通过一系列局部最优选择达到
- 最优子结构：问题的最优解包含子问题的最优解
20. 贪心 vs 动态规划
| 贪心算法 | 动态规划 |
|---|---|
| 自顶向下 | 自底向上（或带备忘录自顶向下） |
| 直接做当前最有利的选择 | 考虑所有子问题再做选择 |
| 不回溯 | 依赖重叠子问题的解 |
| 更快，但适用范围更窄 | 适用范围更广 |
21. 经典贪心问题
部分背包问题：物品可分割，按单位价值（价值/重量）降序贪心选取。
活动选择问题：按结束时间最早贪心选取，每次选不与已选活动冲突且结束最早的活动。
哈夫曼编码：
- 前缀码：任一字符的编码都不是另一个字符编码的前缀
- 构造方法：将所有字符按频率放入最小堆，每次弹出频率最小的两棵树合并，重复直至剩一棵树
第五章：回溯法
22. 基本原理
在解空间树中按**深度优先（DFS）**策略搜索。当判断某节点不包含最优解（或不可行）时，剪枝（Pruning），退回父节点尝试其他分支。
23. 解空间树
- 子集树：从 \(n\) 个元素中找满足性质的子集（如 0-1 背包），节点数 \(O(2^n)\)
- 排列树：确定 \(n\) 个元素的排列（如 N 皇后、旅行商），节点数 \(O(n!)\)
24. 经典回溯问题
N 皇后：约束条件是同一行、同一列、同一斜线上不能有两个皇后。用一维数组 x[i] 表示第 \(i\) 行的皇后所在列。
图着色问题：给定无向连通图和 \(m\) 种颜色，相邻顶点颜色不同。回溯法逐个顶点尝试涂色，冲突则剪枝。
25. 提高回溯法效率
- 设计强有力的剪枝函数（约束函数减去非可行解，限界函数减去非最优解）
- 优化搜索顺序（启发式搜索，优先搜索分支少的节点）
第六章：分支限界法
26. 分支限界法 vs 回溯法
| 对比维度 | 回溯法 | 分支限界法 |
|---|---|---|
| 搜索策略 | 深度优先（DFS） | 广度优先（BFS）或最佳优先 |
| 目标 | 找出所有解 | 找出最优解 |
| 节点扩展 | 每次扩展一个节点 | 维护活节点表，按优先级扩展 |
27. 基本思想
在解空间树上，以广度优先或最佳优先方式搜索。每个活节点只有一次机会成为扩展节点，一次性产生所有儿子节点，舍弃不可行或非最优的节点。
28. 两种常见分支限界法
- 队列式（FIFO）：按先进先出顺序选择扩展节点
- 优先队列式：按优先级（如当前解的界）选择扩展节点
总结
| 算法范式 | 核心思想 | 典型问题 |
|---|---|---|
| 分治法 | 分解→解决→合并 | 二分查找、归并排序、快速排序 |
| 动态规划 | 自底向上填表，避免重复 | 矩阵链乘、0-1 背包、LCS |
| 贪心算法 | 局部最优选择，不回溯 | 部分背包、哈夫曼编码 |
| 回溯法 | DFS + 剪枝 | N 皇后、图着色 |
| 分支限界法 | BFS/最佳优先 + 限界 | 旅行商、0-1 背包最优解 |
复习要点：每种算法范式的思想、适用条件、经典例题的递归方程和复杂度分析是考试重点。