算法设计与分析

这里按算法设计策略组织笔记：每一种策略先讲清核心思想与适用条件，再用经典问题完整走一遍「建模 → 递归关系 → 填表/搜索过程 → 代码实现 → 复杂度分析」。

与 软考·算法基础 的分工：软考部分面向上午场选择题的考点速记，本分类面向代码实现与推导细节，两者互为补充。

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. 如何选择策略

判断顺序建议按下面四步走：

1. 子问题是否独立？ 相互独立 → 分治法；如果子问题之间有重叠（同一个子问题被反复求解）→ 动态规划。
2. 能否证明「每步局部最优即全局最优」？ 能给出交换论证（exchange argument）或数学归纳证明 → 贪心法；证明不了 → 老老实实动态规划。
3. 问题规模能否枚举？ 解空间小且需要所有可行解 → 回溯法；只求最优解且解空间巨大 → 分支限界法。
4. 问题是否 NP 难？ 是 → 小规模用搜索，大规模用近似算法或随机化算法。

一句话记忆：分治看独立、动规看重叠、贪心看证明、回溯看剪枝。

学习目录

• 分治法
• 动态规划
• 贪心法
• 回溯法
• 分支限界法
• 随机化算法
• 线性规划与网络流
• NP完全性理论与近似算法