COMP3121 Week01 学习笔记

01 本周地图：先设计，再证明，再计时

输入：一个带约束的问题 → 处理：抽象输入输出、设计步骤、证明正确、分析代价 → 输出：能清楚解释且满足要求的算法。COMP3121 的核心是解决问题与沟通，不是把更多代码写出来。

02 从故事到算法：Geese in a Trench Coat

来源：Welcome p13–19。n 只鹅的身高 h₁,…,hₙ 都是正整数，目标总高度为 T。判断是否存在两个不同下标 i < j，使 hᵢ + hⱼ = T；要求最坏时间 O(n log n)。故事里的风衣并不影响算法，真正重要的是“两个不同对象”“精确相等”和“最坏时间”。

自然语言描述：先用归并排序将身高按非递减顺序排列。依次选取每一个位置，计算距离目标总高度还差多少，并在该位置之后的已排序部分用二分查找寻找这一高度。找到则返回“存在”；所有位置都失败才返回“不存在”。这里只需判断是否存在，因此排序后无需保留原下标；若要求返回原来的鹅，应同时保存原下标。

正确性分两边：若算法返回“存在”，它确实找到了两个不同位置且和为 T，所以没有误报。若存在解，设这对鹅在排序后的较小位置为 i，另一位置一定在它右侧；处理 i 时，二分必能找到 T−h[i]，所以不会漏报。有限个 i、每次二分区间严格缩小，故会终止。

合并时间用加法，不用乘法：O(n log n) + n·O(log n) = O(n log n)。在 n=8 的粗略规模模型中，排序量级 8×3，8 次搜索量级 8×3，两段相加是48个模型单位；不是精确机器操作数。用哈希表可能得到期望 O(n)，但不能直接声称满足题目的最坏 O(n log n) 保证。

03 正确性证明：覆盖所有合法输入

来源：Welcome p4–6、p19。测试失败能否定算法；测试通过只说明这些样例没有推翻它。证明必须解释任何合法输入都成立。先设计再编码的流程是：读题 → 设计 → 检查正确性与效率 → 必要时重新设计 → 实现；否则容易陷入不断补丁、却没有解决思路错误的循环。

04 复杂度：O、Ω、Θ 不是三种输入情况

来源：本学期 Foundations PDF p3–12。先确定 n 是什么，再选定要分析的运行时间函数 f(n)。最坏、最好、期望描述输入情况或概率模型；O、Ω、Θ描述上界、下界、紧确界，这是两条不同维度。

上述形式化不等式是对课件口头定义的背景补充：n 为输入规模；f 为待分析代价；g 为比较函数；c、n₀ 是不能随 n 改变的常数。用途是证明增长率，而非测量秒数。例：n≥1 时 2n ≤ 2n+7 ≤ 9n，取下界常数2、上界常数9、n₀=1，即得 Θ(n)。代入 n=10，20≤27≤90。

上下界可互换方向：f(n)≤c·g(n) 等价于 g(n)≥(1/c)·f(n)，因此 f=O(g) 推出 g=Ω(f)。例：100n≤100·n，则 n≥0.01·100n。不要把“函数 f 的下界”自动升级为“整个问题对所有算法的下界”。找无序数组最大值必须查看每个元素，否则未看的元素可能更大，这才支持问题需要 Ω(n) 的论证。

求和、乘积规则对非负函数的 Ω 与 Θ 也成立。插入排序最好情况线性、最坏情况二次；普通 BST 操作取决于树高。写 O 不是强制在说最坏情况，写 Ω 也不是强制在说最好情况。

05 对数：为什么“每次减半”只需少量步骤

来源：本学期 Foundations PDF p14–15。logₐb 表示 a 需要几次幂才能得到 b：n=logₐb ⇔ aⁿ=b，a,b>0 且 a≠1。例如 log₂8=3，因为2³=8。算法增长率比较通常取固定底数 a>1。

减半计数（背景推导）：经过 k 次减半后，候选量约为 n/2ᵏ。令 n/2ᵏ≤1，得 k≥log₂n。n=16 时4次减半即可从16缩到1，但还可能需要检查最后一个元素。标准二分在 n≥1 时最多 floor(log₂n)+1 次中点检查，空数组为0次。

06 数据结构：按需要的操作选工具

来源：本学期 Foundations PDF p17–21。结构选择决定性能保证。n 为元素数，h 为树高；期望代价不能当成最坏代价。

树高按边数计：完美二叉树 n=15 时 h=3，而15节点单链 h=14。课件的 h≈log₂n、h≈n 表示量级，不是精确等式。堆“完全”约束树的形状，“父≥子”约束数值，两者都需要。

缺失数原题（Foundations p20）：1..n 中恰有一个数缺失，余下各出现一次。扫描标记后找未出现者，O(n)时间、O(n)空间。补充解答：缺失值=n(n+1)/2−ΣA[i]，在单位代价且整数可容纳的模型下只需O(1)额外空间；n=5，A=[1,2,4,5]，15−12=3。若允许重复或缺多个数，该结论不再适用。

07 二分查找：删掉的部分必须不可能含答案

来源：本学期 Foundations PDF p22–24。输入必须已排序；下面用非递减数组解释如何安全排除。 设A为数组、x为目标、l与r为当前闭区间端点，m=l+floor((r−l)/2)为中点。例如l=0、r=6时m=3。

1. 若 l>r，候选集已空，返回不存在。
2. 取中点 m。如果 A[m]=x，返回 m。
3. 若 A[m]<x，则从 l 到 m 的值都≤A[m]<x，全部可排除，令 l=m+1。
4. 若 A[m]>x，同理排除 m 到 r，令 r=m−1。重复检查。

每次不命中都排除中点并严格缩小区间，所以不会死循环。最坏时间 O(log n)，下面迭代实现只保存几个变量，辅助空间 O(1)。课件递归版本还会使用 O(log n) 调用栈。重复元素不影响“找任意一次出现”，但寻找第一个位置需要修改逻辑。

function binarySearch(A, x) {
    // Precondition: A is sorted in nondecreasing order.
    let l = 0, r = A.length - 1;
    while (l <= r) {
        const m = l + Math.floor((r - l) / 2); // Midpoint
        if (A[m] === x) return m;
        if (A[m] < x) l = m + 1; // Keep the right candidate interval
        else r = m - 1; // Keep the left candidate interval
    }
    return -1; // Empty candidate interval
}

08 二分答案：把最优化变成单调判定

来源：本学期 Foundations PDF p33–43。判定问题问“目标 t 能否达到”，最优化问题问“最大的可行 t”或“最小的可行 t”。把判定结果记作 f(t)∈{0,1}，先证明单调性：000…111 找第一个1；111…000 找最后一个1。方向不同，不能机械沿用同一边界更新。

在上面“最小容量”的例子中，维护可能答案的整数范围[L,R]，取下中点M=floor((L+R)/2)。若M可行令R=M；若不可行令L=M+1。结束时验证候选可行。全不可行时报告无解，不能把最后一个端点直接当答案。

复杂度：候选答案集合记为 A，范围大小 |A|，每次判定代价 C，则总成本 O(C log |A|)，另加建立数据或边界的代价。例如范围1..16、判定每次扫描100个项目，约4轮×100个项目=400个模型单位。不能把判定过程免费算成 O(1)，也不要把 |A| 与输入元素数 n 混为一谈。

先判定，再优化：令 C(t)=Σ（i=n..2n−1）max(t−A[i],0)。A[i]是原有序数组第i个数，t是目标中位数，k是可用加一次操作的总次数；C(t)是把最大的n个数都抬到至少t所需的最小成本。f(t)=1 ⇔ C(t)≤k。max保证已经够大的元素成本为0，不能用负数抵消其他元素的缺口。

为什么只看最大的n个数？中位数至少t，当且仅当至少n个数≥t。任意选择n个要抬升的数时，若选了较小的x而没选较大的y，则以y替换x不会增加max(t−值,0)的成本。不断交换可得到最大的n个数，因此这个和既是必要的最小成本，也是可直接实现的充分条件。若尚有剩余操作，继续增加任意数不会降低中位数，所以“恰好k天”也由C(t)≤k判定。

二分区间为[A[n],A[n]+k]：不做增长就能保持原中位数；要让中位数超过A[n]+k，至少要把原来前n个数中的一个抬高超过k，不可能。C(t)随t不减，所以可行性为111…000。维护L可行、最优值在[L,R]：取上中点M=ceil((L+R)/2)；若可行令L=M，否则令R=M−1。L<R时上中点大于L，每轮区间严格缩小；结束返回L。

讲义给出枚举O(kn)、二分O(n log k)，这里n是上半段元素个数、k是操作预算，不是数组长度。按边界补全：k=0直接返回A[n]；k≥1用O(n log(k+1))表示。每次成本判定O(n)，候选有k+1个。若输入未排序，另加O(N log N)，N=2n−1；本题输入已排序，不应凭空增加排序步骤。

09 归约：改造输入，复用已有算法

来源：Foundations PDF p26–32、p46。输入 → 转成已知问题的实例 → 调用标准算法 → 把结果解释回原问题。这是本讲的解题策略；这里不提前套用后续不可解问题模块的技术定义。归约不是只说一个算法名称，要讲清转化、对应关系和额外成本。

构造H=(V,E′)，其中E′={(a,b)∈E | color(a)≠color(b)}。V为原顶点集合，E为原边集合，color为顶点颜色；只删同色端点之间的边，保留所有顶点，包括孤立点。对H从u运行BFS，返回v的距离；不可达则报告不存在。BFS逐层扩展，每层增加一条边，因此适用于无权最短路。

图的读法（PDF p29、31）：蓝色为u,c，红色为a,d，绿色为b,e,v。删去u–c、a–d、b–v；其他边保留。原图有u→b→v，长度2，但b与v同为绿色，不合法；过滤后可走u→a→c→d→v，长度4。颜色可以重复，只要不连续重复。

正确性要双向：G中每条合法路径的每条边都异色，所以完整保留在H；H中每条路径的边都来自G且端点异色，因此在G合法。路径长度没有改变，候选路径集合及长度一致，故H中的最短距离等于原题最优值。只证明H的路径合法还不够，还需证明没有删掉原题的合法解。

复杂度用邻接表计：扫描顶点与边构造H为O(|V|+|E|)，BFS为O(|V|+|E′|)，|E′|≤|E|，总O(|V|+|E|)。课件图有7个点、10条边，删3条后7条；成本模型可看作构造约7+10，再搜索约7+7，两个阶段相加。另建图与队列空间O(|V|+|E|)。加权边不能直接以普通BFS求最小权重；路径依赖历史的限制也未必能只靠删边表达。

10 递归与枚举：调用熟悉过程，也要算总成本

来源：Foundations PDF p44–47。递归把大实例转成更小的同类实例：写出等价条件 → 规定基本情况 → 确认规模严格减小 → 合并答案。与归并排序同属“分解问题”的大类，但回文每次只留下一个子问题，并不是每次分成两半。

回文测试原题：给定长度为n的字符串s，判断是否正反相同。长度0或1直接为真；其余情况，首尾不等为假，首尾相等时结果等于内部子串的回文结果。用端点写为P(l,r)=(s[l]=s[r])且P(l+1,r−1)，基本情况l≥r为真；l,r为当前区间端点。

补充工作量分析：用两个下标访问原串、不复制子串时，T(n)=T(n−2)+O(1)，最多floor(n/2)次字符比较，总O(n)时间，直接递归调用栈O(n)空间。若每次复制内部字符串，额外字符复制量为(n−2)+(n−4)+…，可能变成O(n²)；不能只数递归次数。

11 自测：先独立解释，再展开答案

12 本学期学习安排与复习清单

以下来自2026-09-17重新下载且哈希一致的2026 T3 Welcome；课件中的一般安排不等于某项任务的实时状态。p27–30：Portfolio 占60%，Final Exam 占40%；期末门槛为40%。任务在 Formatif 按周发布，选择目标等级并根据反馈改进。书面任务通常在当周周一发布、周日首次提交；第 x 周的口头展示在第 x+1 周自己的 lab 结束前完成。

p27–29：Portfolio 的 PS/CR/DN/HD 层级权重为55/15/15/15，最终由导师整体评价，也考虑表达、展示及部分进展。任务类型 W/M/D/E 的相对权重为5/2/10/10；Engagement 在自己的排课 lab 参与，9次中取最好7次。这些相对权重不是课程总分的直接百分比。

p32–34：第6周不授课，第4周周一停课；lab 中与单个学生讨论最多8分钟。课件明确 Portfolio 和考试不允许使用生成式 AI，Portfolio 允许简单拼写与单词/短语翻译辅助。本页用于理解课程与自主复习，不作为提交答案。具体任务要求以老师发布内容为准。

• 能从故事中提取输入、输出、限制与性能目标。
• 能用自然语言解释两鹅配对，并处理重复身高和同一个对象不可复用。
• 能区分输入情况与 O/Ω/Θ，能给出常数界证明。
• 能写出对数定义、三条运算法则和换底公式并代入计算。
• 能解释哈希表、BST、平衡BST、堆各自保证什么。
• 能手动执行二分，解释为何删除区间安全，以及为什么会终止。
• 能证明二分答案所需的单调性，并计入每次判定成本。
• 能用频率表计数，并把初始化值域的成本算进去。
• 能用路径双向对应及长度不变证明彩色最短路归约。
• 能解释最大中位数的最低成本、单调性及最后一个可行值。
• 能写出回文的基本情况，并区分递归次数与子串复制成本。

核对本学期原课件：Welcome · 鹅题 PDF p13 · Foundations · 频率表 p20 · 彩色路径 p28 · 中位数公式 p38 · 回文 p45