期末速成：算法设计与分析

这篇不是把三十多讲压缩成一张公式表，而是给考前建立一条可执行的思考链：先判断题型，再选范式，最后写正确性与复杂度。如果一道题只写了“用动态规划”或“用贪心”，通常拿不到完整分；真正要交付的是状态、转移、边界、顺序、答案位置，以及为什么正确。

先记住这张总图

题目特征	第一反应	必须补上的证明
规模被拆成若干独立子问题	分治	子问题覆盖全部情况，合并不遗漏
同一子问题反复出现，要求最优值或方案	动态规划	最优子结构与状态定义
每步都想立即作出不可撤销选择	贪心	交换论证或割性质
无权最短路、按层扩展	BFS	首次到达即为最短距离
依赖关系、环、连通结构	DFS	发现/完成时间的性质
非负边权单源最短路	Dijkstra	已确定结点不会再被改小
允许负边、要求检测负环	Bellman–Ford	每轮增加允许使用的边数
DAG 上的最短路或依赖计算	拓扑序 DP	所有前驱先于当前结点处理
二分图一对一分配	二分图匹配	增广路使匹配数增加 1
容量、互斥占用、最多通过多少单位	最大流	建图口径与流量守恒
要证明问题是 NPC	归约	已知 NPC 问题 $A\le_p B$ ，方向不能反

一、复杂度：先确定变量，再做渐近分析

1. 常见增长速度

从慢到快大致是

1\prec\log n\prec(\log n)^k\prec n^\varepsilon \prec n\log n\prec n^2\prec n^k\prec c^n\prec n!\prec n^n,

其中 $k>1$ 、 $\varepsilon>0$ 、 $c>1$ 都是常数。

常见等价关系：

\log_a n=\Theta(\log n), \qquad \sum_{i=1}^n\frac1i=\Theta(\log n),

\binom n{k}=\Theta(n^k)\quad(k\text{ 为常数}), \qquad \binom n{n/2}=\Theta\left(\frac{2^n}{\sqrt n}\right).

一个容易丢分的细节：若输入是整数 $n$ 本身，输入长度是 $\Theta(\log n)$ 个比特。一个对数值 $n$ 耗时 $O(n)$ 的算法，对输入长度来说其实是指数时间。

2. 三种记号

$O(g(n))$ ：渐近上界；
$\Omega(g(n))$ ：渐近下界；
$\Theta(g(n))$ ：上下界同时成立，增长阶相同。

“最坏情况是 $O(n^2)$ ”只给上界；若能证明既不会超过也不会低于该量级，才写 $\Theta(n^2)$ 。

3. 主定理

对

T(n)=aT(n/b)+f(n),

先算临界项 $n^{\log_ba}$ ：

若 $f(n)=O(n^{\log_ba-\varepsilon})$ ，递归部分更大：

$T(n)=\Theta(n^{\log_ba}).$
若 $f(n)=\Theta(n^{\log_ba}\log^k n)$ ，两部分同阶：

$T(n)=\Theta(n^{\log_ba}\log^{k+1}n).$
若 $f(n)=\Omega(n^{\log_ba+\varepsilon})$ ，且满足正则条件，合并成本更大：

$T(n)=\Theta(f(n)).$

主定理不能覆盖所有递推。遇到 $T(n)=T(n-2)+n^2$ ，直接展开成平方和；遇到 $T(n)=T(\sqrt n)+\log n$ ，观察每层代价为 $\log n/2^i$ 。

4. 比较排序下界

基于比较的排序可表示为决策树。 $n$ 个互异元素有 $n!$ 种排列，因此树至少有 $n!$ 个叶子，最坏树高满足

h\ge\lceil\log_2(n!)\rceil=\Omega(n\log n).

归并排序、堆排序能达到 $O(n\log n)$ ，所以比较排序的最优最坏复杂度是 $\Theta(n\log n)$ 。

二、分治：分、治、合

1. 归并排序与逆序对

归并排序把数组平分、递归排序，再在线性时间合并：

T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n).

统计逆序对只需在合并时补一句：当右半当前元素小于左半当前元素时，它与左半所有尚未合并元素都构成逆序，数量一次增加 mid - i + 1。

2. 快速排序与选择

快速排序每次围绕枢轴划分：平均 $\Theta(n\log n)$ ，最坏 $\Theta(n^2)$ 。随机枢轴降低持续极端不平衡的概率，但不改变最坏上界。

快速选择只递归进入包含第 $k$ 小元素的一侧，期望时间 $O(n)$ 。若要求确定性最坏 $O(n)$ ，用五个一组的中位数的中位数保证每轮排除常数比例元素。

3. 最大连续子数组

分治解法的跨中点答案由“左侧最大后缀 + 右侧最大前缀”构成，复杂度 $O(n\log n)$ 。动态规划可以进一步做到 $O(n)$ ：

dp[i]=\max\{a_i,dp[i-1]+a_i\}.

这里正好说明：同一道题可以有不同范式，考试时要看题目要求的复杂度和课程章节。

4. FFT 只抓住三件事

多项式系数卷积的朴素复杂度是 $O(n^2)$ ；在足够多的点上求值后，乘法变成逐点相乘；FFT 用奇偶拆分在 $O(n\log n)$ 完成求值和插值。流程是

\text{系数}\xrightarrow{\mathrm{FFT}}\text{点值} \xrightarrow{\text{逐点乘}}\text{乘积点值} \xrightarrow{\mathrm{IFFT}}\text{乘积系数}.

三、动态规划：把“历史”压进状态

1. 标准作答模板

任何 DP 题都按以下顺序写：

状态： $dp[\cdots]$ 精确表示什么；
选择：最后一步可能有哪些互斥情况；
转移：从哪些更小状态得到当前状态；
边界：空集合、长度 0、容量 0 如何取值；
计算顺序：保证依赖状态先算；
答案：最终读哪个状态；
复杂度：状态数乘每个状态的转移数；
恢复方案：需要方案时保存前驱或回溯决策。

2. 0-1 背包

令 $dp[i][c]$ 表示前 $i$ 件物品在容量 $c$ 下的最大价值：

dp[i][c]=\max\left\{dp[i-1][c],dp[i-1][c-w_i]+v_i\right\}.

时间 $O(nW)$ 。压成一维后容量必须从大到小枚举，否则当前物品会被重复使用，悄悄变成完全背包。

3. 最长公共子序列与编辑距离

LCS：

dp[i][j]= \begin{cases} dp[i-1][j-1]+1,&x_i=y_j,\\ \max\{dp[i-1][j],dp[i][j-1]\},&x_i\ne y_j. \end{cases}

编辑距离：若末尾相同就继承 $dp[i-1][j-1]$ ；否则在删除、插入、替换三个前驱中取最小再加 1。

4. 区间 DP

矩阵链乘法令 $m[i][j]$ 为 $A_i\cdots A_j$ 的最少标量乘法次数：

m[i][j]=\min_{i\le k<j} \{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j\}.

戳气球也要枚举区间内最后一个被戳的气球，最后一步确定后左右才真正独立。区间 DP 通常按区间长度从短到长计算。

5. 最优二叉搜索树

枚举根 $r$ ，把左右子树代价相加，再加整个区间所有键被向下推一层产生的概率和。核心不是背公式，而是理解“选根后左右独立，所有结点深度统一增加 1”。

四、贪心：选择容易，证明最难

1. 交换论证模板

设最优解没有采用贪心选择。找到其中第一个与贪心不同的位置，把最优解中的选择与贪心选择交换，并证明：

交换后仍可行；
目标值不会变差。

于是存在一个包含贪心选择的最优解，删去已决定部分后递归成立。

2. 三个经典问题

分数背包：按单位重量价值 $v_i/w_i$ 降序；物品可切分，所以交换成立。
活动选择：按结束时间最早排序；它为后续留下最长可用时间。
Huffman 编码：每次合并频率最小的两个结点；最终加权路径长度等于每次合并权重之和。

0-1 背包不能照搬单位价值贪心，因为不可切分会造成剩余容量碎片。

3. 最小生成树

割性质：对任意割，跨越该割的最轻边一定属于某棵 MST。

Kruskal：全局按边权排序，用并查集跳过成环边， $O(E\log E)$ ；
Prim：从一个顶点开始，每次加入连接树内外的最轻边；二叉堆邻接表实现常写 $O(E\log V)$ 。

五、图算法：先看边权和图类型

1. BFS 与 DFS

BFS 用队列按层扩展，无权图中第一次到达顶点时的边数最少，邻接表复杂度 $O(V+E)$ 。

DFS 用递归或栈沿一条路径深入，适合：

判断环；
拓扑排序；
找连通分量；
记录发现与完成时间；
构造强连通分量算法。

有向图拓扑排序可以把 DFS 完成时间逆序输出；若发现指向灰色顶点的回边，则存在有向环，拓扑序不存在。

2. 强连通分量

Kosaraju 的两遍 DFS：

在 $G^R$ 上 DFS，记录完成时间；
按完成时间从大到小在 $G$ 上启动 DFS；
每棵 DFS 树就是一个 SCC。

邻接访问顺序不同会改变发现/完成时间，但不会改变 SCC 的集合。

3. 最短路选型

条件	算法	典型复杂度
无权图或等权图	BFS	$O(V+E)$
非负边权、单源	Dijkstra	$O((V+E)\log V)$
可含负边、单源	Bellman–Ford	$O(VE)$
DAG	拓扑序松弛	$O(V+E)$
全源最短路	Floyd–Warshall	$O(V^3)$

Dijkstra 最关键前提是所有边权非负。看到负边就要立即停下，不能只说“这个负边看起来不会影响答案”。

4. 匹配与最大流

二分图匹配可以不断寻找增广路；每找到一条增广路，沿路把“未匹配/已匹配”状态翻转，匹配数增加 1。

最大流建模要逐项说明：

点代表什么；
边代表允许什么行为；
容量限制什么资源；
源点和汇点为何这样连接；
整数流如何还原为题目方案。

顶点不能重复使用时常用拆点：把顶点 $v$ 拆成 $v_{in}\to v_{out}$ ，中间边容量设为 1。

Edmonds–Karp 每次用 BFS 找最短增广路，复杂度为

O(VE^2).

六、P、NP、NP-hard、NPC

P：确定性算法可在多项式时间解决的判定问题；
NP：给定证书后，可在多项式时间验证的判定问题；
NP-hard：所有 NP 问题都能多项式归约到它；它不一定属于 NP；
NPC：既属于 NP，又是 NP-hard。

证明新问题 $B$ 是 NPC：

给出证书和多项式验证器，证明 $B\in NP$ ；
选择已知 NPC 问题 $A$ ；
在多项式时间把 $A$ 的任意实例变成 $B$ 的实例；
证明“原实例为 YES 当且仅当新实例为 YES”。

归约方向必须是

A\le_pB.

因为我们要利用已知困难的 $A$ 证明 $B$ 至少一样难。写成 $B\le_pA$ 只能说明 $B$ 不比 $A$ 更难。

固定大小的团要特别小心：判断是否存在大小为 5 或 10 的团，可以枚举 $O(n^5)$ 或 $O(n^{10})$ 个顶点组，指数是常数，所以仍是多项式时间。

七、考场完整作答模板

算法设计题可以直接按下面七段写：

建模与核心观察：为什么这题属于该范式；
数据结构：数组、队列、堆、并查集还是图；
状态或不变量：循环过程中始终保证什么；
伪代码：边界、循环范围和更新顺序写清；
正确性：归纳、交换、割性质或反证；
复杂度：分别算时间和额外空间；
方案恢复：题目要求输出方案时，说明前驱如何保存。

最后用三十秒检查：

下标从 0 还是 1 开始？
空输入、单元素、不可达如何处理？
一维背包容量方向对吗？
Dijkstra 是否存在负边？
图是有向还是无向？
归约方向是否写反？
复杂度中的 $V,E,n,W$ 分别代表什么？

把这些边界写出来，通常比再多堆一个算法名更能拿分。