返回：本科课程：疾风计划

1、课程定位

算法设计与分析训练的是“把问题变成可计算方案”的能力。数据结构更偏向组织数据，算法设计更偏向选择策略、证明正确性、估计复杂度，并判断一个问题到底能不能高效求解。

项目 内容
课程 算法设计与分析
教师 王振波
院校 清华大学
资料来源 清华/学堂在线公开课程大纲 + 常见算法设计课程内容
学习定位 408 主干入门后的算法能力补强，衔接刷题、AI、网络安全和系统项目
笔记范围 0401~0411，对应算法设计与分析 11 个主题

这一组笔记先按“算法范式”整理，而不是按题库刷题顺序整理。每章保留问题模型、核心算法、正确性证明思路、复杂度和复盘清单，后面做题时再把错题和代码实验补进对应章节。

2、参考大纲

来源 采用内容
清华大学 / 学堂在线《算法设计与分析》 算法基础、图、贪心、分治、动态规划、网络流、NP、近似算法、局部搜索、随机算法
国家高等教育智慧教育平台课程页 课程简介、教师和 11 章大纲
中国科学院大学《计算机算法设计与分析》大纲 分治、贪心、动态规划、回溯、分支限界、NP、概率算法、近似算法等常见算法课模块
中国大学 MOOC 算法设计与分析专题课 分而治之、动态规划、贪心策略和算法建模训练

3、学习主线

部分 章节 核心问题 后续连接
建模与分析 Chap 1-2 如何描述问题、算法和复杂度 伪代码、证明、渐进分析
图与贪心 Chap 3-4 如何用局部选择解决结构化问题 BFS/DFS、最短路、MST、调度
分治与 DP Chap 5-6 如何把问题拆开，如何复用子问题 归并、快排、FFT、背包、序列比对
网络流 Chap 7 如何用流量守恒描述匹配和割 最大流、最小割、二分图匹配
困难问题 Chap 8 如何判断问题可能没有多项式精确算法 规约、NP、NP 完全
应对策略 Chap 9-11 精确算法太难时如何近似、局部搜索或随机化 近似比、局部最优、概率界

4、章节索引

编号 Chap 主题 复盘重点 笔记
0401 1 算法导论与稳定匹配 问题形式化、稳定匹配、Gale-Shapley、正确性和复杂度 查看
0402 2 算法分析基础 可处理性、渐进增长、常见时间复杂度、递推与摊还入口 查看
0403 3 图算法基础 图建模、遍历、二分图、连通性、DAG 与拓扑序 查看
0404 4 贪心算法 区间调度、延迟最小化、缓存、最短路、最小生成树、聚类 查看
0405 5 分治策略 归并、逆序数、最近点对、大整数乘法、矩阵乘法、FFT 查看
0406 6 动态规划 加权区间调度、分段最小二乘、背包、RNA、序列比对、最短路 查看
0407 7 网络流 流与割、最大流最小割、Ford-Fulkerson、增广路、二分图匹配 查看
0408 8 NP 与计算困难性 多项式规约、NP、NP 完全、典型规约、co-NP 查看
0409 9 近似算法 负载均衡、中心选择、顶点覆盖、LP rounding、背包近似 查看
0410 10 局部搜索 优化地形、最大割、局部最优、Nash 均衡和稳定性代价 查看
0411 11 随机算法 随机化思想、期望线性性、MAX 3-SAT、Chernoff Bounds 查看

5、复盘顺序

场景 建议顺序
快速补算法主线 0401 -> 0402 -> 0404 -> 0405 -> 0406 -> 0408
刷题前置 0402 -> 0403 -> 0404 -> 0405 -> 0406 -> 0407
图算法专题 0403 -> 0404 -> 0407
困难问题专题 0408 -> 0409 -> 0410 -> 0411
面试复盘 0402 -> 0404 -> 0405 -> 0406 -> 0409

6、统一复盘模板

复盘项 要回答的问题
问题模型 输入、输出、约束、目标函数是什么？
算法策略 属于贪心、分治、DP、流、近似还是随机化？
正确性 用交换论证、归纳、不变式、割性质还是规约证明？
复杂度 时间、空间、最坏、平均、期望或近似比是多少？
边界 空输入、重复元素、不可行实例、退化图如何处理？
实现 能否写出伪代码，并说明关键数据结构？

7、整理口径

算法设计与分析内容跨度很大，博客这里先整理成可复习的知识框架。每章优先保留“为什么这样设计算法”和“怎么证明它对”，代码细节后续结合题目慢慢补。