上一课收尾时,MergeSort 的账单 T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + Θ(n) 摊在桌上没结;更早在 3-1,教授承诺过「怎么解递归算法的时间复杂度,周四见」。今天兑现。方法一简单得近乎无赖:先猜出答案,再用数学归纳法验收。猜是艺术(试错 + 经验),证是手艺——而这门手艺的全部秘密,藏在两个长得几乎一样的常数里:你能挑的 c,和早被定死的 c′。
递归算法的正确性,3-1 已经用归纳法收编;可一问「多快」,写出来的式子就开始自我引用。先把这种式子看清楚,再谈怎么解。
教授开场先回了一遍老账:归约 (reduction) 是全学期最重要的设计原则,递归是它的特例——自我归约:干一点活把问题变小,交给「会解同款问题」的下家,拿到结果再拼装。正确性证明顺着算法结构走归纳法,归纳假设就是那句「你信任下家把活干对了」。这些都顺。卡壳的是第二问:这算法多快?设递归算法的时间复杂度为 T(n),照着算法结构一记账,得到的是——
这种定义 T(n) 时右边又用到 T 自己的式子,叫recurrence relation(递推式)。它把算法的运行时间描述得一点不漏——但也一点没解:我们想要的是 L1-3 那种明码标价的「T(n) = O(某个具体函数)」,而不是一句「T 等于几个小号的 T 加点杂费」。三位老朋友的账单都长这样:
教授:"The formal name is solve by substitution, but I'd like to call it solve by guess."(正式名叫代入法,但我更想叫它「猜猜法」。)
第②步没有任何新数学:把「S(n) = O(n)」按 L1-3 的定义翻译回来,就是「找到某个常数 c,使 S(n) ≤ c·n(对一切 n ≥ n₀)」。第二周肉搏 (c, n₀) 证书的手艺满血回归——只是这次的对手不是显式函数,而是一条递推式,所以证明工具从「代数放缩」换成「归纳法」。这也是递归↔归纳这枚硬币的第三面:3-1 用归纳证递归算法「对不对」,今天用归纳证递归算法「多快」——同一枚硬币,换个刻面。
动笔之前先立规矩。这一节是全课的命门——后面每一条推导、每一个陷阱、每一道挑战题,都会回到这两个常数的身份差异上。
归纳证明一开工,场上会出现两个常数。长得像双胞胎,身份天差地别:
最小的递推,完整走一遍全流程。之后所有战役——n² 也好、下界也好、期末考卷上的也好——全是这套动作的变奏。
猜:S(n) = O(n)。(每层干常数的活、总共剥 n 层,直觉上是条直线。)按定义翻译成目标:要证 S(n) ≤ c·n,c 由我们挑。归纳三件套,逐件核对:
讲义原话:"doesn't matter for asymptotic bounds, can assume S(1) = 1."(对渐近界不重要,设 S(1)=1 即可。)教授的解释是一则等比数列的寓言:一列数每次翻倍,从 2 出发变 4,和从 100 万出发变 200 万——增长率一模一样,都是「翻倍」。初始值决定每一项的具体数值,但渐近记号根本不审数值,只审增长率 (growth rate)。所以 base case 随便设:S(1)=1 行,S(1)=10 行,嫌麻烦设 S(5)=15 也行——"whatever convenient for you to complete the proof."(怎么方便怎么来。)这份自由后面会反复用到,先记住:base case 不重要 ≠ 可以没有,而是「具体取值随便」。
假设 S(m) ≤ c·m 对一切 m < n 成立——特别地,S(n−1) ≤ c(n−1)。教授特意指出这比「只假设 n−1」更强 ("actually this is something stronger… we're making the hypothesis stronger than what we need")。为什么模板一律写强形式?3-1 的挑战题 C3 已经埋过答案:递推每次剥几层是算法说了算(MergeSort 一刀剥一半!),强形式一步到位、永不翻车。
S(n) = O(n) 到手,代回 InsertionSort 的账单:T(n) = T(n−1) + S(n) 变成 T(n) = T(n−1) + O(n)——两级引爆的第二级,点火。
猜:T(n) = O(n²)。(3-2 数循环数出过 Θ(n²),这猜不算冒险——课堂上教授的说法是 "think of it as I'm lucky"。)目标:T(n) ≤ c·n²。假设:T(m) ≤ cm² 对一切 m < n;特别地 T(n−1) ≤ c(n−1)²。代入递推:
和第一战唯一的实质区别:猜想升到二次,展开 (n−1)² 后多出一项 −2cn——正是这笔「负资产」给了我们吃掉 +c′n 的本钱。残差 (c′−2c)n + c 是一条直线:只要斜率 c′−2c 为负,它迟早跌到 0 以下;c 挑得越大,跌得越早。亲手拨一拨:
场景:上面的证明推进到「需要残差 R(n) = (c′ − 2c)n + c ≤ 0」。演示中 c′ = 2(固定,碰不得),你只有一个旋钮:自由常数 c。目标:让格子全绿(允许贴线 R = 0——≤ 不怕取等)。
同一条递推 T(n) = T(n−1) + O(n),三种猜法,三种命运。教授专门演示了猜错的下场——"later, I'll show you what happens if we guess wrong." 兑现时刻。
上界只承诺「不会更糟」,却不说自己离真相多远。想把真相钉死,得从下面再顶一块板子。这一段,课堂上有个同学替所有人问了两个好问题。
于是递推升级为 T(n) = T(n−1) + Θ(n)(InsertionSort 的非递归部分确实是 Θ(n):worst case 恰好比较 n−1 次,3-2 数过)。猜:T(n) = Ω(n²)。目标:T(n) ≥ c·n²——注意不等号已调头。整条链条跟着调头:
讲义最后一页(6/6)清点战果——三张账单,两张已结,一张高挂问号。
| 算法 | 递推式 | 解 | 出处 |
|---|---|---|---|
| Insert / Merge | S(n) = S(n−1) + Θ(1) | Θ(n) | §04 上界 · 挑战题 C1 下界 |
| InsertionSort | T(n) = T(n−1) + Θ(n) | Θ(n²) | §05 + §07 三明治 |
| MergeSort | T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + Θ(n) | ? | 高挂——见下 |
那个红色问号,教授留了话:"We haven't done anything with merge sort… but it turns out if you make the correct guess, you can also solve it using this method. I will record a separate video for the merge sort case—it's really repetitive."(方法完全够用,只要猜对;单独录一支视频演示。)也就是说,4-1 交给你的武器已经能斩 MergeSort,缺的只是那一发正确的猜。挑战题 C3 会让你先用今天的工具给它箍一个不紧的上界,亲手感受「猜」的份量。
把整套动作压缩成可以带进考场的清单,再把最容易栽的四个坑插上旗。
账单里若嵌着别的未知函数(如 S(n)),先解它、代回,得到一条只含 T 和显式函数的递推。
试错 + 经验(以后有 4-3 / 4-4 帮你生产猜想)。宁可先猜松点——松的能证过,再逐步压紧。
O:要证 T(n) ≤ c·g(n);Ω:要证 T(n) ≥ c·g(n)。写明:c 由我们挑,暂不定值。
对一切 m < n 成立;点名递推里实际出现的那几个 m(n−1、⌊n/2⌋……)。base case 的取值随便,先欠着。
递归项用假设换掉(绿);O/Θ 项换成固定常数 c′(红)。从这行起,式子里没有任何渐近记号——全是显式常数。
上界:让残差 ≤ 0(c 往大挑);下界:让残差 ≥ 0(c 往小挑)。残差在有限几个小 n 上不听话?划进 base case。
报出 (c, n₀),宣读:"因为能找到这样的常数,按定义,猜想成立。" ∎
c′ 是别人(往往是昨天的你)证 O(1)/O(n) 时交过的证书,选定即钉死。你的自由只在 c 上。讲义把 c′ 标红,就是防这只手。
归纳步必须收口到同一个 c 的 cn 上;(c+1)n > cn,链根本没接上。写 "= O(n)" 等于每层偷换一次 c——递归 log n 层,c 膨胀成非常数。归纳内部禁用渐近记号,全程显式常数。(案发现场:挑战题 C4。)
O 只是上界,离真相可能差十万八千里(O(2ⁿ) 也「对」)。要 Θ,必须再打下界——而且递推里得有 Θ 级的原料(§07:O 的方向接不上 ≥ 的链)。
单向逻辑:猜错 ⇒ 必失败;失败 ⇏ 猜错(可能是证法问题,比如假设形式太弱)。实践上先换猜没错,但下结论要嘴严——教授原话立此存照。
四道,难度递增。C1 补上讲义总结页欠的半边账;C3 提前挑战 MergeSort;C4 是一份精心伪造的「证明」,等你验尸。先动笔再看解。
提示:照抄 §07 的动作——所有箭头调头。收口时 c 该往哪个方向挑?
提示:n₀ 的自由度不是摆设;⌊n/2⌋ ≤ n/2 且 log 单调。这条递推的形状,几周后你会在 BinarySearch 身上重逢。
提示:两个递归项都要代入假设——强归纳形式终于显出全部威力。一般情形可用恒等式 a² + b² = ((a+b)² + (a−b)²)/2,其中 a = ⌈n/2⌉、b = ⌊n/2⌋,a + b = n,|a − b| ≤ 1。
提示:重读坑二。归纳到底要求把链条收口到哪个式子上?"= O(n)" 三个字符在归纳内部意味着什么?
无限次尝试,零压力。七道题,把「猜—证—两个常数—两个方向」各敲一遍。