期末复习：算法设计与分析知识地图

这门课不是几十个互不相关的算法。真正需要建立的是三层能力：准确建模，识别算法范式，最后用不变量或结构性质证明正确并分析复杂度。

1. 复杂度分析

必须会：

用 $O$ 、 $\Omega$ 、 $\Theta$ 区分上界、下界和紧确界；
丢掉常数和低阶项，但不把不同变量随意合并；
分析循环、递归树、代入法和主定理；
区分最坏、平均、期望与摊还复杂度；
理解比较排序的 $\Omega(n\log n)$ 决策树下界。

主定理先比较 $f(n)$ 与 $n^{\log_ba}$ ，再检查对应条件。套不上时改用递归树或其他方法，不要硬套。

2. 分治

共同结构是“分成独立子问题、递归求解、合并”：

问题	分解与合并	复杂度
归并排序	对半排序，线性归并	$O(n\log n)$
逆序对	子区间计数，归并时数跨区间对	$O(n\log n)$
最大连续子数组	左、右、跨中点三类	$O(n\log n)$
快速排序	按枢轴划分，无显式合并	平均 $O(n\log n)$
线性选择	好枢轴丢掉常数比例元素	$O(n)$
FFT 多项式乘法	奇偶拆分、单位根求值	$O(n\log n)$

写分治算法要同时说清递归规模、子问题数量与合并代价。

3. 动态规划

识别信号是最优子结构与重叠子问题。标准作答顺序：

定义状态，解释每个下标的语义；
写边界；
从最后一个决策推导转移；
给计算顺序；
指出答案位置；
分析状态数与每状态转移成本；
若要求方案，记录前驱或决策。

问题	关键状态
0-1 背包	前 $i$ 件、容量 $c$
最大子数组	必须以 $i$ 结尾
LCS / 编辑距离	两个序列前缀
钢条切割	剩余长度
矩阵链 / OBST	连续区间 $[i,j]$
Floyd–Warshall	允许的中间点集合

空间压缩前先看依赖方向。0-1 背包容量倒序、完全背包正序，是高频易错点。

4. 贪心

贪心要证明“当前选择可以出现在某个最优解中”，常用交换论证或割性质：

分数背包：单位价值最高，依赖可切分；
Huffman：合并最低频的两个结点；
活动选择：选结束最早的兼容活动；
MST：选择尊重当前边集之割上的轻边；
Dijkstra：确定当前距离最小顶点，依赖非负边权。

同样的直觉换一个约束就可能失效：0-1 背包不能按单位价值贪心，带负边不能用 Dijkstra，加权活动选择需要 DP。

5. 图遍历与结构

BFS：队列、按层、无权最短路、二分图；
DFS：递归栈、发现/完成时间、边分类；
有向环：DFS 后向边；
拓扑排序：DFS 完成时间逆序或 Kahn 入度法；
SCC：转置图加两遍 DFS，缩点后为 DAG。

使用邻接表时遍历复杂度是 $O(V+E)$ 。非连通图要有外层循环。

6. 图优化算法选型

目标与约束	算法
无向图连通总成本最小	Prim / Kruskal
无权单源最短路	BFS
非负权单源最短路	Dijkstra
可含负边单源最短路	Bellman–Ford
所有点对最短路	Floyd–Warshall
二分图最大匹配	增广路 / 匈牙利算法
容量网络最大输送量	Ford–Fulkerson / Edmonds–Karp

MST、最短路径和最大流的目标函数完全不同，不能看到“带权图”就混用。

7. 匹配与流的共同核心

二分图匹配通过交替增广路反转选边；最大流通过残量增广路增加或撤回流量。两者都用“允许反悔的残量结构”修正早期选择。单位容量网络可把二分图匹配化为最大流。

最大流结束时，从源点在残量图中的可达集直接给出一个同值最小割。

8. P、NP、NPC

$P$ ：多项式时间可解；
$NP$ ：多项式长度证书可在多项式时间验证；
NP-hard：所有 NP 问题都能规约到它；
NP-complete：既在 NP 中又 NP-hard。

证明新问题 $B$ 为 NPC：先证 $B\in NP$ ，再从已知 NPC 问题 $A$ 构造 $A\le_p B$ 。规约箭头方向是最常见失分点。

9. 考场作答模板

对设计题至少交代：

输入、输出和必要假设；
状态或维护量的精确定义；
算法步骤或伪代码；
正确性依据：归纳、不变量、交换论证、割性质或最优子结构；
时间和空间复杂度；
边界条件与不适用条件。

只有一个算法名字或一段没有解释的代码，通常不能完整覆盖得分点。

10. 最后一分钟检查

下标是否越界，空输入和全负数是否处理；
“最短”是边数、权重，还是总树权；
图是有向还是无向，是否连通，边权能否为负；
DP 的循环方向会不会重复使用同一物品；
复杂度基于邻接表还是矩阵；
规约方向和“当且仅当”两边是否都证明。

能回答这些问题，说明学到的已经不是算法清单，而是一套可以迁移的解题方法。

11. 串讲补充：四个典型分治问题

11.1 字符串等价：先求唯一的规范形式

若偶数长度的字符串允许递归交换左右两半，直接枚举交换方式会产生大量重复。更好的做法是给每个等价类选一个唯一代表：

长度为奇数时，规范形式就是字符串本身；
长度为偶数时，递归求左右两半的规范形式；
把较小的一半放在前面，较大的一半放在后面。

记结果为 $C(s)$ ，则两个字符串等价当且仅当 $C(A)=C(B)$ 。这里真正的技巧不是“递归比较更多情况”，而是利用等价关系的传递性把所有等价字符串压到同一个标准答案。若每层直接比较和拼接字符串，常见实现为 $O(n\log n)$ 。

11.2 好芯片占多数：淘汰时保持多数性质

好芯片报告一定正确，坏芯片的报告不可信，并且好芯片严格多于坏芯片。两两互测时：

只有双方都报告对方为“好”，才保留其中一片；
其他三种报告组合都丢掉这一对。

对于偶数片芯片，设“好—好”组有 $g$ 组、“坏—坏”组有 $b$ 组。原集合中好芯片更多会推出 $g>b$ ，所以每组最多留一片后，好芯片仍然严格占多数。若数量为奇数，可先让其他芯片多数表决轮空芯片：它若为好就直接结束，否则删掉后再做偶数规模的淘汰。

每轮规模至少减半，全部互测次数满足

T(n)=T(n/2)+O(n)=O(n).

这道题最重要的不是递归形式，而是回答：缩小规模以后，“好芯片仍占多数”这个前提为什么没有丢？

11.3 快速幂与矩阵快速幂

计算 $a^n$ 时没有必要递归计算两遍相同的 $a^{\lfloor n/2\rfloor}$ ：

a^n= \begin{cases} (a^{n/2})^2, & n\text{ 为偶数},\\ (a^{(n-1)/2})^2a, & n\text{ 为奇数}. \end{cases}

因此 $T(n)=T(n/2)+O(1)=O(\log n)$ 。把标量乘法换成矩阵乘法，利用

\begin{bmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{n},

便可在 $O(\log n)$ 次常数阶矩阵乘法内求出 Fibonacci 数。这里的提速来自“两个子问题完全相同，只算一次”，不是来自把问题机械地切成两份。

11.4 平面最近点对：预排序消掉递归中的重复工作

先按横坐标和纵坐标各排序一次，用中线把点集等分。递归得到左右两侧的最短距离 $\delta_L$ 、 $\delta_R$ ，令 $\delta=\min(\delta_L,\delta_R)$ 。跨中线的更优点对只可能出现在宽度 $2\delta$ 的条带里；按纵坐标扫描时，每个点只需与后面常数个候选点比较。

若每层递归重新排序，会得到 $O(n\log^2 n)$ ；若把已排序数组线性拆给两个子问题，则

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

这正是课件所说的“增加预处理、减少每层合并成本”。

12. 串讲补充：把动态规划状态写准确

12.1 三角形最小路径和

令 $dp[i][j]$ 表示走到第 $i$ 行第 $j$ 个元素的最小路径和，则

dp[i][j]=a[i][j]+\min\bigl(dp[i-1][j-1],dp[i-1][j]\bigr).

不存在的父结点按 $+\infty$ 处理，答案是最后一行的最小值。状态数为三角形中的元素数，复杂度为 $O(n^2)$ 。

12.2 最长上升子序列

令 $dp[i]$ 表示必须以 $a_i$ 结尾的最长严格上升子序列长度：

dp[i]=1+\max_{j<i,\,a_j<a_i}dp[j],

没有合法 $j$ 时取 $1$ ，最终答案是 $\max_i dp[i]$ ，而不是固定取 $dp[n]$ 。朴素实现为 $O(n^2)$ ；维护各长度子序列的最小末尾值可优化到 $O(n\log n)$ 。

12.3 词典分词

令 $dp[i]$ 表示前 $i$ 个字的最少片段数，枚举最后一段的起点 $j$ ：

dp[i]=\min_{0\le j<i}\left(dp[j]+ \begin{cases} 1, & s[j:i]\text{ 在词典中},\\ i-j, & \text{否则按单字切分}. \end{cases}\right)

记录取得最小值的 $j$ 就能回溯分词方案。即使词典查询是 $O(1)$ ，枚举所有 $(j,i)$ 仍是 $O(n^2)$ ；只有再限制最大词长等条件，才可能把它降到近似线性。这是串讲材料复杂度标注中容易忽略的一层循环。

12.4 投资分配

有 $m$ 单位资金和 $n$ 个项目， $f_k(y)$ 是给项目 $k$ 投入 $y$ 的收益。令 $F[k][x]$ 表示把 $x$ 单位资金分给前 $k$ 个项目时的最大收益：

F[k][x]=\max_{0\le y\le x}\bigl(F[k-1][x-y]+f_k(y)\bigr).

表中有 $nm$ 个状态，每个状态最多枚举 $m+1$ 种投入量，因此复杂度为 $O(nm^2)$ 。若要输出方案，再记录每个状态选择的 $y$ 并逆序回溯。

12.5 鸡蛋掉落

直接定义“楼层数、鸡蛋数对应的最少次数”会在每个状态里枚举试验楼层，得到较重的转移。更清晰的反向状态是： $dp[e][t]$ 表示用 $e$ 个鸡蛋、最多试 $t$ 次，最多能确定多少层：

dp[e][t]=dp[e-1][t-1]+1+dp[e][t-1].

当前鸡蛋若碎，能覆盖下面的 $dp[e-1][t-1]$ 层；若不碎，能覆盖上面的 $dp[e][t-1]$ 层；中间再加当前试验层。逐步增加 $t$ ，直到 $dp[k][t]\ge n$ ，这个 $t$ 就是答案。

12.6 两类区间 DP

相邻石子合并时，令区间和为 $S(i,j)$ 。若题目求最大合并得分，则

dp[i][j]=\max_{i\le k<j}\bigl(dp[i][k]+dp[k+1][j]+S(i,j)\bigr).

若求最小得分，只需把 $\max$ 改为 $\min$ 。区间按长度递增计算，复杂度为 $O(n^3)$ 。

戳气球则要反过来考虑“区间中最后一个被戳的气球”。在两端补 $1$ 后，令 $dp[i][j]$ 表示开区间 $(i,j)$ 的最大收益：

dp[i][j]=\max_{i<k<j}\bigl(dp[i][k]+dp[k][j]+a_i a_k a_j\bigr).

选择“最后一个”以后，它的左右邻居才固定为 $i,j$ ，这正是区间 DP 能成立的原因。

13. 串讲补充：贪心与复杂度边界

13.1 单机任务调度

所有任务从时刻 $0$ 起在一台机器上依次执行，目标是最小化完成时间之和。应按加工时间从短到长排列。若相邻两项满足 $t_i>t_j$ ，交换后总完成时间减少 $t_i-t_j>0$ ；不断消除逆序，便得到最优顺序。这是相邻交换论证的标准模板。

13.2 合并果子与相邻石子不要混淆

若每次可以任选两堆合并，并要最小化所有合并代价之和，就像 Huffman 编码一样，每次从最小堆取出两堆合并，再把新堆放回最小堆，复杂度为 $O(n\log n)$ 。

若题目限制只能合并相邻石堆，选择空间已经改变，通常应使用上一节的区间 DP。看到“合并”二字不能直接套最小堆，先核对“任意两堆还是只能相邻”以及“求最小还是最大”。

13.3 跳跃游戏

求到达终点的最少跳数时，把当前一次跳跃能够到达的位置看成一层。扫描这一层的所有位置，维护下一层最远能到达的下标；扫描完当前层才把步数加一。每个位置只访问一次，复杂度为 $O(n)$ 。

它不是在每一步只看眼前跳得最远的位置，而是用当前层的所有选择共同确定下一层边界，因此不会错过“眼前较近、下一跳更远”的候选。

13.4 环形加油站

令差值 $d_i=a_i-b_i$ 。若 $\sum_i d_i<0$ ，总油量不足，任何起点都不可能成功。否则从左到右累加当前油量；一旦从候选起点 $s$ 出发在位置 $i$ 变成负数， $s$ 到 $i$ 之间的任何位置也不可能跨过 $i$ ，于是把新候选设为 $i+1$ 并重新累计。

一次扫描即可找到起点，复杂度为 $O(n)$ 。证明的核心是一次失败能整体排除一段候选，而不是逐个起点模拟一圈。

13.5 国王游戏

第 $i$ 位大臣左右手数字为 $a_i,b_i$ ，其收益取决于前面所有人的左手乘积再除以自己的 $b_i$ 。为最小化最大收益，应按 $a_i b_i$ 从小到大排列大臣。

证明只看相邻两人：把他们两种次序下可能出现的最大收益写出来，公共的前缀乘积可以约去；当 $a_i b_i\le a_j b_j$ 时，让 $i$ 在 $j$ 前不会使最大值更大。不断交换逆序对即可得到全局最优排列。

13.6 双机调度为什么出现在 NP-hard 例子里

把任务分到两台相同机器，使较晚停机时间最小，等价于让一台机器承担的总时长尽量接近总时长 $T$ 的一半：

\max \sum_i t_i x_i \quad\text{s.t.}\quad \sum_i t_i x_i\le \lfloor T/2\rfloor, \quad x_i\in\{0,1\}.

这就是 0-1 背包 / 划分问题的结构。加工时间若是整数，可以做依赖数值大小的伪多项式 DP；但对一般二进制输入，不能因此宣称它有关于输入长度的多项式时间精确算法。这里连接了“会写一个 DP”和“理解 P、NP、NP-hard 的计算边界”两部分内容。