这是渐近记号的收官课。三件事:把 O/Ω/Θ 与 best/worst case 的关系一句话钉死(正交,别再混);拆解教授亲口所称的"核武器"——极限判别法,对付形状狰狞的函数,一步定档;最后立下写答案的行规:最简形。收尾再开一场八回合竞技场,把两周攒下的兵器全部拉出来遛一遍。
教授开场:"This is the last video in the introduction of asymptotic notations."(这是渐近记号导论的最后一个视频。)总结课不补新地基——它把两周的地基连成一张地图,再塞给你一件此前没有的重武器。
先清点家底。两周下来,你的军火库里已经有:
| 来自 | 兵器 | 一句话 |
|---|---|---|
| 1-2 | best / worst / average case | 同一个算法可以谈好几条"运行时间函数" |
| 1-3 | Big-O 定义 + 证书 (c, n₀) | 增长率意义下的"≤":上界 |
| 2-1 | 证明/证伪攻防术 | 放缩、c–n₀ 交易、量词翻转、对抗游戏 |
| 2-2 | 九条性质 P1–P9 + 食物链 | log ≺ 多项式 ≺ 指数;多项式看首项 |
| 2-3 | Ω(下界)与 Θ(夹住) | "≥"与"=",三把尺子配齐 |
今天这节课,幻灯片一共只有四页——但每页都是一颗钉子:
| 幻灯片 | 钉什么 | 去处 |
|---|---|---|
| 1/4 | O 与 Ω 的"上界/下界"复述 | §02 ↓ |
| 2/4 | bound 与 case 是正交选择 | §03 ↓ |
| 3/4 | 极限判别法(核武器)+ 证明 | §04–06 ↓ |
| 4/4 | 最简形:写答案的行规 | §07 ↓ |
| — | 大盘点:竞技场 + 大一统表(本课补给) | §08–09 ↓ |
幻灯片 1/4 用两段完全平行的话复述 O 和 Ω。注意教授反复敲的黑板:比的是增长率 (growth rate),"we're not talking about absolute values of the functions"——不是比谁的数值大。
三把尺子在图上长什么样?拿 f(n) = 2n² + 8n 对 g(n) = n² 亲手夹一次——上尺 c₂·n² 从头顶压,下尺 c₁·n² 从脚底托,两把都夹住,f 就被"焊死"在 n² 档:
幻灯片 2/4 只有三行字,却是全课最容易考、最容易错的一页:Big-O / Big-Ω 说的是给一条运行时间函数从上还是从下去 bound;best / worst / average case 说的是你在 bound 哪一条函数。原话高亮:"They are independent, orthogonal choices."
还是那位老朋友 LinearSearch(1-2:worst 扫全程 T(n)=an+b,best 第一格命中)。点亮任意一格,看这个组合说的是哪句话:
教授还顺带交代了本课程的默认口径:"in this course we're mostly talking about the worst case analysis"——以后不加说明时,报的都是最坏情况;但哪怕是最坏情况,也既有上界又有下界:worst-case = O(n) 说"最坏也不会比线性差",worst-case = Ω(n) 说"最坏确实会差到线性"。两句合起来才是那句最有分量的话:worst-case = Θ(n)。
教授原话毫不谦虚:"And now I'm ready to give you this kind of nuclear weapon for asymptotic notations."(渐近记号的核武器。)一次极限计算,三种判决。
直觉先行:比值 f/g 是两个函数的相对身高曲线。看它的尾巴——
教授只证判据①,②③留给你("you can prove them very similarly"——它们在挑战题 C1、C2 ↓等着)。证明的全部内容,就是把"极限"翻译回不等式,再认出那恰好是 O 和 Ω 的证书。逐步拆:
教授贴士:"If you're a bit rusty with calculus one, it's a good time to go back and review some related subjects."(微积分一手生了?正好回炉。)这里用到的只有极限的 ε 定义,没有洛必达。
四个试件,一台机器。前三件展示三种判决;第四件是教授的警告成真现场——极限不存在,核武器哑火,回定义救场。
幻灯片 4/4,以后每次作业都用得上:分析算法途中你会得到 O(n + n√n) 这种数学上完全正确的结论,但作为最终答案它"not acceptable"——必须化到最简形 (most concise form):括号里只留那一个主导函数。
每题点出统治项(或选出正确的最简形)。点错不扣分,点对入库。
两周的兵器全部上场:1-2 的 case、1-3 的定义、2-1 的攻防、2-2 的性质与食物链、2-3 的 Ω/Θ、今天的极限判别。每回合一对 (f, g),把成立的记号全部点亮再交卷——注意,可能不止一个,也可能只有一个。
小抄(赛前最后一眼):Θ 成立 ⇒ O、Ω 必然同时成立;比值 → 0 ⇒ 只有 O;比值 → ∞ ⇒ 只有 Ω;比值震荡 ⇒ 自己回定义想。
两周内容,一张表收编。左三列是定义世界(2-3 之前),右两列是今天的新桥梁。
| 记号 | 增长率读法 | 证书(定义) | 极限判据(若 lim f/g 存在) | 一句话 |
|---|---|---|---|---|
| f = O(g) | f ≤ g | ∃c,n₀: f(n) ≤ c·g(n) | lim ≠ ∞(有限即可,含 0) | g 从上界住 f |
| f = Ω(g) | f ≥ g | ∃c,n₀: f(n) ≥ c·g(n) | lim ≠ 0(含 ∞) | g 从下托住 f |
| f = Θ(g) | f = g | ∃c₁,c₂,n₀: c₁g ≤ f ≤ c₂g | lim = a > 0 | 同档,上下夹死 |
表格右列的箭头是单向的:极限结论 ⇒ 记号成立;反过来记号成立推不出极限存在(D 号试件 / 挑战题 C3)。
多项式、log、指数的常规组合:食物链 + P1–P9 秒判,不必动极限。多项式看首项(P4),log 输给任何正幂(P5),多项式输给任何底数 > 1 的指数(P7)。
带尾巴的怪函数(n²/log n、3ⁿ/n⁴…):比值化简、取极限。a > 0 ⇒ Θ;0 ⇒ 只 O;∞ ⇒ 只 Ω。
比值震荡:核武器哑火,亲手找 (c, n₀) 或 (c₁, c₂, n₀)。"You always have the definition"——定义永远在岗。
丢系数、丢低阶项、求和化封闭形;括号里只留主导函数本尊,不向上取整。
bound(上/下)选的是压还是托,case(best/worst/avg)选的是压托哪条函数。两根轴正交,六个组合都合法。worst case 也有 Ω,best case 也有 O。
n = O(n) 且 n = Θ(n)。O 从不排除同档;真想说"严格轻",要么说"O 成立且 Ω 不成立",要么等以后的小 o(本课未详述)。
(2+(−1)ⁿ)·n 对 n 的比值永远震荡,极限不存在,但它就是 Θ(n)(证书 (1, 3, 1))。定理哑火 ≠ 命题为假,回定义。
它是真命题,但不是合格的最终答案——行规要求最简形 O(n√n)。同时别矫枉过正把 n²/log n 磨成 n²:最简是"只留主导项",不是"凑成好看的幂"。
四道,难度递增。C1、C2 正是教授那句"you can prove them very similarly"点名的判据②③;C3 拆穿单向箭头;C4 是一只集大成的怪兽。先动笔再看解。
提示:ε 的自由是你的——挑一个最省事的,比如 ε = 1。这题连 L > 0 都不需要。
提示:"≠ 0"藏着两种情况——有限正数,或 ∞。两种情况的"极限定义"长得不一样,分开处理。
提示:f/2ⁿ = 2^((−1)ⁿ)——先把这个比值算出来,一切自明。§06 的 D 号试件换了件指数马甲。
提示:先把 Σi² 的封闭形请出来(n(n+1)(2n+1)/6),用核武器给它定档;再让三项排座次——注意 2ⁿ/n² 不是"好看的幂",但它就是答案本人。
无限次尝试,零压力。七道题,把正交、极限、最简形各敲一遍。