COMP3121 Week02 学习笔记

01 · 本周地图：从“算法想法”到“可信的论证”

这个部分回答什么问题：第二周究竟新增了什么，应该带着什么目标读？本周重点是把算法说清楚后，证明它对所有合法输入都成立，并兑现声称的运行时间。学习顺序：写清命题 → 选择证明工具 → 找到关键性质 → 推出终态 → 单独核算成本。

← 回到第一周学习笔记 · 先学证明框架，再读树直径与稳定匹配的详细论证。

02 · 衔接：递归与归约也要付成本

这个部分回答什么问题：已经会解决一个子问题，为什么还不能直接宣称新问题高效？归约要付转换输入、调用子程序以及处理结果的成本；递归则把大实例变成更小的同类实例，直到基本情况。

Palindrome(s, l, r):
if l >= r: return true          // 空串或单字符：基本情况
if s[l] != s[r]: return false   // 首尾不等：不可能是回文
return Palindrome(s, l + 1, r - 1)

执行流程：以0起始下标调用 Palindrome(s,0,n−1) → 检查基本情况 → 比较首尾 → 递归到内部区间 → 把真假结果原样传回。n是字符数；l、r是当前左右下标。例子 abba：比较a/a，再比较b/b，进入l>r的空区间并返回真。abc在首尾a/c处即返回假。

正确性是等价关系：一个长度至少2的串是回文，当且仅当首尾相同且内部是回文。规模每次减2，因此会到长度0或1。使用下标时每层O(1)，总O(n)；若每层复制内部子串，最坏复制量是(n−2)+(n−4)+…，可达O(n²)。这是实现成本补充，不能只数比较次数。

03 · 先把证明目标写成一句精确的话

这个部分回答什么问题：证明“算法正确”和证明“算法错误”分别需要什么证据？对所有合法输入的声明是全称命题；一个合法反例足以推翻它，而任意有限个通过的测试通常不能证明它。

量词取反：¬(∀x P(x)) ⇔ ∃x ¬P(x)；¬(∃x P(x)) ⇔ ∀x ¬P(x)。x表示待考虑的输入，P(x)表示所声称的性质。例子：宣称“每个长度3数组都被算法排好序”；若输入[3,1,2]输出[1,3,2]，这一个x就足以推翻全称声明。

1. 写明合法输入与假设：例如无向、无权、连通的树。
2. 写明输出要求：例如返回直径长度，而非任意长路径。
3. 把正确性拆成需要的引理：先得到合法对象，再证明完整性或最优性。
4. 把效率单独分析：重复次数、每次成本、初始化与输出成本。

04 · 直接证明：把操作成本逐项结清

这个部分回答什么问题：什么时候沿着已知事实向前推就够了？如果每个操作的次数与成本已知，直接证明（Direct proof）通常最清楚。课件用堆排序说明成本核算。

1. 把n个元素放进min-heap。可以线性建堆；若逐一插入，O(n log n)也足以得到本例总体上界。
2. 重复n次：访问堆顶的最小元素，删除它，再追加到输出。堆顶读取、追加为O(1)，删除需要最坏O(log n)来恢复堆性质。
3. 合计O(n+n·log n)=O(n log n)。这里n是元素数，log的固定底数不改变渐近界。

05 · 反证法：把“算法失败”变成可操作的假设

这个部分回答什么问题：两次BFS为何就能求树的直径？这不是“走得远看起来就对”，关键是证明第一次找到的最远点v必为某条直径的端点。以下展开课件与课堂的最低公共祖先论证；不等式是为填补课堂口头略写而补出的细节。

1. 目标是：对每棵合法树、每个起点u、每个可选的最远点v，算法输出D。
2. 若v是某条直径的端点，则第二次BFS取到最大d(v,w)，必等于D。因此核心引理是“存在以v为端点的直径”。
3. 反设v不是任何直径的端点。取一条直径x→y，则d(x,y)严格大于从v出发的任意路径，特别大于d(v,x)与d(v,y)。这是要推翻的具体不等式。

将树以u为根。令h(z)=d(u,z)为顶点z的深度，L为x、y、v三者的最低公共祖先（LCA）。v是最远点，所以h(v)≥h(x)、h(v)≥h(y)。至少有一条v→x或v→y经过L：若二者都避开L，三点就全在L的同一个孩子子树中，与L“最低”矛盾。

不妨设v→x经过L。树上路径长度公式为d(a,b)=h(a)+h(b)−2h(LCA(a,b))：两条从根走下来的路，公共前缀被重复计数，必须减两次。于是d(v,x)=h(v)+h(x)−2h(L)。而x、y的LCA不会高于L，因此d(x,y)≤h(x)+h(y)−2h(L)≤h(x)+h(v)−2h(L)=d(v,x)。这与假设d(x,y)>d(v,x)矛盾。若经过L的是v→y，则对称地比较d(x,y)与d(v,y)。

06 · 循环不变式：到底什么始终没变？

这个部分回答什么问题：数组不断变化，为什么还能说某个性质“不变”？Loop invariant是不随迭代失效的逻辑性质，不是数组值不改变。明确性质在“每轮开始”还是“每轮结束”成立，才能对齐下标。

07 · 单调量：不只是下降，还必须不能无限下降

这个部分回答什么问题：如何证明一个过程不可能永远执行？Monovariant选一个有界的整数进度量，每个计入的步骤严格推进。对非负整数Q，若每步Q至少减少1，则从Q₀开始至多执行Q₀步。只说非负实数递减不够，例如1,1/2,1/4,…可以永远降下去。

冒泡排序取逆序对数I(A)=|{(i,j):1≤i<j≤n 且 A[i]>A[j]}|。A是数组，n是长度；I统计位置对而非元素个数。因为最多有n(n−1)/2个位置对，所以0≤I≤n(n−1)/2。相等元素不是逆序对。

08 · 归纳法：允许相信的“小问题”有多大？

这个部分回答什么问题：归纳假设是不是在偷用待证结论？不是。只能假设更小规模的同一个命题；必须证明最小规模，并证明更小规模如何推出当前规模。不要只背n=1、n=k、n=k+1的格式。

1. 基本情况：n=1，一个元素已经有序，未丢失元素。
2. 归纳假设：任意长度k的数组均能被正确排序。
3. 归纳步：取任意长度k+1的A，把全局最小值交换到A[1]，所以A[1]≤其余每个值；剩余A[2..k+1]长度恰为k，应用归纳假设得到有序后缀。
4. 最小值在前 + 后缀有序，得到整个数组有序；交换与后缀排序保留全部元素。由归纳法覆盖所有正整数长度。

09 · 归并排序：两个证明层次，不能跳过中间一步

这个部分回答什么问题：两个递归调用加一个merge，怎样组合成完整证明？先证明“两个已排序数组能被正确合并”这个局部引理，再用强归纳证明每个递归调用确实产生已排序数组。

课件采用闭区间A[ℓ..r]、中点m=⌊(ℓ+r)/2⌋。ℓ、r是左右下标，m属于左半段。例ℓ=1、r=6时m=3，得到[1..3]与[4..6]，长度3+3=6，没有遗漏或重叠。当前元素数N=r−ℓ+1。下方自学伪代码也使用闭区间。

MergeSort(A, l, r):
if l >= r: return                 // 基本情况：至多一个元素
m = floor((l + r) / 2)
MergeSort(A, l, m)                 // 递归排序左半段
MergeSort(A, m + 1, r)             // 递归排序右半段
Merge(A, l, m, r)

Merge(A, l, m, r):
B = empty array
i = l; j = m + 1                   // 各段最小的未取元素
while i <= m and j <= r:
if A[i] <= A[j]:
append A[i] to B; i = i + 1
else:
append A[j] to B; j = j + 1
while i <= m:
append A[i] to B; i = i + 1
while j <= r:
append A[j] to B; j = j + 1
overwrite A[l..r] with B

执行流程：外层MergeSort先分区 → 左右递归各自返回 → Merge比较两段首个未取值 → 较小者进入B，对应指针前移 → 一段耗尽后补入另一段剩余值 → 将B写回原区间。辅助数组占线性额外空间；教授明确说本例无需为原地合并增加复杂度。

1. 初始化：B为空，包含最小的0个元素，命题成立。
2. 保持：因为两段内部已有序，每段的所有未取元素都不小于本段头部。两段头部的较小值因此是全体剩余元素的最小值。取它恰好扩展一个元素，并保持B有序。
3. 一段耗尽：另一段本就有序，且其余值均不小于B末尾，按原顺序追加不会破坏性质。
4. 终止：所有元素恰好进入B一次，因此B就是整个输入区间的有序重排；写回不改变这个结论。

全局强归纳：基本情况N≤1成立；假设所有更小规模都能被MergeSort正确排序。对N≥2，两半都非空且严格小于N，归纳假设给出“左右各自有序”；随后使用已证明的merge引理得到整个区间有序。子问题规模不断缩小也保证递归终止。

10 · 归并的成本：每层总量，而非每个结点都算n

这个部分回答什么问题：递归调用很多，为何总时间只有O(n log n)？关键是按同一层所有子问题的总规模计费。n是原数组长度；某个merge处理的N可能远小于n。

单次merge的N=r−ℓ+1个元素各复制进B一次，再各写回A一次，都是常数成本，因此总O(N)；双段比较至多N−1次。例两段长度3和2，N=5，最多4次头部比较，随后补齐余项，并写回5项。比较次数不是所有指令的总数。

当n为2的幂时，第j层有2ʲ个长度n/2ʲ的子问题，总合并量2ʲ·(n/2ʲ)=n；有log₂n个合并层，所以T(n)=O(n log n)。j从0开始，代表层号。例n=8有3层，合并长度之和8+8+8=24；实际时间还乘上复制、比较的常数。一般n使用向上/向下取整，层高至多⌈log₂n⌉，每层总量仍O(n)。

11 · 稳定匹配：到底要让谁满意？

这个部分回答什么问题：双方都提交偏好，却不可能人人拿到第一选择，应该保证什么？输入是n个开发者、n个客户；每个人严格排列对方全部n人，无并列、无缺项。目标是完美匹配且没有双方都想私下改配的阻塞对。

记M(d)为d的现客户、M(c)为c的现开发者，c ≻d M(d)表示d更喜欢c。阻塞条件是[c ≻d M(d)] ∧ [d ≻c M(c)]。例David想换Cynthia，但Cynthia更喜欢现搭档Daphne，则第二条件不成立，不构成阻塞。

不考虑偏好，共有n!=n·(n−1)·…·1种完美匹配：依次给每个客户分配未使用的开发者。例n=4是24种，n=10是3,628,800种。枚举全部匹配再检查稳定性会很慢。课件写n!≈(n/e)ⁿ是展示主增长尺度的简写，e≈2.718；精确比值趋近1的Stirling近似应为n!≈√(2πn)(n/e)ⁿ（背景补充），n=4时约23.5接近24，而省略平方根的式子约4.69，不能拿来准确计算数量。

12 · Gale–Shapley：先理解状态如何变化

这个部分回答什么问题：为什么客户可以先接受、再换人？这里的接受是暂时的。开发者按照自己的偏好从高到低提案；客户始终保留到目前为止自己最喜欢的提案者，其他人继续尝试下一位。

1. 初始化：所有开发者和客户都未配对，每个开发者记录下一位尚未提案的客户。
2. 选择任一尚未配对、且还有客户未提案的开发者d。让d向名单上最喜欢的未尝试客户c提案，之后永不重复这一对提案。
3. 若c没有搭档，暂时接受d。
4. 若c已有搭档d′，比较偏好：更喜欢d就换成d，d′重新空闲；否则拒绝d。
5. 重复，直到没有符合条件的开发者。随后仍需证明：这个停止条件确实意味着人人有配对。

13 · 稳定匹配：三个命题与O(1)一轮的实现

这个部分回答什么问题：算法停止后为何一定得到稳定的完美匹配，以及n²轮为何真能变成O(n²)时间？

证明依赖链：不重复提案 → 会终止；客户一旦配对不再空闲 + 停止条件 → 完美匹配；开发者按序提案 + 客户搭档只改善 → 无阻塞对。不要从算法描述直接跳到“显然完美且稳定”。

例如客户c偏好[d₂,d₀,d₁]，预处理为rank[c][d₂]=0、rank[c][d₀]=1、rank[c][d₁]=2。已有d₀时收到d₂，比较0<1就替换，无需扫描整张名单。输入共有2n张长度n的偏好表，即2n²项；n=3时18项。预处理O(n²)+最多n²轮×每轮O(1)=O(n²)，包括偏好表的空间O(n²)。若每轮扫描偏好表或扫描全部开发者找空闲者，可能把实现上界拖到O(n³)。

14 · 本周通用解题方法：看到什么信号，用什么骨架

这个部分回答什么问题：下次遇到陌生题，如何选择证明路线？先把算法的输入、状态、每步动作、结束条件、目标写清楚，再选择最贴近它结构的工具；同一道题完全可以组合多种方法。

15 · 自测：先写理由，再展开答案

这些自测按本周知识点编写，不是官方测验题。答案默认隐藏，文本只保留在当前页面；每道题可单独清空。

16 · 复习清单与术语表

• 我能把“总是正确”的否定写成一个存在性命题，并保留合法输入限制。
• 我能解释递归的规模为什么变小，并核算转换和调用次数。
• 我能写出树直径证明中的LCA与深度不等式，而不只说“v很远”。
• 我能区分不变式、单调量与归纳假设，并说清各自证明哪件事。
• 我能给merge写出强于“B有序”的不变式，区分局部引理与全局归纳。
• 我能按每层总规模解释O(n log n)，并处理非2次幂。
• 我能区分匹配、完美匹配、稳定匹配，并把Gale–Shapley的三个命题按依赖顺序说明。
• 我能解释rank表与空闲栈为什么使一轮O(1)。

17 · Greedy Lecture 地图：录音到底讲到哪

这个部分回答什么问题：整份154页 PDF 含有后续内容，这一段课堂录音对应哪些页？按话题顺序和独有例子交叉定位：从 Frozen Yoghurt I（实际 p4）进入贪心，讲到 Cell Towers 的 greedy stays ahead 指标讨论（对应实际 p36 主题）时，录音在一句未说完的话中结束。p1–3 是封面与目录；p36 正式命题是否已展示无法由录音确认；p37–38 是紧接着的完整证明，但没有出现在本份 transcript 中。

18 · 贪心选择为什么有时可行，有时会锁死后路

这个部分回答什么问题：局部看起来最划算，为什么未必能推出整体最优？Greedy algorithm 在每一步只保留眼前最好的一个方向，省去枚举，但必须证明被排除的选择不会在后续反超。登山例子说明局部最高峰未必是全局最高峰。

记第 i 件重量 wᵢ>0、价值 vᵢ，背包容量 W，xᵢ 是所取比例。分数版最大化 Σvᵢxᵢ，约束 Σwᵢxᵢ≤W 且 0≤xᵢ≤1。若某方案在仍可取高比值物品 i 时却取了低比值物品 j 的一小段重量 δ，把这 δ 重量从 j 移给 i，价值变化 δ(vᵢ/wᵢ−vⱼ/wⱼ)≥0。反复调整便得到按比值排序的方案；排序 O(n log n)，扫描 O(n)。这里 δ 是可转移重量，不是物品件数。 数值代入：若高比值为6、低比值为5，可移动δ=0.5 kg，则价值增加0.5×(6−5)=$0.5；δ不能大于低比值物品已取重量或高比值物品剩余容量。不要把δ当作0.5件物品的价值。

19 · 活动选择：认识目标，再击破错误准则

这个部分回答什么问题：如何选择最多个互不重叠活动？活动 i 的开始与结束时刻是 sᵢ、fᵢ。采用半开区间 [sᵢ,fᵢ)，这样前一个活动在 t 结束、后一个在 t 开始视为兼容。目标是最大化活动数量，而不是总时长。

算法：按 fᵢ 升序排序；lastFinish 初始为负无穷；顺序扫描，若 sᵢ≥lastFinish 就选取 i 并令 lastFinish=fᵢ。例 A=[0,5)、B=[4,6)、C=[5,10)：先选 A，跳过 B，选 C，得到2项。排序 O(n log n)，每项只检查一次是 O(n)，总 O(n log n)。n 是活动数。

20 · 活动选择的交换证明：每换一次都保住最优

这个部分回答什么问题：为什么“最早结束”不是一次碰巧有效？设贪心结果 G=(g₁,…,gᵣ)，任取一份合法方案 A=(a₁,…,aₛ)，均按结束时刻排序。若前 k−1 项相同而第 k 项不同，gₖ 是在共同前缀之后最早结束的可选活动，所以 f(gₖ)≤f(aₖ)。

1. 把 A 的第 k 项 aₖ 换成 gₖ，构成 A′=(g₁,…,gₖ,aₖ₊₁,…,aₛ)。
2. 合法性：gₖ 与共同前缀兼容；原方案中 aₖ 结束后才开始的后继也不会与更早结束的 gₖ 冲突。
3. 数量：只替换一项，没有减少活动；gₖ 不会与后继是同一活动，因为后继从 aₖ 结束之后才开始。
4. 反复替换，分歧位置严格往后移，且始终保留一份与原方案同样多项的合法方案。若贪心先耗尽而替换方案仍有下一项，那么这项与贪心全部前缀兼容，贪心本应继续选择，矛盾。

21 · 基站覆盖：算法、边界与课堂的领先指标

这个部分回答什么问题：在一条长度为 L 的道路上，如何用最少半径 R=5 km 的基站覆盖所有房屋？先将房屋位置 x₁≤…≤xₙ 排序。取最左未覆盖房屋 h，把新基站中心放在 min(h+R,L)，再跳过它覆盖的所有房屋，如此重复。若 h+R 超过终点，截到 L 即可，且仍覆盖 h。

扫描时只需保存最近一座塔中心 c：若当前房屋 x≤c+R，已有覆盖；否则创建新塔。因为房屋与塔中心都按从左到右处理，更早基站的右端不可能比最近基站更远。排序前提下扫描 O(n)，未排序时 O(n log n)。

课堂进入 greedy stays ahead 时指出：不能拿“每步覆盖房屋总数”作领先量。一个向中间偏的塔可能先覆盖更多房屋，却遗漏最左房屋，最后反而要用更多塔。课堂正在尝试的量是“前 k 座塔之后，从最左边起连续已覆盖到第几间房”。录音就在讨论这个最长前缀时截断。

22 · 课件后续自学补全：基站为什么最优

这个部分回答什么问题：若要把课堂提出的 stays ahead 指标写成完整证明，应如何收尾？以下根据课件 p37–38 自学补全，不属于本份 transcript 已确认的讲授范围。设贪心的第 k 座塔位置 gₖ，任一合法方案按位置排序后的第 k 座塔位置 aₖ。 课件正式证明比较的是第 k 座塔的位置，不直接比较已覆盖房屋总数；它和课堂讨论的连续前缀都表达从西向东推进，但不能未经论证就把两个指标视为完全等价。

1. 基础：最左房屋 h 必须被第一座塔覆盖，故任意方案 a₁≤h+R；贪心 g₁=h+R（若受道路终点限制则取 L）。
2. 归纳：假设 aₖ₋₁≤gₖ₋₁。令 h 是贪心第 k 座塔要照顾的第一间房，则 h>gₖ₋₁+R，gₖ=min(h+R,L)。若 aₖ>gₖ，则前 k−1 座塔的最右覆盖端不超过 gₖ₋₁+R<h；第 k 座塔又在 h+R 右侧（未截断情形），也盖不到 h，矛盾。受道路终点截断时 aₖ≤L=gₖ 自动成立。
3. 所以对每个 k，aₖ≤gₖ，等价于贪心塔的位置始终不比任意合法方案更靠西。最后一座贪心塔所对应的未覆盖房屋 h 无法被任意少一座塔的方案覆盖，否则与上面的领先关系矛盾，因此塔数最少。

23 · Greedy Lecture 复习与自测入口

这个部分回答什么问题：做新题时怎样把课堂方法用起来？先确认目标和合法输入，再尝试局部规则，主动找反例；若规则还站得住，给出交换后的可行与不变差，或定义可归纳的领先量，最后单独核算排序与扫描成本。

• 分数背包能交换任意小份额；0-1 背包的离散性会破坏相同比值规则。
• 活动选择的目标是最大数量；最早结束的交换证明须保住合法性和项数。
• 基站覆盖的比较量是从最左房屋开始的连续覆盖前缀，不是总覆盖数。
• 同一个贪心想法在改动目标、输入条件或边界后，需要重新证明。