算法设计与分析
Design and Analysis of Algorithms
📖这门课到底讲什么
算法设计与分析在数据结构之上更进一步：以算法设计范式为骨架，系统讲授分治、动态规划、贪心、回溯与分支限界、随机化与近似算法，并配以正确的证明与渐近分析（主定理、摊还分析、NP 完全性）。它关心的是为什么这个算法是对的、为什么它的复杂度是这个量级、问题本身有多难这三件事。学完你应能对一个问题写清最优子结构与状态转移、用反例或交换论证证明贪心正确性、用归约证明问题是 NP 难的，并能把实际工程问题（任务调度、资源分配、字符串匹配、路径规划）建模成经典算法问题求解。
🎯为什么必须学好
它是算法岗与竞赛的必修课：笔试压轴题基本靠动态规划与图算法，面试追问为什么贪心正确、如何证明复杂度，直接区分背题者与真正理解者。对考研与保研，它是 408 数据结构题的进阶支撑，也是机试拉开差距的关键。长期看，它训练的是用可证明的方式思考效率，这种能力在架构设计、性能优化、决策系统里会持续受益。
📌核心知识清单
- 渐进分析与复杂度：大 O/大 Theta/大 Omega、主定理求解递归式、摊还分析（聚合法、记账法、势能法）
- 分治：归并排序与逆序对计数、快速选择、最近点对、矩阵乘法（Strassen）、分治的复杂度方程构建
- 动态规划：最优子结构与重叠子问题、背包问题族、最长公共子序列、编辑距离、区间 DP、状态压缩 DP
- 贪心：活动选择与区间调度、霍夫曼编码、分数背包、最小生成树（Kruskal 与 Prim）、拟阵与交换论证证明正确性
- 回溯与分支限界：N 皇后、数独、子集与排列枚举、剪枝策略与搜索空间估计
- 图算法进阶：最大流（Ford-Fulkerson 与 Edmonds-Karp）、二分图匹配（匈牙利算法）、强连通分量、网络流建模技巧
- 字符串算法：KMP 的失配函数与均摊分析、Z 算法、Trie 与 AC 自动机、后缀数组入门
- 计算复杂性：P 与 NP、NP 完全与归约（SAT、顶点覆盖、旅行商）、近似算法与启发式策略
✍️怎么学（可执行步骤）
- 以 CLRS《算法导论》为主线（重点第2至8、15、16、22至26章），同时用《算法（第4版）》做实现，理论证明与代码实现双轨并行
- 每学一个范式就整理一页模板：适用条件、状态定义套路、正确性证明方式、复杂度推算方法，动态规划部分建议手写二十道题的完整状态转移推导
- 在 Codeforces 或洛谷参加周赛，从 Div.3 开始，重点做 dp 与图论标签的题，每场比赛后补题并写题解
- 读研方向的同学可跟斯坦福 CS161 的讲义，做完其中关于 NP 完全性与近似算法的作业，建立复杂度理论的基本功
📚推荐教材与书籍
本科算法课标准教材，重点分治、堆、动态规划、贪心、图算法与 NP 完全性章节
实现导向、图示优秀，字符串算法与图算法章节尤其出色，适合配合编码练习
从问题建模到算法选择的实战指南，附大量在线题目索引，做项目与准备机试非常实用
面向竞赛的系统训练书，覆盖 dp、图论、数论与计算几何，适合想冲 ICPC 的同学
🎬视频课程 / 公开课
Tim Roughgarden 讲授，分治、图算法与 NP 完全性讲得极清晰
国内高校版本，与考研机试题目风格接近
🌐网站与文档
中文最全的算法专题讲解，含状态设计技巧与优化方法（单调队列、斜率优化）
英文算法百科，每种算法都有证明、复杂度与可运行代码，写题解的好参考
🐙GitHub 开源资料
覆盖 dp、贪心、图算法的完整实现集合，可作为模板库查阅
按范式分类的题解，动态规划专题从入门到进阶组织得很好
用统一框架讲 dp 与回溯，适合把零散技巧串成体系
🧪动手实践任务
实践 1
实现并对比编辑距离、LCS、背包三类 DP 问题，输出状态转移表并在报告中解释每一项的含义
实践 2
实现最大流算法并在一个任务分配实例上求解（如工人与任务匹配），输出流量分配结果与最小割验证
实践 3
选一道 NP 完全问题（如旅行商）分别用精确搜索与贪心近似求解，比较解质量与运行时间，写出近似比实验说明
实践 4
整理一份《算法范式对照表》：对二十道经典题标注所属范式、状态定义、证明方式与复杂度，作为长期复习资料
🧾考试与面试
💼 面试会怎么考
高频：给一个问题让你说清最优子结构与状态转移（如股票买卖、打家劫舍变形）；贪心题被追问为什么贪心是对的、能不能给反例；最大流与二分图匹配的实际建模（任务分配、时间表安排）；快排与归并的复杂度推导（用主定理现场演算）；问到 NP 完全性时会问 P 与 NP 的区别以及为什么实际问题常用近似或启发式。面试官在意的是推导过程而非结论。
📝 期末与考研怎么过
期末通常包括复杂度分析题（解递归式）、算法设计题（写出伪码与复杂度）、正确性证明题（归纳或交换论证）与 NP 归约题。备考方法是把常见递归式的解背熟、把每种范式准备一到两个标准例题的完整答案、练习两三道归约题（3-SAT 归约到顶点覆盖）。目标八十分以上；若走算法方向，争取把归约类题目也做对。
⚠️ 常见坑
- 动态规划状态定义含糊，先写循环再想状态，导致边界与转移全靠试，应先在纸上写清状态含义与转移方程
- 贪心题不验证正确性，用错策略且举不出反例，面试时无法自证；至少要会用交换论证或反例检验
- 复杂度分析只算最好情况，忽略递归树深度与常数项，得不到正确上界
- 遇到难题直接看题解并以为自己会了，一个月后重做仍不会；正确做法是标记题目并在三周后闭卷重做