📁 算法设计与分析
期末速成：算法设计与分析
串起复杂度、分治、动态规划、贪心、图算法与 P、NP、NPC，集中整理高频公式、算法选型和考场作答模板
往年题
0 folders, 5 posts
算法、正确性与复杂度
从算法的定义、RAM 模型、循环不变式到最坏和平均复杂度，建立算法分析的基本语言
渐近记号与函数增长
讲清 O、Ω、Θ、o、ω 的量词含义、运算规则、常见函数阶和易混结论
归并排序与分治框架
用归并排序理解分、治、合，证明正确性并推导 Θ(n log n) 复杂度
递推式求解：展开、递归树与主定理
系统整理算法复杂度递推式的三种解法，并解释主定理三种情形为何成立
最大连续子数组：从暴力到分治
以股票收益和最大子段和为例，推导跨中点合并、正确性和 Θ(n log n) 分治算法
逆序对计数与快速排序
在一次课中串起归并计数、分区操作、快速排序正确性以及随机化平均复杂度
选择问题：第 k 小元素
从排序、Quickselect 到 median of medians，理解期望线性与最坏线性选择算法
堆排序与比较排序下界
从完全二叉树、维护堆性质到堆排序，并用决策树证明 Ω(n log n) 下界
多项式乘法与快速傅里叶变换
从系数表示、点值表示到单位根分治，解释 FFT 如何把多项式乘法降到 O(n log n)
0-1 背包与动态规划入门
从暴力子集到状态转移，讲清最优子结构、重叠子问题、一维压缩和方案恢复
最大连续子数组：动态规划解法
从“必须以当前位置结尾”推导 Kadane 算法，并讲清边界、方案恢复和分治解法的关系
最长公共子序列
从子序列与子串的区别出发，推导 LCS 状态转移、回溯方案和空间优化
最小编辑距离
用前缀动态规划统一插入、删除、替换，讲清转移方向、初始化与编辑序列恢复
钢条切割
用钢条切割理解自顶向下记忆化、自底向上动态规划和最优方案恢复
矩阵链乘法
从括号化顺序到区间动态规划，推导最少标量乘法次数并恢复最优方案
最优二叉搜索树
在已知访问概率时，用区间动态规划构造期望搜索代价最小的二叉搜索树
分数背包与贪心方法
从单位价值排序推导分数背包，理解贪心选择性质、交换论证及其适用边界
Huffman 编码
从前缀码和编码树出发，推导 Huffman 贪心合并、正确性与压缩实现要点
活动选择问题
用最早结束时间贪心选择最多互不冲突活动，并用交换论证解释为何正确
图的基本概念与表示
梳理有向图、无向图、路径、环、连通、树、欧拉道路，以及邻接矩阵和邻接表
广度优先搜索
从按层扩展理解 BFS、队列不变量、无权最短路、BFS 树与常见应用
深度优先搜索
理解 DFS 的深入与回溯、深度优先森林、时间戳、无向边分类和线性复杂度
有向图上的 DFS 与边分类
用颜色和时间戳区分树边、后向边、前向边、横向边，为判环和拓扑排序打基础
有向环检测与拓扑排序
从后向边与完成时间理解 DAG，掌握 DFS 和 Kahn 两种拓扑排序方法
强连通分量
从缩点 DAG 理解强连通结构，并推导 Kosaraju 两遍 DFS 算法及其正确性
最小生成树
从割性质与安全边理解 Prim、Kruskal 算法，区分生成树、最短路与非连通情形
图中的最短路径
统一理解松弛操作，以及 BFS、Dijkstra、Bellman-Ford 和 Floyd-Warshall 的适用条件
二分图最大匹配
从交替路与增广路理解匈牙利算法，掌握匹配最大性的判据和复杂度
最大流与最小割
从容量、流守恒和残量网络推导 Ford–Fulkerson、Edmonds–Karp 与最大流最小割定理
P、NP 与 NP 完全
从判定问题、证书验证和多项式规约理解复杂度类别，以及如何证明 NP 完全
期末复习：算法设计与分析知识地图
按分析方法、分治、动态规划、贪心、图算法和复杂度理论串联全课程，并给出选型清单
作业一：递推式与基础算法
整理递推式分析、组合数归纳证明，以及错排、众数和特殊逆序对三道编程题
作业二：动态规划
讲解四次方数分解、最长公共子序列、最大全 1 正方形和双圆覆盖，并复盘原实现问题
作业三：Huffman、搜索、动态规划与博弈
整理 Huffman 压缩实验、引水入域、树上选点和永夜的报应四项作业，并解释建模关键
作业四：图算法综合
讲解关押罪犯、方格选数、最小生成树和道路升级，串联二分图、并查集、最大流与分层最短路