CSC5001 期中复习：从读题到写证明

复习餐厅选址时，我能说出“选或不选当前位置”，一写转移式就把三个东西混在了一起：当前位置的利润、最靠后的兼容位置，以及兼容范围内的最优总利润。递推式也有类似的问题。看到 substitution method，我下意识就开始展开求和，没反应过来这道题要求代入归纳假设。

考完回头看，卷上遇到的很多考点复习时都碰过。我把当时最容易写错的几步留下来。上面先查公式和英文指令，下面再看推导和例子。这是复习记录，例题来自复习过程和练习材料。

速查

要查什么	公式或结论	写题时检查
主定理	$T(n)=aT(n/b)+\Theta(n^d)$	比较 $a$ 和 $b^d$，子问题要满足同一缩小比例
线性选择	$T(n)\le T(\lceil n/5\rceil)+T(7n/10+O(1))+O(n)$	每组五个，找 pivot 本身也有递归成本
FFT	$T(N)=2T(N/2)+\Theta(N)$	两个输入统一补零，$N\ge u+v-1$
餐厅选址	$DP(i)=\max\{DP(i-1),p_i+DP(q(i))\}$	$q(i)$ 是前缀边界，$DP(i)$ 不强制选 $i$
Bellman–Ford	$O(nm)$，单源最短路径	第 $n$ 轮仍可松弛说明有源点可达的负环
Floyd–Warshall	$\Theta(n^3)$，所有点对最短路径	中间顶点放最外层，负环看 $d(v,v)<0$
并查集	按秩合并加路径压缩，摊还 $O(\alpha(n))$	只有不同根且同秩合并时，新根的秩才加一

题目里的英文	我需要写什么
Describe / design an algorithm	说清可以执行的步骤和返回值
Write pseudocode	写初始化、循环范围、更新和返回
Explain / justify	给出结论成立的理由
Prove or disprove	判断后给证明、反证或反例
Substitution method	先猜界，再代入归纳假设验证
Tight asymptotic bound	给出紧确的渐近界，通常写 $\Theta$
At most / at least / exactly	最多／至少／恰好，会直接改变边界和转移

递推式

主定理先数实际递归几次。代入法先写要证明的不等式，并让同一个常数覆盖基础情况和递推步骤。

对 $T(n)=aT(n/b)+\Theta(n^d)$，递归树第 $\ell$ 层有 $a^\ell$ 个规模为 $n/b^\ell$ 的子问题，非递归工作量与 $n^d(a/b^d)^\ell$ 同阶。比值小于、等于、大于 $1$ 时，结果分别是 $\Theta(n^d)$、$\Theta(n^d\log n)$、$\Theta(n^{\log_b a})$。逆序对计数和 FFT 都是 $a=b=2,d=1$。例如归并时若右半边当前元素小于左半边当前元素，它和左半边所有尚未合并的元素构成跨区逆序对。内部两类在递归里处理，三类加起来才是总数。

代入法练习是证明 $T(n)=T(n-2)+2\log_2 n$ 属于 $O(n\log n)$。先假设基础成本是固定常数，递推从 $n=3$ 开始。我们从 $n=2,3$ 分别覆盖偶数和奇数，取足够大的固定常数 $c\ge1$，让这两个规模都满足 $T(n)\le cn\log_2 n$。对 $n\ge4$，代入较小规模的界：

$$\begin{aligned} T(n) &\le c(n-2)\log_2(n-2)+2\log_2 n\\ &\le cn\log_2 n-2(c-1)\log_2 n\\ &\le cn\log_2 n. \end{aligned}$$

易混点。我当时写出的是展开求和。展开可以帮助猜量级，题目指定 substitution 时，还要写归纳假设和上面这步不等式。证明也不必从 $n=1$ 开始，因为 $\log_2 1=0$ 盖不住正的基础成本，Big O 允许从足够大的规模开始。

反驳 $3^n=O(2^n)$ 时，我会从定义假设 $3^n\le c2^n$ 对所有 $n\ge n_0$ 成立。除以 $2^n$ 后得到 $n\le\log_{3/2}c$。取整数 $n>\max\{n_0,\log_{3/2}c\}$ 就矛盾。这里最容易漏写的是 $n\ge n_0$。

Assume the bound holds for the smaller subproblem. Substituting it into the recurrence gives …

线性选择

只需要某个排名时，可以用 selection 找门槛。划分后用实际排除的元素数量更新排名。

设 $L,E,G$ 分别存放小于、等于、大于 pivot 的元素。如果目标在 $G$，就在 $G$ 中找第 $k-\lvert L\rvert-\lvert E\rvert$ 小。两边有多长取决于 pivot 和输入，不能直接用原数组长度的一半。

Median of medians 每五个元素分一组，递归选择组中位数的中位数作为 pivot。至少约一半的组中位数不大于它，每个这样的组至少贡献三个不大于它的元素，所以这一侧有约 $3n/10$ 个元素。另一侧同理。划分后只需搜索至多 $7n/10+O(1)$ 个元素，找 pivot 的另一次递归约有 $n/5$ 个元素。两项规模比例之和 $9/10<1$，加上分组和划分的线性成本，总时间为 $O(n)$。

找离中位数最近的 $k$ 个数时，我一开始想扫一遍再维护堆。这里可以先求中位数 $m$，再对距离 $\lvert x-m\rvert$ 做一次选择，找第 $k$ 小距离 $\delta$。全选距离小于 $\delta$ 的元素，再从距离恰好等于 $\delta$ 的元素里补足 $k$ 个。例如集合 $\{1,3,5,7,9\}$ 的中位数为 $5$，若 $k=2$，必须选 $5$，再从 $3$ 和 $7$ 中任选一个。两次线性选择和几次扫描仍是 $O(n)$。

易混点。原元素互不相同也可能产生相同的距离，距离数组要保留重复项。英文里 the first $k$ elements 是前 $k$ 个，the $k$-th smallest element 才是第 $k$ 小的那一个。

FFT

FFT 减半时，系数数量和求值点数量都减半。 对 $P(x)=1+2x+3x^2+4x^3$，偶数项和奇数项分别形成 $E(y)=1+3y$ 和 $O(y)=2+4y$。

$$P(x)=E(x^2)+xO(x^2),\qquad P(-x)=E(x^2)-xO(x^2).$$

在 $1,-1,\mathrm{i},-\mathrm{i}$ 求值时，平方后只有 $1$ 和 $-1$。比如在 $y=1$ 得到 $E(1)=4,O(1)=6$，于是同时得到 $P(1)=10$ 和 $P(-1)=-2$。复用这组结果就是分治合并的具体动作。对 $N$ 个单位根也是如此，两个半规模 FFT 算完后，合并全部点花 $\Theta(N)$，共有 $\log_2 N$ 层合并。

多项式乘法中，两个输入各有 $u,v$ 个系数，结果最多有 $u+v-1$ 个系数。两个输入先补零到同一个 $N$，取不小于 $u+v-1$ 的最小的 2 的幂。接着分别做 forward FFT，逐点相乘，再做一次 inverse FFT。逆变换把单位根换成其倒数，结果各除以 $N$。三次 FFT 和一次线性扫描合计 $O(N\log N)$。

易混点。我复述时把两次正变换的成本按原长度 $u,v$ 分开算了。逐点相乘需要相同的求值点，所以三次变换都按补零后的共同长度 $N$ 计算。$\log_2 N$ 是递归深度，输出仍有 $N$ 个。

动态规划

先写状态表示哪一类解，再问最后一个选择改变了什么。

餐厅位置 $a_1<\dots<a_n$，利润为 $p_i$，两家店至少相距 $L$。设 $DP(i)$ 为从前 $i$ 个位置可取得的最大合法总利润。若选 $i$，更早的所有位置都要满足 $a_j\le a_i-L$。这些位置恰好构成前缀，末尾下标记为 $q(i)$，没有兼容位置时设为 $0$。

$$DP(0)=0,\qquad DP(i)=\max\{DP(i-1),p_i+DP(q(i))\}.$$

不选 $i$ 的最优值来自前 $i-1$ 个位置。选 $i$ 时，可以把兼容前缀里的最优方案接在它前面，间距仍然合法。如果前缀方案的利润更低，就能替换为更好的方案，提高总利润。因此两支取最大，按 $i$ 递增算到 $DP(n)$ 就得到答案。逐个扫描求 $q(i)$ 时，每轮花 $O(i)$，合计 $O(n^2)$ 时间、$O(n)$ 额外空间。

易混点。$q(i)$ 只标记兼容前缀的边界，那个位置本身未必开店。$DP(q(i))$ 存的是整个兼容前缀的最优组合。位置数组从 $1$ 开始，$DP(0)$ 则表示考虑零个候选位置。

题型	状态怎么选
钢条切割	$R(i)$ 存长度 $i$ 的最大收入。枚举第一段长度 $j$，比较 $p_j+R(i-j)$。
无限找零	$B(t)$ 存金额 $t$ 是否可达，枚举最后一枚面额 $x_j$，看 $B(t-x_j)$。$B(0)$ 为真。
每枚硬币最多一次	$B(i,t)$ 加上前 $i$ 枚的限制。选与不选都读上一行 $i-1$。
无限供应但最多 $K$ 枚	$B(k,t)$ 记录剩余枚数限制。选一枚后读 $B(k-1,t-x_j)$。所有 $B(k,0)$ 为真。
酒店停靠	$P(i)$ 存到达酒店 $i$ 的最小罚分，枚举上一站 $j$，增加 $(200-(a_i-a_j))^2$。
TSP	$C(S,j)$ 同时记录已访问集合和当前城市。枚举上一城，再加最后一条边。

TSP 从城市 $1$ 出发，集合 $S$ 不含 $1$，状态 $C(S,j)$ 还没有回到起点。基础值为 $C(\{j\},j)=d_{1j}$，按集合大小递增计算 $\min_{i\in S\setminus\{j\}}\{C(S\setminus\{j\},i)+d_{ij}\}$。访问完所有城市后，要枚举最后一城并加上回到 $1$ 的费用。$O(n2^n)$ 个状态各枚举 $O(n)$ 个候选，时间 $O(n^2 2^n)$，空间 $O(n2^n)$。

Let $DP(i)$ be the maximum total profit obtainable from the first $i$ locations, subject to the minimum-distance constraint.

Any feasible solution either skips location $i$ or chooses it. Each case uses an optimal solution to a smaller subproblem.

最短路径

Bellman–Ford 的阶段限制边数，Floyd–Warshall 的阶段限制中间顶点。 设 $n$ 为顶点数，$m$ 为边数。

Bellman–Ford 的 $D(i,v)$ 是从源点 $s$ 到 $v$、最多用 $i$ 条边的最小代价。$D(0,s)=0$，其余为 $+\infty$。保留上一阶段的值，或者枚举最后一条边：

$$D(i,v)=\min\left\{D(i-1,v),\min_{(u,v)\in E}\left[D(i-1,u)+w(u,v)\right]\right\}.$$

源点无法到达任何负环时，最多 $n-1$ 条边足够。额外一轮若还能改进，就有从 $s$ 可达的负环。若该负环还可达 $v$，到 $v$ 的代价便可任意降低。常见边扫描实现做约 $n$ 轮松弛，时间为 $O(nm)$。

Floyd–Warshall 更新 $d(u,v)\leftarrow\min\{d(u,v),d(u,k)+d(k,v)\}$。$k$ 必须放在最外层，因为每个阶段要更新所有点对，下一阶段才能使用本阶段得到的路径。例如只有边 $1\to3\to4\to2$，每条边权为 $1$。处理 $k=3$ 后得到 $d(1,4)=2$，处理 $k=4$ 时才能用它得到 $d(1,2)=3$。三层循环各枚举 $n$ 个顶点，时间为 $\Theta(n^3)$，二维表空间为 $\Theta(n^2)$。

易混点。Floyd 的负环判断看对角线 $d(v,v)<0$。普通的负距离可能只来自一条负权边。

并查集

两个不同的根同秩时，新根的 rank 加一。路径压缩后不调整 rank。 合并前先找根，小秩根的父指针指向大秩根。根的父指针指向自己。

例如合并后得到 $4\to3\to1$，箭头表示子节点指向父节点。执行 Find(4) 时沿链找到 $1$，然后把这条路径上的节点直接接到根。集合成员和代表保持原样，查找路径缩短。只做按秩合并时单次查找最坏 $O(\log n)$。再加路径压缩后，操作序列的摊还成本可写作 $O(\alpha(n))$。

复习这类操作题时，我会把“挂到下面”换成明确的父指针赋值，避免把树根和箭尾搞混。写伪代码也一样。比如说清楚下标从 $1$ 开始，以及 for 循环是否包含上界，再给具体的更新式。