CSCI3160 Quiz 复习笔记：Warm Up 至 Greedy 2

覆盖范围：L00A、L00B、L01、L02、L03、L04；对应 6 份课件，26 个知识条目，无缺讲。

定位：按课件顺序复习定义、算法执行、复杂度和正确性证明；可以直接用作考前复习主笔记。范围解释：“第一个 PPT”按最早的 Warm Up 01 起算；“greddy 2”按 Greedy 02（最小生成树）理解，包含这一整讲。编写日期：2026-09-30。基于逐讲伴读整理；页码沿用原 PDF 页号。

先明确复习边界

顺序	课件	本次要掌握的内容
L00A	Warm Up 01（本地课件）	RAM、原子操作、时间与空间、随机运行时间
L00B	Warm Up 02（本地课件）	最坏时间、最坏期望、二分查找、随机找零
L01	Recursion / Repeating / Geometric Series（本地课件）	汉诺塔、秩、随机缩减、线性期望选择
L02	Divide and Conquer（本地课件）	归并排序、逆序对、二维支配、Strassen
L03	Greedy 01（本地课件）	活动选择、交换论证、贪心前缀
L04	Greedy 02（本地课件）	生成树、Prim、MST 安全扩张证明

截至 Greedy 2，不包括 Greedy 3 的 Huffman、动态规划或后续图算法。Kruskal 属于单独的 T05，本笔记不将它扩充成必复习章节；Prim 的实现解释用于补足 L04 p.22。原文件名的“隐藏”是历史网页状态标记，本次复习范围以你的要求为准。

证据说明：A 级表示往年题考过对应内容；C 级表示根据知识结构整理的通识复习角度。往年卷不是本次 Quiz 的考纲。以下优先级是学习建议，不是题目预测。

L00A：先知道算法在数什么

1. RAM、内存与原子操作

一句话：RAM 是一套统一的计费规则；算法时间按实际执行的基本操作数计算。

直觉：同一段程序换电脑会改变秒数，却不会改变其基本操作随输入规模增长的方式。RAM 让我们暂时忽略机器差异，比较算法本身。

形式：每个内存单元和寄存器保存一个 $w$ 位字；本课程有 8 个寄存器。允许常量初始化、寄存器复制、整数算术、比较与分支、按地址读写内存，以及均匀随机抽样。一次允许的原子操作按常数时间计。

算例：讲义 p.7 的整数除法为 $6/3=2$ 、 $5/3=1$ 。后者不是浮点数。补充示意：地址寄存器为 7，内存第 7 格为 23，则读取得到的是 23，不是 7；读、加一、写回是不同操作，初始化也要另计。

联系与误区：地址与内容不同；8 个寄存器不限制输入只能有 8 个元素；常数时间算术针对模型中的字，不能据此声称任意长度整数乘法都是一步。

出处：#L00A-01（L00A p.4–5）、#L00A-02（p.6–10）。考试角度：C 级，识别操作、区分地址和值。

2. 时间、空间与随机运行时间

一句话：时间数执行次数；随机算法在固定输入上的执行次数也可能变化。

直觉：循环只写三行，运行一百轮就要付一百轮的费用。调用随机数后，同一输入也可能走不同分支，因此“运行时间”成为随机变量。

形式：运行时间是实际原子操作序列的长度。本讲空间特别定义为“访问到的最大内存地址”。若固定输入为 $I$ ，随机代价记为 $X_A(I)$ ，期望代价为 $E[X_A(I)]$ 。

算例：讲义 p.15 的过程为：

p.15 1. do 2. r = RANDOM(0, 1) 3. until r = 1

How many times would Line 2 be executed?

每次独立抽样成功概率为 $1/2$ 。令抽样次数为 $N$ ，第一次必抽，失败才重来：

E[N]=1+\frac12E[N],\qquad E[N]=2.

这是期望抽样次数，不是整段程序恰好两步。另一个补充示意：只访问地址 2、5、100，本讲空间是 100，不是 3。

联系与误区：期望 2 次不代表最多 2 次；连续失败任意多次都有正概率，但永不成功的概率为零。固定输入的确定性代价为常数，其期望就是该常数。

出处：#L00A-03（L00A p.11–13）、#L00A-04（p.14–16）。考试角度：C 级，期望保证与单次执行上界的区别。

L00B：最坏、期望和随机化

3. 最坏时间与最坏期望的顺序

一句话：最坏期望先固定输入求随机平均，再在同规模输入中挑最大的平均值。

直觉：这里有两种变化：输入可以变化，算法内部抽样也可以变化。只有第二种变化用于求本课的随机期望。

形式： $I_n$ 表示全部规模为 $n$ 的合法输入。确定性算法的最坏代价与随机算法的最坏期望分别为：

\max_{I\in I_n}X_A(I),\qquad \max_{I\in I_n}E[X_A(I)].

不能自行假定输入均匀分布，再把所有输入的运行时间平均。

算例（补充示意，沿用伴读演示数字）：某输入的代价恒为 5，另一输入的代价以相同概率取 2 或 10。两个期望是 5 和 6，最坏期望是 6；所有可能执行中的最大代价是 10。这两个答案不矛盾。

联系与误区：最坏期望小，不等于每次运行都快。二分查找则有确定性的 $O(\log n)$ 最坏保证，但前提是输入已经排序；若先排序，必须另外计费。

出处：#L00B-01、#L00B-02（L00B p.3；二分查找见 p.4–6）。考试角度：C 级，说明期望针对谁、最大值针对谁。

4. 找零：先算成功概率，再算时间

一句话：每次独立成功概率为 $p$ ，重复直到成功的期望尝试次数是 $1/p$ 。

直觉：好位置占比越高，随机命中的等待时间越短。只要求找到任意一个零时，不需要把所有元素读完。

形式：数组长 $n$ ，含 $z\ge1$ 个零，每轮均匀、有放回地抽一个位置，则

p=\frac zn,\qquad E[N]=\frac1p=\frac nz.

其推导是 $E[N]=1+(1-p)E[N]$ 。每轮若花 $O(1)$ 时间，期望总时间为 $O(n/z)$ 。只有一个零时，最坏期望为 $O(n)$ ；恰好一半为零时，对每个合法输入均为 $O(1)$ 。

算例：L00B p.10 原问题与数组：

p.10 Problem “Find-a-Zero”: Let A be an array of n integers, among which half of them are 0. Design an algorithm to report an arbitrary position of A that contains a 0.

For example, suppose A = (9, 18, 0, 0, 15, 0, 33, 0). An algorithm can report 3, 4, 6, or 8.

这里 $n=8,z=4$ ，期望尝试 $8/4=2$ 次。某次执行仍可连续抽到非零位置而失败很多次。

联系与误区：确定性算法的探查顺序可被最坏输入针对，前 $n/2$ 个不同探查位置都可能非零，故确定性最坏需要 $\Omega(n)$ 次探查。随机化的优势是对每个固定输入都有常数期望，不是每次都比确定性快。所有元素全为零是一次成功的特例；无有限运行上界的说法需要存在非零位置。

出处：#L00B-03（L00B p.7–8）、#L00B-04（p.10–11）。考试角度：C 级，把“成功比例→期望次数→每次成本”写全。

5. 补充：渐近符号与增长比较

这一节是分析工具补充，不新增讲义记忆条目。往年 Quiz 1 Q1 考过 $O$ 、 $\Omega$ 、 $\Theta$ 的辨别（A 级）。

对最终非负的函数：

$f=O(g)$ ：存在常数 $c>0,n_0$ ，使所有 $n\ge n_0$ 满足 $f(n)\le cg(n)$ ，表示渐近上界。
$f=\Omega(g)$ ：存在常数 $c>0,n_0$ ，使所有 $n\ge n_0$ 满足 $f(n)\ge cg(n)$ ，表示渐近下界。
$f=\Theta(g)$ ：上下界同时成立，表示同阶。

常用比较办法是看 $f(n)/g(n)$ ：趋于 0 表示 $f$ 严格慢于 $g$ ；趋于有限正常数表示同阶；趋于无穷表示 $f$ 严格快于 $g$ 。极限不存在时不能硬用此法，要回到定义。

对固定常数 $a>0,\varepsilon>0$ ，有 $(\log n)^a=o(n^{\varepsilon})$ ；固定底数变化只改对数的常数倍。遇到指数里也有对数的表达式，先用同一底数改写或取对数，别把它当作固定次幂的对数。

易错点： $O$ 不表示“恰好同阶”，更不自动表示“最坏”；“最坏还是期望”来自你分析的代价变量。精确题目要求 tight bound 时，应给 $\Theta$ 并支持上下界。

L01：递归、重试与几何级数

6. 递归和汉诺塔

一句话：递归先把更小的同型问题当作已解决，再说明如何利用子问题输出解决当前问题。

直觉：设计时不必把所有调用展开，但证明时必须有基本情形、规模下降和归纳步骤，才能兑现“子问题正确”的假设。

形式：汉诺塔把 $n$ 个盘从 A 移到 B，以 C 为辅助柱：先搬 $n-1$ 个小盘 A→C，再搬最大盘 A→B，最后搬 $n-1$ 个小盘 C→B。所示算法的移动次数满足

M(1)=1,\qquad M(n)=2M(n-1)+1=2^n-1.

讲义用上界表述；此处等式描述上述固定递归过程实际执行的移动数。

算例（补充示意）： $n=2$ 时，小盘 A→C，大盘 A→B，小盘 C→B，共 3 步； $n=3$ 时 $2\cdot3+1=7$ 步。展开式为 $2^jM(n-j)+(2^j-1)$ ，取 $j=n-1$ 就得到 $2^n-1$ 。

联系与误区：短代码也能产生指数工作。二分查找只递归一半，快速排序要递归两侧；递归次数不同，递推式也不同。辅助柱和目标柱的角色要随调用参数改变。

出处：#L01-01（L01 p.4）、#L01-02（p.5–8；递归练习 p.9）。考试角度：C 级，写基本情形、合法步骤及递推。

7. 秩与保留答案的随机缩减

一句话：选择问题只找第 $k$ 小的值；丢掉一部分元素后，必须同时调整目标秩。

直觉：如果丢掉了所有较小元素，目标在剩余集合里的位置会向前移动。保留目标值和保留原来的 $k$ 不是同一回事。

形式：本讲输入是元素互异的集合。枢轴 $v$ 的秩 $r$ 是不大于 $v$ 的元素数。分成 $S_1=\{x:x\le v\}$ 和 $S_2=\{x:x>v\}$ ，于是：

条件	保留集合	新的目标秩
$k\le r$	$S_1$	$k$
$k>r$	$S_2$	$k-r$

只有目标侧规模不超过 $2n/3$ 才接受，否则从当前原问题重新尝试。讲义分析暂设 $n$ 是 3 的倍数；当 $n/3\le r\le2n/3$ 时两侧均足够小，因此单次成功概率至少 $1/3$ ，期望尝试至多 3 次。一次扫描分区花 $O(n)$ ，所以成功缩减一次的期望成本是 $O(n)$ 。

算例：讲义 p.11 的题面：

p.11 The k-Selection Problem: You are given a set S of n integers in an array and an integer $k\in[1,n]$ . Find the k-th smallest integer of S.

For example, suppose that S = (53, 92, 85, 23, 35, 12, 68, 74) and k = 3. You should output 35.

取枢轴 53， $r=4$ ，保留 {53,23,35,12}， $k$ 仍为 3，大小 4 符合阈值。取枢轴 23， $r=2$ ，目标在右侧，新秩为 1，答案仍是 35；但右侧大小 6 大于 $16/3$ ，所以这一轮应拒绝。

联系与误区：失败表示“缩得不够小”，不是答案错误。中间三分之一是保证成功的充分条件，不代表只有这些秩能成功；因此结论是“概率至少”，不是“恰好”。允许重复值时需另行处理等于枢轴的整组元素，不能直接套互异集合的秩概率。

出处：#L01-03（L01 p.11–12）、#L01-04（p.13–15）。考试角度：A 级，Quiz-01-2025T1 Q2 考过改变缩减阈值后的成功概率分析；本次只总结方法，题目演练见原伴读。

8. 为什么选择的总期望是线性

一句话：虽然递归不止一层，但各层越来越便宜，总工作构成收敛的几何级数。

直觉：不能把每一层都按原来的 $n$ 收费。并且选择只追目标所在的一侧，不是两侧都递归。

形式：固定 $0<c<1$ 时，

n+cn+c^2n+\cdots=\frac{n}{1-c}.

在选择算法中，每次成功后规模至多为原来的 $2/3$ ，每层期望工作至多与当前规模成正比，故忽略取整、将小规模直接求解后，

E[T(n)]\le an+a\frac{2n}{3}+a\left(\frac23\right)^2n+\cdots =3an=O(n).

其中 $a$ 已包含本层重试的常数期望开销，不可把重试次数漏算。形式化地，可对每层实际输入条件化求期望，再利用该层规模上界相加。

算例（补充示意）：初始规模 27，规模上界依次为 27、18、12、8；前四项合计 65，无限几何和为 81。层数可以是对数量级，总代价仍是线性。

联系与误区： $O(\log n)$ 层乘以根节点的 $O(n)$ 是松上界，丢失了几何衰减，不能据此否定更紧的线性结论。该保证仍是期望时间；固定缩减比例也很重要，比例若随 $n$ 趋近 1，要重新分析。

出处：#L01-05（L01 p.17）、#L01-06（p.19–20）。考试角度：A 级，Quiz-01-2025T1 Q2(b) 考过缩减因子改变后总期望是否改变阶数。

L02：分治——分开以后还欠什么工作

9. 归并排序与递归树

一句话：两半分别排好，再线性合并；每层总成本线性，共有对数层。

直觉：两条有序序列的最小剩余元素一定在两个表头之一，所以每次只比较表头，无须重新搜索。

形式：设 $n=2^h$ 方便分析，

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

第 $j$ 层有 $2^j$ 个大小为 $n/2^j$ 的子问题，层工作量为 $\Theta(n)$ ； $h=\log_2n$ ，总时间 $\Theta(n\log n)$ ，因此满足讲义的 $O(n\log n)$ 上界。

算例（补充示意）：合并 [2,7] 与 [3,5]，依次输出 2、3、5，再追加 7。每个元素输出一次。 $n=8$ 的三层合并工作规模合计分别为 8、8、8。

联系与误区：当前节点花 $O(n)$ 不意味着整个算法只花 $O(n)$ ；两个递归调用都要计。正确性用归纳：两半已排序，合并每步选全体剩余元素中的最小者，最终不漏不重地产生有序数组。

出处：#L02-01（L02 p.5–6）。考试角度：C 级，能解释“节点数×单节点成本”，而非只背答案。

10. 逆序对：课堂版是双对数

一句话：按原位置分半，答案等于左内部、右内部、跨两半三部分之和。

直觉：每个数对只属于三类中的一类，所以拆分既不会漏掉，也不会重复。跨半区的左下标天然小于右下标，只剩数值大小要判断。

形式：逆序对满足 $i<j$ 且 $A[i]>A[j]$ 。最多有 $n(n-1)/2$ 个，由严格降序数组达到。课堂合并方法：排序左半副本，对右半每个值 $e$ 二分查询左半大于 $e$ 的元素数。因此当前节点成本为 $O(n\log n)$ ，递推为

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

设 $h=\log_2n$ ，第 $j$ 层成本上界为 $an(h-j)$ ，于是

\sum_{j=0}^{h-1}an(h-j)=an\frac{h(h+1)}2=O(n\log^2n).

算例：L02 p.8 的原定义及数据：

p.8 An inversion is a pair of (i, j) such that $1\le i<j\le n$ , and $A[i]>A[j]$ .

Example: Consider A = (10, 3, 9, 8, 2, 5, 4, 1, 7, 6).

左半内部为 8，右半内部为 4。左半排序副本 [2,3,8,9,10]，对右半 5、4、1、7、6，分别计得跨逆序 3、3、5、3、3，共 17；总数 $8+4+17=29$ 。

联系与误区：不能先把整个原数组排序再数；那会抹掉原位置关系。相等不构成逆序，所以应查“严格大于”。T03 的改进版可以做到 $O(n\log n)$ ，但这不是 L02 课堂算法的合并成本；答题先认清指定的是哪一版。

出处：#L02-02（L02 p.8）、#L02-03（p.10–12）。考试角度：A 级，Quiz-01-2025T1 Q3 考过两半输出、跨逆序数量及改变合并成本后的递推分析。

11. 二维支配：先满足一个坐标条件

一句话：按横坐标分成左右后，只有右点可能支配左点，跨组计数只需比较纵坐标。

直觉：二维条件是“横坐标不小且纵坐标不小”。分组已自动保证跨组的横坐标顺序，剩下一维可以排序后做二分查询。

形式：不同点 $p,q$ 中， $q$ 支配 $p$ 当且仅当 $p[1]\le q[1]$ 且 $p[2]\le q[2]$ 。讲义输入的横坐标互异。按横坐标均分得到左组 $P_1$ 、右组 $P_2$ ，递归得到各组内部计数；将左组纵坐标排序，对每个右点 $q$ 加上左组中纵坐标不大于 $q[2]$ 的点数。左组结果不变。

当前节点排序与查询耗时 $O(n\log n)$ ，所以同样得到 $O(n\log^2n)$ 总时间。

算例：L02 p.15 的任务是：

p.15 Let P be a set of n points in $\mathbb Z^2$ with distinct x-coordinates. Find, for each point $p\in P$ , the number of points in P that are dominated by p.

沿用 p.15、p.19–21 原图的点名，左右组分别为 $p_1$ 至 $p_4$ 、 $p_5$ 至 $p_8$ 。右组内部计数是 0、1、0、0，来自左组的补充计数是 2、4、2、0，故右组最终为 2、5、2、0。左组为 0、1、0、2，整体为 0、1、0、2、2、5、2、0。

联系与误区：数的是“这个点支配多少别的点”，不是“有多少点支配它”；不计自己；纵坐标允许相等，查询是“≤”，不同于逆序对的“>”。只返回跨组计数会漏掉组内贡献。

出处：#L02-04（L02 p.14–15）、#L02-05（p.17–22）。考试角度：C 级，说明为什么跨组只补右侧，以及二分查询的比较方向。

12. Strassen：少一次子乘法改变指数

一句话：把八次半阶矩阵乘法改为七次，额外付出平方级加减成本，总指数便低于 3。

直觉：省下的不只是最外层的一次乘法，而是每层每个节点的一次递归子调用；这种节省会在整棵递归树上累积。

形式：将两个矩阵写成四个块，左矩阵为 $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ ，右矩阵为 $\begin{pmatrix}e&f\\g&h\end{pmatrix}$ 。讲义 p.25 的七个积为：

\begin{aligned} p_1&=a(f-h),&p_2&=(a+b)h,\\ p_3&=(c+d)e,&p_4&=d(g-e),\\ p_5&=(a+d)(e+h),&p_6&=(b-d)(g+h),\\ p_7&=(a-c)(e+f). \end{aligned}

恢复结果：

AB=\begin{pmatrix} p_5+p_4-p_2+p_6&p_1+p_2\\ p_3+p_4&p_1+p_5-p_3-p_7 \end{pmatrix}.

块加减要逐元素进行，成本 $O(n^2)$ ，所以

T(n)\le7T(n/2)+O(n^2)=O(n^{\log_2 7}),\qquad \log_2 7\approx2.807.

第 $j$ 层的加减成本是 $O(n^2(7/4)^j)$ ，逐层增加，底层主导；叶子数 $7^{\log_2 n}=n^{\log_2 7}$ 。

算例（补充示意，沿用伴读数字）： $a,b,c,d=1,2,3,4$ ， $e,f,g,h=5,6,7,8$ 。七个积为 $-2,24,35,8,65,-30,-22$ ，恢复得到 $\begin{pmatrix}19&22\\43&50\end{pmatrix}$ 。例如右上格 $p_1+p_2=-2+24=22=1\cdot6+2\cdot8$ 。

联系与误区：分块后，块加法不是 $O(1)$ ；矩阵乘法不可交换次序，展开验证时必须保持因子顺序。少递归调用不代表所有小规模实例实际都更快；渐近结论忽略了常数。

出处：#L02-06（L02 p.25–28；存储与普通乘法见 p.24）。考试角度：C 级，写出 7、 $n/2$ 、 $n^2$ 分别来自哪里，推导指数。

13. 补充：递推分析的固定写法

先写“子问题个数、每个规模、当前节点额外工作”，再展开。对 $T(n)=aT(n/b)+f(n)$ ，第 $j$ 层成本为 $a^jf(n/b^j)$ ，深度约 $\log_b n$ ；最后还要计入叶子。

本次范围中的结构	层成本特征	得到的时间保证
二分： $T(n)=T(n/2)+O(1)$	每层常数	$O(\log n)$ 最坏
归并： $T(n)=2T(n/2)+O(n)$	每层 $O(n)$	$O(n\log n)$ 最坏
课堂逆序/支配： $T(n)=2T(n/2)+O(n\log n)$	第 $j$ 层 $O(n(\log n-j))$	$O(n\log^2n)$ 最坏
随机选择：期望层成本与 $n,(2/3)n,\ldots$ 成正比	几何递减	$O(n)$ 期望
Strassen： $T(n)=7T(n/2)+O(n^2)$	按 $7/4$ 几何递增	$O(n^{\log_2 7})$ 最坏

这是分析结构的归纳，不是新的课件条目。若题目把合并成本改掉，必须重新代入逐层求和，不能保留原答案。

L03：Greedy 1——活动选择

14. 每次选最早结束的兼容活动

一句话：最大化互不相交活动的个数时，按结束时间从早到晚选。

直觉：当前活动越早结束，留给之后活动的时间越多；这个直觉需要下一节的交换论证来保证全局最优。

形式：本讲用闭区间 $[s,f]$ ，兼容要求后一个活动的开始时刻严格大于前一个的结束时刻。先按 finish 非降序排序，再扫描：

last_finish = 负无穷
answer = 空集合
for [s,f] in 按 finish 排序后的活动:
    if s > last_finish:
        将 [s,f] 加入 answer
        last_finish = f
return answer

排序 $O(n\log n)$ ，扫描 $O(n)$ ，总计 $O(n\log n)$ ；若已按 finish 排序，扫描部分为 $O(n)$ 。

算例：讲义任务与原例：

p.3 Input: A set S of n intervals of the form [s, f] where s and f are integers. Output: A subset T of disjoint intervals in S with the largest size $\lvert T\rvert$ .

p.4 Example: Suppose $S=\{[1,9],[3,7],[6,20],[12,19],[15,17],[18,22],[21,24]\}$ .

依次选 [3,7]、[15,17]、[18,22]，共 3 个。[1,9] 与第一项相交；[12,19] 与第二项相交；[21,24] 与第三项相交。

联系与误区：优化目标是活动数，不是总时长或收益。不要误选最早开始或持续时间最短。闭区间 [1,3] 与 [3,5] 相交，因此这里不能把条件写成 s >= last_finish；其他课程若用半开区间，条件才可能不同。

出处：#L03-01（L03 p.3–6；实现 p.11）。考试角度：C 级，手工执行及说明排序键、端点条件。

15. 交换论证：最优解可以迁就贪心

一句话：证明存在一个最优解包含当前贪心选择，然后对剩余问题重复。

直觉：无需证明所有最优解都与贪心完全一致；只要能把某个最优解改造成包含它、又不损失解的大小即可。

形式：第一次选择 $I$ 为结束最早的活动。取最优解 $O$ ，令 $J$ 为其中结束最早的活动。如果 $I$ 不在 $O$ 中，就以 $I$ 替换 $J$ 。对 $O$ 中其余活动 $K$ ，

f(I)\le f(J)<s(K).

所以替换后仍可行，活动数不变，仍是最优解。

推广时保持不变量：存在某个最优解，包含当前整个贪心前缀。 剩余最优活动都在前缀之后；若能插在某两次贪心选择之间，它当时也应是候选且更早结束，与贪心选择矛盾。然后在剩余部分交换最早结束的活动，保持前缀、可行性和数量。终止时没有候选可加，包含该前缀的最优解也不能再有额外活动，故当前解最优。

算例：仍用上一节原例，另一个最优解是 {[1,9],[12,19],[21,24]}。先将 [1,9] 换成 [3,7]，再将 [12,19] 换成 [15,17]，最后将 [21,24] 换成 [18,22]。每次保留此前选择，数量都为 3。

联系与误区：“给后面留下更多时间”只是直觉；完整证明必须说清楚换掉谁、为什么不冲突、为什么数量不变，以及如何重复到结束。

出处：#L03-02（L03 p.7–10）、#L03-03（p.9–10）。考试角度：C 级，写完整交换证明；既有伴读另含往年反向活动选择的演练，按需回看。

L04：Greedy 2——最小生成树与 Prim

16. 生成树与最小生成树

一句话：生成树覆盖全部顶点且连通无环；MST 在所有生成树中让边权总和最小。

直觉：连接所有点需要足够的边，但环上的边提供冗余连接。找一批便宜边并不够，还必须形成合法生成树。

形式：本讲输入是连通无向带权图 $G=(V,E)$ 。设顶点数为 $N$ ，边数为 $M$ 。生成树具有全部 $N$ 个顶点、 $N-1$ 条边，连通且无环；成本为所选边权之和。树上任意两点之间有唯一简单路径，加一条非树边会形成唯一环，从环中删一条边可恢复树。

算例：L04 p.3 的原图有八点，边为 ab:1, ef:2, ac:3, bc:3, cf:5, ch:6, af:7, ah:8, gh:9, be:10, gd:11, ed:12, bg:13。p.5 的一棵树取 ab,bc,cf,ef,ch,gh,gd，成本 $1+3+5+2+6+9+11=37$ 。把 bc 换成同权的 ac，成本仍为 37；p.7 指出这两棵都是 MST。

联系与误区：只验证有 $N-1$ 条边不够，仍可能不连通并在某处有环。MST 不一定唯一；它最小化所有树边总和，不是在指定源点到各点的路径上分别求最短。

出处：#L04-01（L04 p.4–6；非唯一性 p.7）。考试角度：C 级，判断生成树、计算总权重、区分不同优化目标。

17. Prim 每轮选的是最轻跨边

一句话：维护已加入顶点集 $S$ ，每次选一端在 $S$ 、另一端不在 $S$ 的最轻边。

直觉：跨边正好把一个新顶点接到当前树上，保持连通，而且不会在已有顶点之间加出环。

形式：讲义从全图最轻边初始化，之后逐轮扩张。常见的任取一个起点再扩张也是 Prim 的标准写法，但手算本讲实例时沿用课件初始化。候选只包括跨边：两端都在内部或都在外部的边均不合资格。

算例：沿用上一节的 L04 p.3 原图，p.9–15 的执行为：

步骤	加入的边	新加入的点	累计成本
初始化	ab，权 1	a、b	1
2	ac，权 3	c	4
3	cf，权 5	f	9
4	ef，权 2	e	11
5	ch，权 6	h	17
6	gh，权 9	g	26
7	gd，权 11	d	37

已有 {a,b,c} 时，bc:3 两端都在内部，不能选；ef:2 两端都在外部，也不能选。直到 f 加入，ef:2 才成为跨边。

联系与误区：所选权重序列可以从 5 降到 2，所以 Prim 不是按全图边权递增选边；相同最轻跨边可任选，最终树可能不同。每轮加入一个新点，最终应有 $N-1$ 条树边。

出处：#L04-02（L04 p.8–15）。考试角度：C 级，列每轮 $S$ 、候选跨边、选择与累计成本。

18. Prim 正确性：加边成环，再删另一跨边

一句话：每个已选边前缀都能保留在某棵 MST 中，所以不断选择不会把所有最优解排除掉。

直觉：如果一棵 MST 没有本轮贪心边，就把它加进去，再用一条不更轻的边抵掉。这次交换还必须保护以前选过的边。

形式：令已选边集为 $F$ ，已加入顶点集为 $S$ ，保持不变量“存在一棵 MST $T$ 包含 $F$ ”。本轮选最轻跨边 $e$ 。

若 $e$ 已在 $T$ 中，则 $T$ 本身包含新前缀。
否则将 $e$ 加入 $T$ ，形成唯一环。
因 $e$ 跨越 $S$ 与外部，沿环绕回去必定存在另一条跨边 $e'$ 。
$e'$ 不属于 $F$ ，因为 $F$ 的两端都在 $S$ 内；删除它不会破坏已有选择。
由于 $e$ 是最轻跨边， $w(e)\le w(e')$ 。令 $T'=T+e-e'$ ，得到连通无环的生成树，且

w(T')=w(T)+w(e)-w(e')\le w(T).

由于 $T$ 已最优， $T'$ 也最优，并包含 $F\cup\{e\}$ ，完成归纳。初始化的全图最轻边也可用“加边成环、删另一边、成本不增”证明安全。最后选满 $N-1$ 条边，前缀本身就是那棵 MST。

算例：原图中，某棵 MST 使用 ab、bc 而不是 ac。Prim 已选 ab，本轮选择 ac。加入后形成 a–b–c–a 环，删除同权的 bc 即可；保留旧边 ab，总成本不变。

联系与误区：不能随便删环上一条边——可能删掉此前贪心选择，或删掉比新边更轻的边。“存在一棵 MST 包含前缀”也不能偷换为“每棵 MST 都包含前缀”。

出处：#L04-03（L04 p.16–21）。考试角度：C 级，完整说明环上为何有另一跨边、为何保护前缀、为何成本不增。

19. Prim 的实现与复杂度

L04 p.22 提出的目标是 $O((N+M)\log N)$ 。以下是该实现问题的解释，详细过程见 T04 伴读。

给每个外部顶点 v 维护 key[v]：它连接当前 $S$ 的最轻边权，并保存对应父顶点。最小堆按 key 排序，取 key 最小者加入，再扫描其邻边以更新外部顶点。

选起点 r
所有 key = 无穷，parent = 空
key[r] = 0
将全部顶点放入支持 decrease-key 的最小堆 Q
while Q 非空:
    u = extract-min(Q)
    若 parent[u] 非空，输出边 {parent[u],u}
    for u 的每个邻点 v:
        if v 仍在 Q 且 w(u,v) < key[v]:
            key[v] = w(u,v)
            parent[v] = u
            decrease-key(Q,v)

这是从单点初始化的标准实现。连通图中最终覆盖全部顶点。邻接表配合带位置索引、支持 decrease-key 的二叉堆： $N$ 次取最小，至多 $O(M)$ 次更新，单次堆操作 $O(\log N)$ ，总时间 $O((N+M)\log N)$ 。若每轮线性扫描所有顶点找最小 key，可得到 $O(N^2+M)$ ，简单图中常写 $O(N^2)$ 。复杂度取决于实现，不是 Prim 名字自带的固定数值。

考试角度：C 级，解释 key 的含义与操作计数；不要把它误写成从起点到 v 的整条路径长度。

把同一输入拿来做三个不同问题。 补充数组 [3,1,2]：选择第 2 小返回 2；排序返回 [1,2,3]；逆序计数返回 2，对应原下标 (1,2),(1,3)。它们可能共享分区或排序步骤，但输出契约不同，不能用“反正最后都排序”替代各自的时间分析。

基础自测：对这个数组先整体排序再数逆序，会得到什么？为什么错？

会得到 0。原位置关系已经被改变，原题的两个下标对不再可见；正确分治只对各半的副本排序，并保留半区归属。

进阶自测：选择只有一支递归，是否就必定线性？

不一定。若每次只去掉一个元素，本层扫描成本依次为 $n,n-1,\ldots,1$ ，总和 $n(n+1)/2=\Theta(n^2)$ 。线性期望需要正文中的固定比例缩减，以及获得这次缩减所需重试成本的期望界。

证明复习也可以先改一个条件再找断点：活动按收益最大化时，“替换后数量不变”不再保证收益不降；Prim 若选两端已在 S 内的边，连通性没有扩展还可能造环。先说具体失效步骤，比只说“贪心有时会错”更能检验理解。

考前最后过一遍

复习时间有限时，先确认下列动作能独立完成，再回看对应小节补洞。这是掌握标准，不是额外小测。

解释最坏期望中的“先期望、后最坏”，不把输入随机化。
从单次成功概率算出重试次数，再乘单次操作成本。
随机选择时正确更新 $k$ ，解释拒绝条件与几何求和。
为分治写出三个量：调用个数、子问题规模、合并成本。
逆序对保留原位置分组，分清内部贡献与跨组贡献。
二维支配写对“谁支配谁”和纵坐标的非严格比较。
从七个子乘法及平方加减成本推导 Strassen 指数。
活动选择按最早结束排序，记住闭区间的严格兼容条件。
写交换论证时同时证明可行性、目标值不变或不变差、旧选择保留。
Prim 只选跨边，能用“加边成环→删另一跨边”完成归纳。

证明题可按这个顺序写：定义当前状态 → 写不变量 → 取一个最优解 → 构造交换 → 检查可行性 → 比较目标值 → 说明保留旧选择 → 终止时推出最优。 两种贪心都适用，但交换对象和可行性理由必须分别展开。

完整性对账

原整理范围内知识清单共有 26 条，已全部进入正文；范围外条目不纳入分母。此表记录这份复习摘要的覆盖范围。

讲次	条数	已覆盖编号
L00A	4	#L00A-01、#L00A-02、#L00A-03、#L00A-04
L00B	4	#L00B-01、#L00B-02、#L00B-03、#L00B-04
L01	6	#L01-01、#L01-02、#L01-03、#L01-04、#L01-05、#L01-06
L02	6	#L02-01、#L02-02、#L02-03、#L02-04、#L02-05、#L02-06
L03	3	#L03-01、#L03-02、#L03-03
L04	3	#L04-01、#L04-02、#L04-03

来源与证据

本笔记以下列既有伴读为主；没有重新阅读全文课件 PDF，课件页码沿用已有来源定位。它是一份范围内总结，不是逐页替代讲义。

2026-09-30 整理时另外读取 Quiz-01-2025T1-题解.pdf（本地课件）的全部文本，核对 Q1–Q3 的考查内容；没有把往年题题目扩充为本次额外范围，也没有把既有伴读里的历史全量核验声明当作本次新核验。其他试卷本次未重读。本笔记没有展开往年题解答；需要演练时可进入相应伴读附录。

原整理的考试证据记录（2026-09-30）：读了 Quiz-01-2025T1-题解.pdf；未识别用途的 PDF：无