上一课每证一个 Big-O,都要亲手挑 c、挑 n₀、写链条——像每次做饭都从种麦子开始。这一课把九条性质一次性证好、装进工具箱:从此丢常数、定多项式、比对数指数,几乎再也不用碰 c 和 n₀。但有一条铁律:每件工具入箱前,必须先用定义证明它。
教授开宗明义:上个视频我们反复直接套定义;这个视频要从定义推导出一批可复用的性质,让"证 f = O(g)"变得省力。
九条性质,按用途分成四组。这就是今天的货架:
| 组 | 性质 | 一句话 | |
|---|---|---|---|
| 积木 | P1 · P2 · P3 | 丢常数 / 比幂次 / 加法合并——多项式的三块积木 | §02 ↓ |
| 推论 | P4 | 多项式一眼定档:只看最高次项 | §03 ↓ |
| 比大小 | P5 · P6 · P7 | 多项式碾压对数 / log 底数无所谓 / 指数碾压多项式 | §04 ↓ |
| 组合器 | P8 · P9 | 传递性 / 乘法法则——把已知的 O 拼成新的 O | §07 ↓ |
先上三条最基本的。前两条的证明各只有一行;第三条是本课第一次完整演示"拆包→拼装→打包"。
这正是我们发明 Big-O 的两大动机之一(另一个是无视小 n)。乘常数是把函数曲线整体"拉伸"——绝对值变了,增长率纹丝不动。证明就一行:
教授补充:c 取 a+1 也行,任何 ≥ a 的 c 都行——又见"证书不唯一"。
幂越高,增长越快——所以低幂 = O(高幂)。证明更短:取 c = 1, n₀ = 1,不等式 nb ≤ na 两边同除 nb(n ≥ 1 时合法)变成 1 ≤ na−b,因 a ≥ b 显然成立。∎ 注意方向:a ≥ b 才行,别写反。
直觉(教授版):f 和 g 都是"增长不超过 h 的慢家伙",两个慢家伙加在一起,也别指望追上 h。但直觉不算数——这条的证明要"用三次定义":两条已知的 O 各拆包一次,要证的 O 打包一次。亲手走一遍:
三块积木一拼,多项式立刻缴械:adnd + ad−1nd−1 + … + a₁n + a₀ = O(nd)。按幂次降序排好,最高次项 (leading term) 一个人决定整个函数的档次。
选一个多项式,看谁是首项;再拖动 n,看首项在整个函数值里的占比怎么走向 100%——"低次项迟早沦为零头"的实感:
(log n)a = O(nb),对任意常数 a, b > 0。注意量词的狂妄:a 可以是 100,b 可以是 0.01——对数的任何次幂,都翻不过多项式的任何正次幂。
先别急着信——亲眼看一场。下面的赛道上,蓝线是对数的幂,绿线是多项式。注意小 n 处谁在赢:
证明呢?教授原话:"I will skip this proof. You can read it line by line."(这个证明我课上跳过,你们逐行读。)那我们就逐行读——每一步只用初等对数技巧:
loga n = O(logb n),对任意常数 a, b > 1。计算机科学里写 log 默认底 2(我们用二进制),但写 log₄、log₁₀、ln 都行——因为在 Big-O 眼里全是一回事。
证明就这一行:换个底,只是乘一个常数(loga b 不含 n),P1 直接吃掉。比如 log₂ n = log₂10 · log₁₀ n ≈ 3.32 · log₁₀ n——比值恒为 3.32,一条水平线。
na = O(bn),对任意常数 a > 0、b > 1。又是狂妄的量词:哪怕 n¹⁰⁰⁰ 对上 1.1ⁿ,多项式也输。
证明呢?教授原话:"I'll leave that as an exercise."(留作练习。)套路和 P5 那段对数戏法很像——这个练习我们真的会做:挑战题 C4 ↓,等你亲手拆。
最后两条不比大小,而是把已知的 O 拼成新的 O——工具箱里的扳手和螺丝刀。
增长率的"≤"当然可以串:f ⪯ g ⪯ h,所以 f ⪯ h。证明又是那台拆包机——两条已知各拆包一次,拼装,打包。唯一的新意:这次两条不等式是串联(代入)而不是并联(相加),所以常数相乘:
两个函数相乘,上界也相乘。教授特别预告:"这学期我们基本会一路偷偷地用它 (use this implicitly)"——而它最常见的一次出场,就是分析嵌套循环时的 n·log n:
n log n 是排序等算法里最常见的运行时间之一,先混个脸熟。P9 的证明也被留作练习("Proof: Exercise")——它在挑战题 C2 等你,比 P7 那个简单。
工具全部入箱。现在来干这节课真正的活:拿到一个乱七八糟的 T(n),全程只报性质编号、不碰 c 和 n₀,把它的档次定出来。
把 L03 的"增长率阶梯"用今天的三条比大小性质(P5/P6/P7)升级成完整食物链——每一道分界线,现在都有定理撑腰。
n log n 卡在 n 和 n² 之间:n·1 ≤ n·log n(n ≥ 2),而 n·log n = O(n·n) = O(n²)(P9)。
P1 只管乘法位上的常数。指数位上的 5 是硬的:2⁵ⁿ = 32ⁿ,底数换了,跨档(L04)。丢常数前先问:它长在哪?
换 log 底 = 乘常数 logab(P1 吃掉);换指数底 = 乘 (b/a)ⁿ,一个随 n 爆炸的因子。P6 与 L04 挑战题 C2 各管一边。
nb = O(na) 要求 a ≥ b。低幂钻进高幂的 O 里,不能反着钻。写之前默念:O 是"≤"。
(log n)¹⁰⁰ 要到 n ≈ 2¹⁷⁴⁰⁰⁰ 才输给 n⁰·⁰¹;0.001n⁵ 要到 n ≈ 10⁶ 才压过 999n⁴。有限实验永远证不了也推不翻渐近结论——L04 就说过:单点不是证据。
四道,难度递增。C2 和 C4 正是讲义里两处 "Proof: Exercise" 的正主——教授留的作业,咱们替他收了。先动笔再看解。
提示:f(n) 和 g(n) 各自与 m(n) 什么关系?一张 (c, n₀) = (2, 1) 的证书就够了。
提示:拆包两次,然后把两条不等式相乘。想想:不等式相乘,什么时候是合法操作?
提示:上一课有个现成的跨档反例……f 和 g 只差一个乘法常数时,指数上会发生什么?
提示(教授说套路像 P5):把两边都写成 2 的幂,比较指数;需要"log n 最终小于 εn(ε 任意小)"——这可以从 P5 的显式不等式 log n ≤ (1/δ)·nδ 里榨出来。
无限次尝试,零压力。七道题,把九件工具各敲一遍。