上一课我们拿到了递归这件兵器,今天立刻开工:排序 (sorting)——全计算机科学最经典的问题。在大多数人眼里,InsertionSort 是一个双重循环;教授偏要你戴上递归的眼镜看它:「让别人把前 n−1 个排好,我只负责把最后一个插进去。」一句话就是整个算法。顺便,三问仪式全程走一遍:对不对?多快?能更快吗?——第三问的答案,埋在下一课。
老规矩(L1-1):碰到新问题,第一件事不是写代码,而是把问题本身用 Input/Output 定义清楚。排序的定义朴素得几乎无聊——但每个词都有讲究。
两个讲究:①「permutation」——输出必须是输入那些数的重新排列,一个不多、一个不少,不许丢、不许改;② 不等号是 ≤ 而不是 <——重复元素完全合法。讲义的例子里就有两个 8:
↓ 排序(升序 ascending order)之后:
面对一整个乱序数组,教授的第一反应完全符合他的懒人哲学:"I have a large array to sort. That's a lot of work, and I don't want to do all that work by myself."
那怎么办?"What if I can give this job to someone else... Maybe I ask my TA to solve it. Maybe I'll ask your friends. It's just somehow it's sorted."(要是能把活儿交给别人呢?交给助教、交给你朋友——总之,前 n−1 个元素不知怎么的就排好了。)这正是 3-1 的神谕心态:递归调用只要作用在严格更小的输入上,结果闭眼信。于是全局图景变成:
"As you can imagine, the insert procedure can also be thought of as a recursive procedure."(插入这个动作,本身也能递归地想。)于是一个递归套着另一个递归——双层结构登场。
n = 1:要把「最后一个元素」插进它前面那个已排序数组——可那个数组是空的。教授:"you have an element trying to insert it into an empty array... well, actually nothing to do, it's already inserted there."(其实什么都不用做,它已经插好了。)一个元素独自呆着,就是有序。
做一次比较:拿 A[n] 和它紧前面的那个元素 A[n−1] 比。两种结局:
忠实记录:教授课上当场修正了讲义的两处笔误——两处递归调用都应作用在 A[1..n−1] 上("Sorry, this is a typo. I will correct it.")。本页伪代码已按修正后的版本排印,与最终 PDF 一致。
双层递归结构:外层每回卷一步,就发动一整场内层递归。这个结构待会儿会精确映进证明(§05)和账单(§06–07)。
教授明知故犯:"I told you that you should not think of tracing the black box... and here, in order to convince you, I'd like to show you the actual run of an insertion sort."(为了让你服气,我们违一次禁。)讲义用整整一页动画追完 [8,1,9,2,8,4,6,5]——这里把它做成可以逐帧把玩的机器。
图例:虚线 = 被「晾在一边」的元素 · 绿 = 已排好的前缀 · 橙 = 正在插入的旅行元素 · 红圈 = 正在比较的邻居
看清两个阶段了吗?下潜阶段一次比较都没发生——递归只是不停地把活儿往外推:晾下 5、晾下 6、晾下 4……直到单元素触底;所有真正的工作都在回程:每回卷一层,就是「第 k 次迭代」——把第 2 个插进前 1 个,把第 3 个插进前 2 个……教授在转录里就是这么复盘的:"It first tried to insert the second element to the first element, then the third element to the first two elements, and so on."
彩蛋一:两个 8 全程谁也没跨过谁——比较用严格 >,相等不交换,排序保持相等元素的原始相对次序。这个性质叫 stability(本课未详述,后面的课再见)。彩蛋二:转录里教授顺口说「剥到空数组」,但按伪代码 n ≤ 1,下潜其实在单元素 [8] 就触底了——无伤大雅,两者都是 base case 的地盘。
"This may feel tedious and repetitive. Just bear with me——I trust that being exposed to more examples will help you get rid of the fear for induction proofs."(多见几个例子,归纳恐惧症自然痊愈。)新花样只有一个:算法有两层,证明也要两层。
顺序有讲究:先证 Insert,再证 InsertionSort。教授:"because we have two parts of the algorithm, we first prove the correctness of the inner part."为什么?因为 InsertionSort 的归纳步里要引用「Insert 是对的」这个事实——引理必须先立住,才能被引用。依赖链长这样:
3-1 说递归算法与归纳证明是同一枚硬币的两面 (two sides of the same coin)——今天是两枚硬币:每个递归函数配一份归纳证明,依旧逐行对应:算法的 base case ↔ 证明的 base case,递归调用 ↔ 归纳假设,「变小 + 拼装」那步 ↔ 归纳步里唯一要亲手检查的部分。
和证明一样,记账也要先内后外:"Just like when we do the proof... we also first need to figure out the time complexity of the insert function."先给它的账单起个名字:S(n)。
先看最顺的剧本:第二个 if 的条件不成立(A[n−1] ≤ A[n])。教授:"my entire insert will just finish. It's done."——if 后面没有任何语句,函数当场结束,只花 O(1)。但 L1-2 的老规矩:best case 说了不算。"You cannot say for any input I will never execute the body of the if statement——that wouldn't be true... we usually consider the worst case, because that gives us a guarantee: they will never exceed that estimation."(最坏情形给的是「绝不超过」的承诺。)
最惨的剧本是走进 if 里面。里面两行:Swap 花 O(1)——教授现场拆给你看:"temp = A[n], A[n] = A[n−1], A[n−1] = temp. That's some constant number of operations";递归调用 Insert(A[1..n−1])——输入 size 是 n−1,按 S 的定义,它的账单恰好就是 S(n−1),"because that's how we define S"。加起来:
这种自我引用的式子,3-1 已经打过照面:recurrence relation(递推式)。讲义把右边留成红色的问号——但教授在答疑里忍不住现场剥了一次洋葱。跟着剥:
轮到外层。给 InsertionSort 的账单起名 T(n),逐行记账——L1-2 的手艺,只是这次账本里会出现两个函数。
教授自己都笑:"now we have a probably even more convoluted recurrence relation."(一条更绕的递推。)绕在哪?T 的肚子里住着 S,而 S 自己还是一条递推——套娃。讲义再次把答案留成红问号:"how do you derive the big O out of this recurrence relation? Again, that has to wait for Thursday."今天不硬解,但我们可以走另一条路偷看答案——下一节。
Insert 记 S(n),InsertionSort 记 T(n)——都是以输入规模为参数的函数。有几个递归函数,就有几本账。
自己干的活按 L1-2 数(判断、交换都是 O(1));递归调用按定义记成「同名函数在更小 size 上的值」:Insert(A[1..n−1]) 记 S(n−1),InsertionSort(A[1..n−1]) 记 T(n−1);调用别的函数就挂它的账单:Insert(A[1..n]) 记 S(n)。
S(n) = O(1) + S(n−1),T(n) = T(n−1) + S(n)。列账单本课就能做;系统地解账单,周四(4-1 代入法)开讲。剥洋葱只是手感。
"For this very simple example, we can actually write a non-recursive version."——不是退回旧世界,而是借道:没有递归调用的代码,账单不含 T 和 S,好算得多。
逐句对照递归版:while 循环体三行 = 一次 Swap(A[j], A[j+1])——开循环时 key 就住在 A[j+1] 里,所以「A[j+1] = A[j]; A[j] = key」正是把这对邻居对调;while 的两个条件 = Insert 的两道闸门合体——「A[j] > key」对应第二个 if(还要不要继续换),「j > 0」对应 base case(撞到最左端必须停)。外层 for 则复刻了回卷:第 i 轮把 A[i] 插进已排好的 A[1..i−1]。教授把验证留给你:"You can verify this is doing exactly the same as in the previous example."——挑战题 C2 伺候。
讲义原文:while-loop: O(n) time;for-loop: n rounds, O(n) time each, in total O(n²)。内层 while 每轮最多走 O(n) 步,外层 for 恰好 n 轮,相乘封顶。"It's a quadratic time algorithm... It's not super efficient."
粗算里「每轮 O(n)」偏宽了:第 i 轮插入 A[i] 时,左边只有 i−1 个元素,while 最多走 i−1 步。把每轮的真实上限加起来——Gauss 求和正式在本课程出场:
还是平方档。教授:"even if you do the more careful analysis like this, you still get the quadratic running time."细算把系数从 n² 压到约 n²/2——而 P1(L2-2)早就教过:乘法常数不改档。想真正降档,得换算法,不是换算盘。
O(n²) 是 worst case 的判决。可哪种输入把 InsertionSort 折磨得最惨?哪种让它白拿工资?这次你来当出题人——亲手摆一个输入,看比较次数怎么变。
点两个格子交换它们 → 自定义阵型(会自动重新记账)。
每根柱 = 第 k 轮(把 A[k] 插进前 k−1 个)的比较次数。绿 = 该轮 1 次比较、0 次交换(best 分支);红 = 一路走到最左端(full walk);蓝 = 介于其间。
本课的坑,一半来自两场课堂答疑——同学们替你踩过了,对号入座。
base case 看输入的大小(size ≤ 1 才触发);best case 看输入的长相(任意大的 size,只要 A[n−1] ≤ A[n],Insert 照样一步收工)。教授答疑原话:"It's not just the base case."
细算的结果是 n(n+1)/2——系数减半,档次纹丝不动(P1:常数不改档)。粗算 n·O(n) 和细算 Σ O(i) 给出同一个 O(n²)。降档要换算法,不是换算盘。
教授自己的三行版都被自己亮了红牌:"I didn't tell you how."每个未定义的子过程都必须当场写清,否则违反 unambiguous(L1-1),不配叫算法。写作业时这是最容易丢分的一句。
展开必须停在 base case:n−i 变负,「负规模的耗时」没有意义。本课 S(1) = O(1) 恰好无关痛痒,但教授预警:以后会有 base case 干大活的例子——它的开销会写进最终答案。
四道,难度递增。C2 是教授课上亲口留的作业;C3 提前试驾周四的活;C4 把第 2-3 课的尺子拿出来做全套鉴定。先动笔再看解。
提示:逐轮数。第 k 轮(k = 2..n)把 A[k] 插进前 k−1 个,这一轮最少比几次?最多比几次?什么时候取到?
提示:循环不变式 (loop invariant) 就是「迭代世界的归纳法」——P(i) 扮演归纳假设,一轮 for 扮演归纳步。
提示:第二步会剥出一列 c·k 的和——Gauss 刚在 §08 教过。记住这只是手感,不是严格解法(周四见)。
提示:2-3 的核心口诀——bound(O/Ω/Θ)和 case(best/worst)是两个正交的旋钮。worst case 的 Ω 只需要展示「一族足够惨的输入」。
无限次尝试,零压力。七道题,把「委托—插入—两层归纳—两本账单」这条链各敲一遍。