这里按算法设计策略组织笔记：每一种策略先讲清核心思想与适用条件，再用经典问题完整走一遍「建模 → 递归关系 → 填表/搜索过程 → 代码实现 → 复杂度分析」。
与 软考·算法基础 的分工：软考部分面向上午场选择题的考点速记，本分类面向代码实现与推导细节，两者互为补充。
1. 算法设计策略总览
| 策略 | 核心思想 | 解的性质 | 典型问题 | 时间复杂度量级 |
|---|---|---|---|---|
| 分治法 | 分解 → 递归求解 → 合并 | 子问题相互独立 | 归并排序、快速排序、二分查找、最大子段和、大整数乘法 | $O(n\log n)$ ~ $O(n^2)$ |
| 动态规划 | 子问题重叠，自底向上填表，用表避免重复计算 | 满足最优子结构 + 重叠子问题 | 矩阵连乘、最长公共子序列、0-1 背包、最优二叉搜索树 | $O(n^2)$ ~ $O(n^3)$ |
| 贪心法 | 每步取当前最优，不回溯 | 需证明贪心选择性质 | 活动安排、哈夫曼编码、最小生成树、单源最短路径 | $O(n\log n)$ ~ $O(n^2)$ |
| 回溯法 | 深度优先搜索解空间树 + 剪枝 | 系统性枚举，可求全部可行解 | 0-1 背包、n 皇后、图着色、旅行商问题 | 最坏指数级 |
| 分支限界法 | 广度优先/优先队列搜索 + 限界剪枝 | 求最优解，剪枝效率高于回溯 | 0-1 背包、旅行商问题、装载问题 | 最坏指数级 |
| 随机化算法 | 决策过程引入随机数 | 概率正确 / 概率高效 | 随机快排、素数测试、随机化最小割 | 与随机性相关 |
| 线性规划与网络流 | 线性约束下优化目标 / 最大流最小割 | 多项式时间可解 | 最大流、最小费用流、二分图匹配 | 多项式级 |
| NP 完全性理论与近似算法 | 判定问题归约与近似比保证 | 精确解不可行时求近似解 | 顶点覆盖、集合覆盖、TSP 近似 | 多项式级近似 |
2. 如何选择策略
判断顺序建议按下面四步走：
- 子问题是否独立？ 相互独立 → 分治法；如果子问题之间有重叠（同一个子问题被反复求解）→ 动态规划。
- 能否证明「每步局部最优即全局最优」？ 能给出交换论证（exchange argument）或数学归纳证明 → 贪心法；证明不了 → 老老实实动态规划。
- 问题规模能否枚举？ 解空间小且需要所有可行解 → 回溯法；只求最优解且解空间巨大 → 分支限界法。
- 问题是否 NP 难？ 是 → 小规模用搜索，大规模用近似算法或随机化算法。
一句话记忆：分治看独立、动规看重叠、贪心看证明、回溯看剪枝。
评论