CSCI3160 期中简略复习

范围：Warm Up 1 至 DP 4，含相关 Tutorial 1–6 内容。本篇概括概念、算法和证明要点；完整推导见详细复习，试卷题干与解答见真题解析。

Warm Up 1：计算模型

RAM 用寄存器、按地址访问的内存和基本指令描述运行。一个机器字的读写、复制、整数运算、比较和跳转按常数成本计；RANDOM(a,b) 均匀抽取闭区间内的整数。该假设只覆盖机器字能够容纳的值。处理整个数组、矩阵或大整数，须按实际访问和运算量计费。

时间数全部基本操作，空间看实际存储需求。 课件的空间定义是最大访问地址；常用的连续存储下与使用单元数量同阶。辅助空间不含输入，但包含递归栈。

确定性算法在固定输入上运行过程固定。随机算法的运行时间可变化；本范围中的随机选择算法答案始终正确，随机性只影响耗时。

Warm Up 2：渐近分析与重试

记号	从某个规模起成立的关系
$f=O(g)$	$f\le cg$ ，渐近上界
$f=\Omega(g)$	$f\ge cg$ ，渐近下界
$f=\Theta(g)$	$c_1g\le f\le c_2g$ ，同阶

常数不得随 $n$ 变化。三个符号不分别表示最坏、最好或平均情况。先选时间函数，再求它的界。固定底数的对数同阶；固定次幂的对数慢于任意正次幂的 $n$ ；固定次幂的 $n$ 慢于固定底数大于 1 的指数。

确定性的最坏时间是 $\max_{|I|=n}T(I)$ 。随机算法通常保证 $\max_{|I|=n}\mathbb E_R[T(I,R)]$ ：固定输入，只对内部随机选择取期望，再要求所有合法输入均满足界。二分查找依靠有序性，每轮排除一半，最坏时间 $O(\log n)$ 。

独立重试中，每轮成功概率为 $p$ 。包含首次成功的尝试总数期望为 $1/p$ ；此前失败次数期望为 $(1-p)/p$ 。若数组 $n$ 个位置中有 $z>0$ 个零，均匀有放回抽样找到零的期望检查次数为 $n/z$ ，但单次运行没有固定的尝试次数上限。

拒绝采样从较大的均匀范围取数，只接受目标范围，其余重试，仍得到均匀输出。公平随机位可生成 $\lceil\log_2n\rceil$ 位数，接受小于 $n$ 的值；接受概率超过 $1/2$ ，期望位生成成本 $O(\log n)$ 。 $n=1$ 直接返回。

Lec 1：递归与选择

递归需要输入含义、返回值、边界和严格缩小的规模；正确性用归纳说明较小问题的正确答案足以构成当前答案。汉诺塔先搬上层 $n-1$ 盘，再搬最大盘，再把上层 $n-1$ 个盘从辅助柱移到终点柱，故 $H(n)=2H(n-1)+1=2^n-1$ 。深度不等于调用数。

选择第 $k$ 小，只递归目标所在的一边。 对互异元素集选枢轴 $v$ ，分成 $L=\{x\le v\}$ 、 $R=\{x>v\}$ 。令 $r=|L|$ ，则：

(S,k)\longrightarrow \begin{cases} (L,k),&k\le r,\\ (R,k-r),&k>r. \end{cases}

本讲随机抽枢轴，若目标所在部分超过 $2n/3$ 就重试，足够小时直接排序。中间固定比例的枢轴都能成功，故每层期望尝试次数是常数。每次划分扫描当前集合，保留规模按比例下降：

n+\frac23n+\left(\frac23\right)^2n+\cdots=O(n).

所以选择的最坏期望时间为 $O(n)$ 。若有确定性线性时间中位数黑盒，可每次平衡划分，得到确定性线性选择；黑盒成本必须计入。几何级数适用条件是固定缩减比例，并且总工作要包含所有递归分支。

Lec 2：分治与合并

归并排序按位置分半，递归排好两边，用双指针每次取较小的首元素。未输出元素的最小者必在两个指针处，因此合并正确。 $T(n)=2T(n/2)+O(n)=O(n\log n)$ ，辅助空间 $O(n)$ 。

逆序对是 $i<j$ 且 $A[i]>A[j]$ ，最多 $n(n-1)/2$ 对。递归同时返回逆序数和有序数组；合并时若 $R[j]<L[i]$ ，新增逆序数为左半剩余元素数，再输出 $R[j]$ 。每个跨边界逆序对恰在右端元素输出时计入一次。线性合并得到 $O(n\log n)$ ；每层重新排序并逐项二分则为 $O(n\log^2n)$ 。

二维支配： $q$ 支配 $p$ 指 $q.x\ge p.x,q.y\ge p.y,p\ne q$ ；输出每个点支配的其他点数。本课 $x$ 坐标互异。先按 $x$ 排序并据此递归分半，只有右半点可能支配左半点。两边递归返回按 $y$ 排序的结果，合并时累计已输出左点数；每输出右点就把这个数加到它的答案。 $y$ 相等先输出左点，纳入等号。总时间 $O(n\log n)$ 。

逆序：右值更小时，数左边尚未输出的元素
支配：输出右点时，数左边已经输出的点

矩阵乘法的输入规模为 $n^2$ 个元素。普通公式 $C_{ij}=\sum_kA_{ik}B_{kj}$ 为 $O(n^3)$ ；普通分块仍需八次半规模乘法。

Strassen 用七次乘法。记

\begin{aligned} p_1&=A_{11}(B_{12}-B_{22}),&p_2&=(A_{11}+A_{12})B_{22},\\ p_3&=(A_{21}+A_{22})B_{11},&p_4&=A_{22}(B_{21}-B_{11}),\\ p_5&=(A_{11}+A_{22})(B_{11}+B_{22}),\\ p_6&=(A_{12}-A_{22})(B_{21}+B_{22}),\\ p_7&=(A_{11}-A_{21})(B_{11}+B_{12}). \end{aligned}

结果为 $C_{11}=p_5+p_4-p_2+p_6$ 、 $C_{12}=p_1+p_2$ 、 $C_{21}=p_3+p_4$ 、 $C_{22}=p_1+p_5-p_3-p_7$ 。展开后抵消即可验证。

T(n)=7T(n/2)+O(n^2)=O(n^{\log_2 7}).

非 2 的幂边长补零到下一个 2 的幂，不改变阶数。

Lec 3：活动选择

目标是在时间区间中选最多个互不相交活动。按结束时间排序，每次取仍兼容且结束最早的活动。本课为闭区间，兼容条件是后一个开始时间严格大于前一个结束时间。排序加扫描为 $O(n\log n)$ 。

交换证明：取一个最优解的首活动 $j$ ，用最早结束活动 $g$ 替换。 $f_g\le f_j$ ，所以原后续活动仍可安排，活动数不变。对剩余活动重复，得到不变式：存在一个最优解包含全部已选活动。 停止时不能再添加活动，该最优解便与当前解相同。这个证明不要求最优解唯一。

Lec 4：最小生成树

MST 是覆盖连通无向图全部顶点、无环且总边权最小的生成树，含 $|V|-1$ 条边。树加一条边会成唯一环，删一条树边会分成两部分。

割性质：任意割的最轻边属于某棵 MST。若原 MST 不含它，加入后在环上删去另一条跨边，权重不增加。唯一最轻跨边属于每棵 MST。

Prim扩展同一棵树。本课以全图最轻边开始，此后每轮取树内到树外的最轻跨边，接入一个新顶点。交换时删去的跨边不会是此前已选的内部边，因此仍存在一棵 MST 包含所有已选边。

实现为每个外部顶点保存到当前树的最小边权 key 和端点 parent。最小堆取出最小 key 顶点；新顶点加入后，只扫描其邻边更新其余 key。每个树外顶点至多出队一次、每边检查常数次，时间 $O((|V|+|E|)\log|V|)$ ，额外数组和堆空间 $O(|V|)$ 。

Kruskal按权重递增检查边，只接受连接不同当前分量的边。它是当前某个分量割上的最轻边，交换可保持此前森林的全部边。并查集维护分量；按大小合并保证树高 $O(\log|V|)$ 。排序主导，总时间 $O(|E|\log|E|)$ 。

环性质：环上唯一最重边不属于任何 MST；有并列时只能保证存在一棵 MST 不含某条指定最重边。全图权重互异可推出 MST 唯一，因为两棵不同 MST 的边集差异中，最轻边可以换掉另一棵中的更重边，造成矛盾。

Lec 5：Huffman 编码

前缀码不允许一个码字成为另一个的前缀。二叉编码树只在叶子放字符，根到叶子的标签是码字，叶子深度是码长。频率归一化为 $p_i$ 后，平均码长为 $\sum_i p_i d_i$ ；出现次数未归一化时，最小化加权深度的目标等价。

算法把每个字符建成一棵带频率的树，用最小堆反复取出两棵最轻树，合成权重为两者之和的新树，再放回。共 $n-1$ 次合并，时间 $O(n\log n)$ ，空间 $O(n)$ 。

正确性分两步。正频率字符的最优树可取为每个内部节点都有两个孩子的二叉树，最深叶子的兄弟也是最深叶子；把最小频率字符换到这两个位置不会增大加权深度，所以存在一棵最优树把两者放成兄弟。再收缩它们，展开所增加的成本恒为 $f_x+f_y$ ，与余树结构无关，因而收缩后的问题也必须最优。递归应用便证明整体最优。并列频率或交换左右子树都可能产生不同最优码。

Lec 6 / DP 1：动态规划的成本

递归可能反复计算相同状态。记忆化在首次计算后缓存，之后直接返回；自底向上按依赖顺序计算。两者使用同一递推。

对 $f(0)=0$ 、 $f(k)=\max_{1\le i\le k}(A[i]+f(k-i))$ ，朴素递归有指数多个调用，但不同状态只有 $n+1$ 个。每个 $k$ 仍枚举 $k$ 种选择，所以填表时间是 $\sum_{k=1}^n k=\Theta(n^2)$ ，空间 $O(n)$ 。状态数乘每状态工作量，才是总时间。

Lec 7 / DP 2：钢条切割

$R[k]$ 为长度恰为 $k$ 的最高收入， $P[i]$ 为一整段长度 $i$ 的售价。先确定第一段长度 $i$ ，余下为同类问题：

R[0]=0,\qquad R[k]=\max_{1\le i\le k}\{P[i]+R[k-i]\}.

任何方案都有第一段，收入不超过相应候选；取最大候选并接上剩余部分最优方案，又能达到这个值。因此等式成立。 $i=k$ 表示不切，必须保留。

按 $k$ 递增填表，枚举所有第一段。时间 $\Theta(n^2)$ ，空间 $O(n)$ 。记录取得最大值时的 first[k]，恢复时反复输出 first[r] 并减少剩余长度，最多 $n$ 步，无须在每格复制整份方案。

Lec 8 / DP 3：依赖顺序与空间

状态必须包含确定子问题所需的全部信息。依赖箭头从先算的状态指向使用它的状态；填表顺序应是依赖图的拓扑顺序。

前缀二维表若依赖上、左、左上，行列递增即可；区间状态若依赖更短区间，按区间长度递增。边界状态必须单独定义，尤其不能对没有合法切分点的集合直接取最大或最小。

一个旧状态不再被任何未来状态使用时，其空间才可复用。只依赖上一行的表可以保留两行；钢条切割可能读取所有更短长度，不能只保留两个值。求值所需信息与恢复方案所需信息也不同。

Lec 9 / DP 4：LCS

子序列允许删除字符但保持相对顺序，子串要求连续。公共子序列的匹配位置在两串中都严格递增，连线不能交叉。

$D[i,j]$ 表示前缀 $X[1..i]$ 、 $Y[1..j]$ 的 LCS 长度：

D[i,j]= \begin{cases} 0,&i=0\text{ 或 }j=0,\\ D[i-1,j-1]+1,&x_i=y_j,\\ \max(D[i-1,j],D[i,j-1]),&x_i\ne y_j. \end{cases}

末尾相等时，存在一份最优解把这对末尾匹配：若都未用可追加，若只用一端可把最后匹配移到两末尾。末尾不等时无法同时使用两端，否则匹配交叉，因此至少删去一端，取两种可能的最大值。

按行列递增填 $(n+1)(m+1)$ 个状态，每格常数工作，时间 $O(nm)$ 、完整表空间 $O(nm)$ 。回溯从 $(n,m)$ 出发：相等则记录字符并走左上；不等则走到保留当前最优值的上方或左方；最后逆序记录。回溯 $O(n+m)$ 。

只求长度时可保留两行，并把较短字符串作列，辅助空间 $O(\min(n,m))$ 。原表被覆盖后，不能直接沿它恢复序列，须另外保留路径或重新计算。

考试证据：知识范围按 Warm Up 1 至 DP 4 编写；真题与重新推导的解答单列于《MT-真题精讲与标准答案》。