研究生课程 · 算法
算法设计与分析
算法是"解决问题的有限指令序列"，复杂度分析回答"它到底多快"。同一问题的两个解法可以相差亿万倍：暴力搜索 TSP 到 30 城已是天文数字，而 Held-Karp 动态规划 2²⁰ 步搞定 20 城。把指数做成多项式，是这门课的全部浪漫。
1 复杂度与渐进记号
概念O、Ω、Θ 与"每秒 10⁸ 次"
O（上界）、Ω（下界）、Θ（同阶）。常用阶：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。
经验法则：1 秒 ≈ 10⁸ 次基本运算 ⇒ n=10⁶ 时 O(n log n) 稳、O(n²)（10¹² 次）已死；n=40 时 O(2ⁿ)（10¹²）也死。
均摊分析（动态数组扩容 O(1) 均摊）；对数从何而来：每步把问题规模砍半。
经验法则：1 秒 ≈ 10⁸ 次基本运算 ⇒ n=10⁶ 时 O(n log n) 稳、O(n²)（10¹² 次）已死；n=40 时 O(2ⁿ)（10¹²）也死。
均摊分析（动态数组扩容 O(1) 均摊）；对数从何而来：每步把问题规模砍半。
随堂检测复杂度
2 分治与主定理
定理T(n) = aT(n/b) + O(nᵈ)
比较 d 与 log_b a：
① d > log_b a ⇒ T = O(nᵈ)（顶层合并主导，如二分查找 a=1,b=2,d=0 → O(log n)）
② d = log_b a ⇒ T = O(nᵈ log n)（均衡，如归并排序 a=2,b=2,d=1 → O(n log n)）
③ d < log_b a ⇒ T = O(n^{log_b a})（叶子主导，如 Strassen 矩阵乘 a=7,b=2 → O(n^2.81)）
例：Karatsuba 大数乘 O(n^1.585)，快排期望 O(n log n)。
① d > log_b a ⇒ T = O(nᵈ)（顶层合并主导，如二分查找 a=1,b=2,d=0 → O(log n)）
② d = log_b a ⇒ T = O(nᵈ log n)（均衡，如归并排序 a=2,b=2,d=1 → O(n log n)）
③ d < log_b a ⇒ T = O(n^{log_b a})（叶子主导，如 Strassen 矩阵乘 a=7,b=2 → O(n^2.81)）
例：Karatsuba 大数乘 O(n^1.585)，快排期望 O(n log n)。
3 排序：从冒泡到快排
定理比较排序的下界
决策树论证：任何比较排序最坏 Ω(n log n)（n! 片叶子的二叉树深度 ≥ log₂n! ≈ n log n）。
冒泡/插入 O(n²)；归并稳定 O(n log n)；快排期望 O(n log n)、最坏 O(n²)（随机化选 pivot 防敌手）；堆排序原地 O(n log n)。
非比较排序突破下界：计数/桶/基数排序 O(n + k)。
冒泡/插入 O(n²)；归并稳定 O(n log n)；快排期望 O(n log n)、最坏 O(n²)（随机化选 pivot 防敌手）；堆排序原地 O(n log n)。
非比较排序突破下界：计数/桶/基数排序 O(n + k)。
4 动态规划
概念最优子结构 + 重叠子问题
DP = 带"记忆化"的递归：把指数级重复子问题压成多项式个状态。
0/1 背包：dp[i][w] = max(dp[i−1][w], dp[i−1][w−wᵢ]+vᵢ)，O(nW)；
LCS：dp[i][j] = dp[i−1][j−1]+1（相等）或 max(dp[i−1][j], dp[i][j−1])，O(mn)——diff 工具的内核；
其他：Floyd 多源最短路 O(n³)、矩阵链乘、编辑距离。
0/1 背包：dp[i][w] = max(dp[i−1][w], dp[i−1][w−wᵢ]+vᵢ)，O(nW)；
LCS：dp[i][j] = dp[i−1][j−1]+1（相等）或 max(dp[i−1][j], dp[i][j−1])，O(mn)——diff 工具的内核；
其他：Floyd 多源最短路 O(n³)、矩阵链乘、编辑距离。
5 贪心算法
概念只看眼前的正确性
贪心 = 每步取局部最优。成立需要贪心选择性质 + 最优子结构（可用交换论证证明）。
正例：活动选择（按结束时间排序）、Huffman 编码（每次合并最小频率）、Kruskal/Prim 最小生成树、Dijkstra（非负权）。
反例：0/1 背包用贪心（按单价）可能错——需要 DP；但分数背包贪心正确。找零钱 {1,5,11}：找 15 元贪心 11+1×4 共 5 枚，最优 5×3 共 3 枚。
正例：活动选择（按结束时间排序）、Huffman 编码（每次合并最小频率）、Kruskal/Prim 最小生成树、Dijkstra（非负权）。
反例：0/1 背包用贪心（按单价）可能错——需要 DP；但分数背包贪心正确。找零钱 {1,5,11}：找 15 元贪心 11+1×4 共 5 枚，最优 5×3 共 3 枚。
6 图算法：BFS/DFS 与最短路
概念搜索的波纹
BFS：队列、按层扩展，O(V+E)，无权图最短路；DFS：栈/递归，拓扑排序、割点、强连通分量。
Dijkstra：非负权单源最短路 O((V+E)log V)（优先队列）；Bellman-Ford 容忍负权 O(VE)；Floyd-Warshall 全源 O(V³)（DP 三重循环）。
MST：Kruskal（并查机）与 Prim。
Dijkstra：非负权单源最短路 O((V+E)log V)（优先队列）；Bellman-Ford 容忍负权 O(VE)；Floyd-Warshall 全源 O(V³)（DP 三重循环）。
MST：Kruskal（并查机）与 Prim。
随堂检测DP · 贪心 · 图
7 NP 完全性概述
概念P、NP 与 NP 完全
P：多项式时间可解；NP：解可在多项式时间被验证。P ⊆ NP（是否相等 = 千禧年难题）。
NP 完全（NPC）：NP 中最难的问题族——SAT 是第一个（Cook-Levin），经多项式归约传递得到 3-SAT、TSP(判定)、顶点覆盖、哈密顿回路、子集和、3-着色……
实务策略：近似算法（顶点覆盖 2 倍近似）、随机化、参数化、指数但剪枝的搜索（分支限界）。
NP 完全（NPC）：NP 中最难的问题族——SAT 是第一个（Cook-Levin），经多项式归约传递得到 3-SAT、TSP(判定)、顶点覆盖、哈密顿回路、子集和、3-着色……
实务策略：近似算法（顶点覆盖 2 倍近似）、随机化、参数化、指数但剪枝的搜索（分支限界）。