Algorithm Design · Lecture 2-3

配齐尺子:Ω 与 ΘAsymptotic Notations: Big-Omega and Theta

Big-O 的尺子只有一面刻度:「增长不快于」。这节课把渐近记号家族的另外两位成员请进门——Ω 说「不慢于」,Θ 说「同阶」——三把尺子终于配齐。顺手还要拆掉一个最流行的误解:O 不是「最坏情况」,Ω 也不是「最好情况」。

✓ 第一周:对不对·怎么数　✓ Big-O:定义·实战·工具箱　▶ 配齐尺子:Ω 与 Θ

Ke Chen · May 21, 2026 承接 Lecture 2-2 可交互中英双语

↓ 向下滚动开始 · scroll to begin

一把只会说「≤」的尺子 / Big-O only speaks upper bounds

教授开场:「这个视频我们要介绍渐近记号家族的另外两位成员(two more members of this asymptotic notation family)——Big-Omega 和 Big-Theta。」在见新人之前,先回味一下老熟人 Big-O 的一个小尴尬。

回忆整条线:1-2 里我们推出 LinearSearch 最坏情况的运行时间是 an + b(a、b 是两个不知道具体值的常数);1-3 有了 Big-O,就能干脆地说——它的最坏情况时间复杂度是 O(n)。

但注意:O 说的是上界 (upper bound)。上界之上,皆是上界。所以下面这些话全部合法:LinearSearch 是 O(n²);是 O(n¹⁰⁰);是 O(2ⁿ·n!)——教授原话:「or some even crazier functions(或者一些更疯的函数)」。

互动 · 上界超市:给 LinearSearch 挑一个 O

真实增长率是线性 (an+b)。点一个候选上界,看它「合法吗」和「有用吗」是两回事:

O(log n) O(n) O(n²) O(n¹⁰⁰) O(2ⁿ·n!)

信息量 · how much it tells you about the true behavior

讲义原则:永远追求最低可能上界 · lowest possible upper bound 「这些说法都合法 (valid),但我们总是选择最低可能上界,因为它给出最准确的分析。」教授对 O(n¹⁰⁰) 的评语值得背下来:「It is correct upper bound, it's just too far away. It's not accurate.」——合法性和信息量是两回事,松掉的上界不撒谎,只是什么都没说。

转折 · 你应该觉得哪里不对劲教授:「I'm sure it felt weird that we have upper bounds…there got to be lower bounds as well. And you would be correct to guess that.」(只有上界,你肯定觉得怪——理应有下界。你猜对了。)有「≤」就该有「≥」:下界的记号,叫 Ω(Big-Omega)。

Ω:把不等号翻个面 / Big-Omega describes lower bounds

教授把两个定义并排放在一起,然后说:「所有的改动都在那个蓝框里 (everything changed is inside that blue box)——我们把不等式的方向翻转了。」除此之外,一个字都没变。

定义 · Big-O(1-3 的老朋友)

对 f, g : ℕ → ℝ⁺,若存在 c > 0 和 n₀ ∈ ℕ,使得 f(n) ≤ c·g(n) 对所有 n ≥ n₀ 成立,则记 f(n) = O(g(n))。

定义 · Big-Omega(新成员)

对 f, g : ℕ → ℝ⁺,若存在 c > 0 和 n₀ ∈ ℕ,使得 f(n) ≥ c·g(n) 对所有 n ≥ n₀ 成立,则记 f(n) = Ω(g(n))。

两个量词原封不动:∃(紫)还是「找一张证书就赢」,∀(黄)还是「门槛之后步步成立」。唯一的改动是红块里的 ≥。

f = Ω(g) 的三种读法(和幻灯片逐条对应):

渐近地,f(n) 的增长不慢于 (no slower than) g(n)。
按增长率讲,f(n) ≥ g(n)。
按增长率讲,g(n) 是 f(n) 的一个下界 (lower bound)。

一句话:Ω 是 O 的正对面(directly the opposite)。O 说「≤」,Ω 说「≥」;O 给上界,Ω 给下界。c 和 n₀ 的两大特权也原样保留:c 吃掉常数倍,n₀ 跳过小 n。

立刻用一次。LinearSearch 最坏情况 T(n) = an + b(a, b > 0),它 = Ω(n) 吗?

an + b ≥ a·n,对所有 n ≥ 1　→　证书 (c, n₀) = (a, 1)　→　T(n) = Ω(n) ∎

于是最坏情况的 LinearSearch 同时有 O(n) 和 Ω(n)——上界和下界咬在同一档上。这个「咬合」正是 §07 的主角。另,1-3 的提醒继续有效:这里的「=」是记号滥用,真身是集合成员(f ∈ Ω(g)),只能从左往右读。

Ω 练手场:紫线趴下去 / The Ω playground

还记得 1-3 的 Big-O 练手场吗?那里你调 c 和 n₀,要让紫线 c·g(n) 压在蓝线上方。现在整个世界镜像翻转:要证 Ω,紫线必须从 n₀ 起永远趴在蓝线下面。

互动 · Ω 练手场:调出一张有效的下界证书

3n+1 = Ω(n)? 0.01n² = Ω(n)?(2-1 的老对手) n = Ω(n²)?(注定失败)

f(n)(要被托住的函数)c·g(n)(你的下界,必须趴下)n ≥ n₀ 生效区

c =2

n₀ =1

练手场教你的三件事 ① c 往小调是安全方向——Ω 里 c 的职责是「把 g 压矮」,正对着 O 里「把 g 抬高」;② n₀ 还是用来跳过小 n——0.01n² 在 n < 100 时确实托不住 n,但 Ω 允许你把门槛挪到 100 再开赛;③ 方向错了谁也救不了——n 想给 n² 当下界,c 再小、n₀ 再大都注定翻车,这就是「不存在证书」。

头号误解:界不是情况 / Bounds are not cases

幻灯片专门画了个大红叉:「O 描述最坏情况,Ω 描述最好情况」。教授:「And that's absolutely not right.」这可能是渐近记号最流行的谣言——这一节把它彻底埋掉。

分清两件完全不同的事:

O 和 Ω 是「界」:给某一条函数标上界、下界——它们回答「这条曲线增长多快」。
最好/最坏/平均是「情况」:决定你在谈论哪一条函数(教授:「Best case and worst case describe which running time function we are talking about.」)。

先选情况,得到一条确定的函数;再对这条函数,想标上界就 O、想标下界就 Ω。教授的结论:「They are independent, orthogonal choices. You can just mix any of them.」(独立、正交,随便混搭。)用 LinearSearch 亲手把六种搭配摸一遍:

互动 · 情况 × 界:六格混搭台(LinearSearch)

① 选情况: 最坏 T(n)=an+b 最好 T(n)=常数平均 T(n)≈a·n/2

② 选界: 上界 O 下界 Ω

那为什么谣言这么像真的? 因为课上确实最常对「最坏情况」使用 O——教授也说:「Usually in this course, we're mostly talking about the worst-case time complexity.」高频搭配 ≠ 绑定关系:对最坏情况你照样可以谈 Ω(本课 §02 刚做过),对最好情况也照样可以谈 O。2×3 = 6 格,格格合法。

Ω 实战:四连判 / True or false, with Ω

幻灯片给了四道判断题。动手之前,教授先送了个大礼包:「因为 O 和 Ω 的定义如此相似,你完全可以猜到:上个视频学的九条性质,对 Ω 同样全部成立(all the nine properties … are also true for big omega)。」判断心法照旧:比两边的增长率,多项式看首项。

教授:「We'll leave some of them as an exercise in our first homework.」——Ω 版性质会出现在第一次作业里;§10 挑战题 C1 先带你把「加法合并」的 Ω 版证一遍。

① 3n + 1 = Ω(n)

真。3n + 1 ≥ 1·n 对所有 n ≥ 1(左边连 3n 都不止)。证书 (c, n₀) = (1, 1);取 (3, 1) 也行——Ω 证书同样不唯一,交出任何一张有效的就赢。

② 0.01n² = Ω(n)

真。0.01n² ≥ 1·n ⟺ 0.01n ≥ 1 ⟺ n ≥ 100 → 证书 (1, 100)。品一品这个回旋镖:2-1 我们用对抗游戏郑重其事地证明了 0.01n² ≠ O(n);同一对函数,换成 Ω 一次通过——增长快于 n 的函数当不了 n 的上界,却天生是 n 的下界。0.01 这种小系数只能把 n₀ 推远(到 100),推不翻方向。

③ 22n = Ω(2n)

真。22n = (2²)ⁿ = 4ⁿ = 2ⁿ·2ⁿ ≥ 1·2ⁿ(因为 2ⁿ ≥ 1)→ 证书 (1, 1)。但反方向呢?22n = O(2ⁿ) 要求 4ⁿ ≤ c·2ⁿ ⟺ 2ⁿ ≤ c——n > log₂c 就翻车(2-1 的老朋友:指数底数不可换)。只 Ω、不 O:这种「单边关系」§08 会专门分类。

④ n⁵ + 1888n³ + n·log n = Ω(n⁶)

假——幻灯片上唯一的 FALSE。教授的推理:「多项式函数特别简单,取首项 (leading term),它碾压其余所有项。」左边首项 n⁵,右边 n⁶;n⁵ 增长慢于 n⁶,所以左边当不了 n⁶ 的下界:n⁵ 是 O(n⁶),不是 Ω(n⁶)。

严格反证(2-1 的量词翻转 + 对抗游戏) · Write-up

量词翻转要证「不存在证书」:对任意 (c, n₀),都能找到一个 n ≥ n₀ 使 n⁵ + 1888n³ + n·log n < c·n⁶。

先驯服左边 n ≥ 44 时 n² ≥ 1936 ≥ 1888,故 1888n³ ≤ n⁵;又 log n ≤ n(1-3 基本事实)给 n·log n ≤ n² ≤ n⁵。于是左边 ≤ 3n⁵,对所有 n ≥ 44。

逼出矛盾若左边 ≥ c·n⁶,则 3n⁵ ≥ c·n⁶,两边除以 n⁵:3 ≥ c·n,即 n ≤ 3/c——只有有限个 n 满足!

对抗一击对手无论交出什么 (c, n₀),我方取 n* = max{n₀, 44, ⌊3/c⌋+1}:此处左边 ≤ 3n*⁵ < c·n*⁶。不等式在 n* 处失败,证书作废。∎

教授紧接着反手一句,埋下下一节的种子:「Actually, it's quite the opposite——n⁶ is Ω(n⁵).」(其实恰好反过来:n⁶ 是 n⁵ 的下界。)

战绩:0 / 0　

对偶:O 和 Ω 是同一句话的两面 / Duality: f = O(g) ⟺ g = Ω(f)

刚才那句「其实恰好反过来」不是巧合,是定理:f 被 g 从上面压住,恰好等于 g 被 f 从下面托住。每一条 Big-O 知识,免费附赠一条 Ω 知识。

f(n) ≤ c·g(n)　⟺　g(n) ≥ 1c·f(n)　　(两边同除 c > 0,方向不变)
证书变换:(c, n₀) ⟶ 镜像 ⟶ (1/c, n₀)

完整的双向证明(以及它送出的 Θ 对称性)在挑战题 C2 等你。

互动 · 镜像机:把前几课的 O 定理免费翻成 Ω 定理

2-1 例一:3n+5 = O(n−3) 2-1 例二:2ⁿ⁺¹ = O(2ⁿ) §05 刚证:n⁵ = O(n⁶)

对偶给你的实战外挂以后遇到「证明 g = Ω(f)」,先问一句:f = O(g) 我是不是早就会证?会,就把证书除个 c 交上去。反过来也一样。O 的整套肌肉——定义拆包、证书、九条性质——Ω 全部白拿,连难度都不变,只是照了个镜子。

Θ:当上界和下界咬合 / Theta describes tight bounds

教授:「It's tempting to ask what happens if I have a matching bound——如果上界和下界在同一档相遇,会怎样?」答案是家族第三位成员:Θ。

定义 · Big-Theta(幻灯片原文)

注意到 f(n) 可以同时满足 f(n) = O(g(n)) 和 f(n) = Ω(g(n))。此时我们记 f(n) = Θ(g(n))。

f = Θ(g) 的读法:f 和 g 渐近同阶 (asymptotically of the same order)——「they grow similarly」,增长率意义上的「=」。至此刻度配齐:O 是 ≤,Ω 是 ≥,Θ 是 =。

把定义展开,就是一副「三明治」:两张证书合成一张。

推导:两张证书 → 一张三明治证书 · Write-up

拆包 O f = O(g):存在 c₂, n₀ 使 f(n) ≤ c₂·g(n),对 n ≥ n₀。

拆包 Ω f = Ω(g):存在 c₁, n₀′ 使 f(n) ≥ c₁·g(n),对 n ≥ n₀′。

拼装当 n ≥ max{n₀, n₀′},两条同时生效:c₁·g(n) ≤ f(n) ≤ c₂·g(n)——f 被 g 的两个常数倍夹在中间。这一手「取 max 让两张证书同时生效」正是 2-2 拆包机的老动作。

打包 Θ 证书是三元组 (c₁, c₂, n₀″),n₀″ = max{n₀, n₀′}。反方向显然:有了三明治,拆开就是一张 O 证书加一张 Ω 证书。∎

互动 · 三明治机:亲手把 n²+10n 夹成 Θ(n²)

蓝线 f(n) = n²+10n。调三个旋钮,让黄线 c₁·n² 从 n₀ 起趴在蓝线下面、紫线 c₂·n² 压在蓝线上面——同时做到,就是一张 Θ 证书:

f(n) = n²+10nc₁·n²(下片面包)c₂·n²(上片面包)

c₁ =1

c₂ =2

n₀ =5

试试:c₂ = 2 时 n₀ 要挪到多大?(上界条件 10n ≤ (c₂−1)n² ⟺ n ≥ 10/(c₂−1)。)再试试把 c₁ 抬过 1——为什么无论 n₀ 多大都救不回来?

「最低可能上界」的正式说法,拿到了 §01 说好的上界要「最低可能」,当时只能凭感觉;现在有了检验器:当你的 O 和你的 Ω 咬在同一个 g 上(即 f = Θ(g)),上界就不可能再压低了——再低就会戳破下界。分析一个算法的终极目标,就是给它的(最坏情况)时间复杂度找到 Θ。

三路分类赛:O、Ω,还是 Θ? / The three-way classifier

幻灯片的六道 Θ 判断题,升级成三路分类:对每对 (f, g),f 究竟是 g 的同阶(Θ)、严格更慢(只 O 不 Ω),还是严格更快(只 Ω 不 O)?心法照旧——「we're basically considering the growth rate of the two functions」:比增长率,多项式看首项,log 把系数和幂次全拍扁。

① f = (n+10)³　vs　g = n³

Θ。上界用 2-1 的膨胀技:n ≥ 1 时 10 ≤ 10n,故 (n+10)³ ≤ (11n)³ = 1331n³;下界白拿:(n+10)³ ≥ n³。三明治证书 (c₁, c₂, n₀) = (1, 1331, 1)。2-1 只证到了 O,今天补上另一半——加 10 再立方,档次纹丝不动。

② f = log(√n)　vs　g = log n

Θ。根号先变身:√n = n1/2,于是 log(√n) = ½·log n——精确等于一半。乘法位上的常数 ½,增长率纹丝不动(P1 的精神)。三明治证书 (½, ½, 1),两片面包重合成一片。

③ f = log(99n³)　vs　g = log n

Θ。log 把乘法变加法、把幂变系数:log(99n³) = log 99 + 3·log n。下界:log 99 > 0,所以 ≥ 3·log n ≥ 1·log n(n ≥ 1);上界:n ≥ 2 时 log n ≥ 1,故 log 99 + 3·log n ≤ (log₂99 + 3)·log n < 10·log n(log₂99 ≈ 6.63)。三明治证书 (1, 10, 2)。系数 99、幂次 3,进了 log 全成浮云。

④ f = n⁵ + 1888n³ + n·log n　vs　g = n⁵

Θ。下界白拿:三项全非负,f ≥ n⁵,c₁ = 1;上界:1888n³ ≤ 1888n⁵,n·log n ≤ n² ≤ n⁵(n ≥ 1),故 f ≤ 1890·n⁵。三明治证书 (1, 1890, 1)。「多项式看首项」对 Θ 同样成立——首项既是它的上界担当,也是它的下界担当。

⑤ f = n⁵ + 1888n³ + n·log n　vs　g = n⁶

只 O——幻灯片上唯一的 FALSE(Θ 版)。O 成立:f ≤ 1890n⁵ ≤ 1890n⁶;Ω 不成立:§05 第④题刚用对抗游戏拆过。教授点破两题的联系:「exactly the one we marked on previous slide for big omega」——Θ 要两个方向都过,Ω 那关没过,Θ 立刻连坐。上界故意松一档仍然合法,但「合法的松上界」永远换不来 Θ。

⑥ f = 5n·log n + 1000n − 6　vs　g = n·log n

Θ。先安检那个 −6:定义要求 f : ℕ → ℝ⁺,而 n = 1 时 f = 5·0 + 1000 − 6 = 994 > 0,合格。下界:1000n − 6 > 0(n ≥ 1),所以 f ≥ 5·n·log n,c₁ = 5;上界:n ≥ 2 时 log n ≥ 1,故 1000n ≤ 1000·n·log n,于是 f ≤ 5n·log n + 1000n·log n = 1005·n·log n(丢掉 −6 只会更小)。三明治证书 (5, 1005, 2)。那个 −6 纯属吓唬人——被非负性检查和 n₀ 轻松化解。n·log n 这位排序界常客,2-2 靠 P9 拼出过它,以后天天见。

⑦(回收 §05)f = 22n　vs　g = 2n

只 Ω。Ω:4ⁿ ≥ 2ⁿ,证书 (1, 1);O:4ⁿ ≤ c·2ⁿ ⟺ 2ⁿ ≤ c,在 n > log₂c 处翻车——指数底数不可换(2-1)。和第⑤题互为镜像:⑤是「太慢,当不了下界」,⑦是「太快,当不了上界」;两边各断一条,Θ 都不成立。

战绩:0 / 0　

全家福 + 本课陷阱 / The family portrait & pitfalls

三位成员到齐,拍一张全家福;再把这节课挖出的坑逐个钉上警示牌。

记号	增长率读法	定义里的不等式	角色	方向
f = O(g)	f ⪯ g(不快于)	f(n) ≤ c·g(n)	g 是上界	单向
f = Ω(g)	f ⪰ g(不慢于)	f(n) ≥ c·g(n)	g 是下界	单向
f = Θ(g)	f ≍ g(同阶)	c₁·g(n) ≤ f(n) ≤ c₂·g(n)	g 是紧界 (tight bound)	对称(C2 证)

工具迁移清单:2-2 的九条性质,O 版已证;Ω 版全部成立(教授明说,部分留作第一次作业——C1 练一条);Θ 版由「O 版 + Ω 版」逐条拼合即可得(推论,课上未逐条展开),最实用的三条:

多项式看首项,对 Θ 成立:adnd + … + a₀ = Θ(nd)(ad > 0)——§08 第④题就是实例。
乘法常数照丢:a·f = Θ(f)。所以 0.01n² = Θ(100n²)——同阶不等于跑得一样快,只是增长节奏相同。
严格分档处 Θ 必断:log ≺ 多项式 ≺ 指数(P5/P7 的分界线),跨界只有单边的 O 或 Ω,没有 Θ。1-3 的增长阶梯,现在可以正式读成「每一级是一个 Θ 等价档」。

本课四个坑 · Pitfalls

界 ≠ 情况(幻灯片亲自打叉)

"O 管最坏,Ω 管最好" ✗

O/Ω 给一条函数标上下界;最好/最坏挑哪条函数。正交的两轴,六格全合法——最好情况有 O,最坏情况有 Ω(§04 的六格你都点亮了吗)。

Ω 也要追求「最高可能下界」

"T = Ω(1),我证完了" ✗

合法,但空话——任何正函数都是 Ω(1)。镜像 §01:上界求最低,下界求最高,两头相遇即 Θ,分析才算到位。

「=」依旧是单行道,但 Θ 例外

"f = O(g) 所以 g = O(f)" ✗

O/Ω 都是单向的:f = O(g) 换来的是 g = Ω(f)(对偶,方向翻转),不是 g = O(f)。唯独 Θ 真正对称:f = Θ(g) ⟺ g = Θ(f)。

不是 Θ ≠ 没有关系

"n⁵ 和 n⁶ 不同阶,所以什么都说不了" ✗

n⁵ = O(n⁶)、n⁶ = Ω(n⁵) 都成立——慢的当上界素材、快的当下界素材,单边关系照样有用。真正「谁也压不住谁」的野生函数对也存在(C4 造一对)。

挑战题:作业预演 + 思维扩展 / Harder problems

四道,难度递增。C1 正对教授那句「Ω 版性质留作第一次作业」;C2 把 §06 的对偶定理补成完整证明。先动笔再看解。

★★ · 作业预演:Ω 版加法合并

C1. 证明性质 P3 的 Ω 版:若 f = Ω(h) 且 g = Ω(h),则 f + g = Ω(h)。

提示:照搬 2-2 的拆包机?可以。但 Ω 版其实有一条更懒的路——想想「加上一个非负的东西」会让左边变大还是变小。

题解 · Solution

拆包① f = Ω(h):存在 c, n₀ 使 f(n) ≥ c·h(n),对 n ≥ n₀。

白捡一步 g : ℕ → ℝ⁺,故 g(n) ≥ 0 处处成立——另一条已知甚至不用拆。

拼装 n ≥ n₀ 时:f(n) + g(n) ≥ f(n) ≥ c·h(n)。

打包证书原封不动:(c, n₀)。∎

品一品 O 版(2-2 的 P3)必须拆两张证书、常数相加、门槛取 max;Ω 版一张就够——因为往下界上再堆东西只会更稳。非负性又一次悄悄干活。当然,对称地给出 (c+c′, max{n₀, n₀′}) 的「豪华版」也全对。

★★★ · 对偶定理(§06 的欠账)

C2. 证明:f = O(g) ⟺ g = Ω(f)。并由此推出 Θ 的对称性:f = Θ(g) ⟺ g = Θ(f)。

提示:整场证明只有一个动作——在不等式两边同除一个正常数。证书怎么变换,§06 已经剧透了。

题解 · Solution

⇒ 方向 f = O(g):存在 c, n₀ 使 f(n) ≤ c·g(n),对 n ≥ n₀。因 c > 0,两边同除 c 保序:g(n) ≥ (1/c)·f(n),对同样的 n ≥ n₀。证书 (1/c, n₀) 有效,故 g = Ω(f)。

⇐ 方向 g = Ω(f):存在 c′, n₀′ 使 g(n) ≥ c′·f(n),对 n ≥ n₀′。同除 c′ > 0:f(n) ≤ (1/c′)·g(n)。证书 (1/c′, n₀′),故 f = O(g)。∎

推论:Θ 对称 f = Θ(g) ⟹ f = O(g) 且 f = Ω(g) ⟹(两次对偶)g = Ω(f) 且 g = O(f) ⟹ g = Θ(f)。反向同理。∎

品一品 O 和 Ω 不是两套理论,是一条不等式的两种念法;Θ 因此天生对称——「同阶」才配得上「=」的读法。顺带验证 §06 镜像机:3n+5 ≤ 4(n−3)(n ≥ 17)除以 4,就是 n−3 ≥ ¼(3n+5)。

★★★ · 吸收律:幻灯片例④的幕后定理

C3. 设 f = O(g)。证明 f + g = Θ(g)。

提示:上界方向拆包一次就够;下界方向连拆包都不用(想想 C1 的「白捡一步」)。证完回头看幻灯片的 n⁵ + 1888n³ + n·log n = Θ(n⁵),它是谁的实例?

题解 · Solution

上界拆包 f = O(g):f(n) ≤ c·g(n),对 n ≥ n₀。于是 f(n) + g(n) ≤ c·g(n) + g(n) = (c+1)·g(n)。O 证书 (c+1, n₀)。

下界 f(n) ≥ 0,故 f(n) + g(n) ≥ g(n) = 1·g(n),对所有 n ≥ 1。Ω 证书 (1, 1)。

合体上界 + 下界 = Θ:f + g = Θ(g),三明治证书 (1, c+1, n₀)。∎

品一品这就是吸收律:把「不超过 g 档」的项加进 g,档次纹丝不动。幻灯片例④正是实例——取 g = n⁵,f = 1888n³ + n·log n(P2/P5/P9 给出 f = O(n⁵)),一句 C3 直接收工。以后见到长和式:找最重的项当 g,其余整包当 f。

★★★★ · 思维扩展:增长率不是全序

C4. 判断真假:对任意 f, g : ℕ → ℝ⁺,f = O(g) 与 f = Ω(g) 至少有一个成立。(也就是:任何两个函数的增长率总能比出「≤」或「≥」吗?)

提示:§08 里全是乖巧的多项式/对数/指数,它们确实两两可比。想造反例,得让 f 和 g 来回振荡、轮流领先——试试按 n 的奇偶分段定义。判「不成立」用什么武器?2-1 的量词翻转,两次。

题解 · Solution

判假。存在谁也压不住谁的函数对。

构造对 n ≥ 1:f(n) = n(n 为偶数)、f(n) = 1(n 为奇数);g 反过来:g(n) = 1(偶)、g(n) = n(奇)。两个函数处处为正,合法。(若你的 ℕ 含 0,把 0 处补成 1 即可——有限个点改不动渐近行为。)

拆 f = O(g) 量词翻转:对任意 (c, n₀),取偶数 n* > max{n₀, c}:f(n*) = n* > c = c·1 = c·g(n*)。不等式失败,任何证书作废。

拆 f = Ω(g) 对任意 (c, n₀),取奇数 n* > max{n₀, 1/c}:f(n*) = 1 < c·n* = c·g(n*)。失败,作废。∎

品一品于是两个函数之间共有四种可能:Θ(同阶)、只 O(严格更慢)、只 Ω(严格更快)、不可比。§08 的三路分类赛之所以够用,是因为算法分析里常见的函数(多项式、对数、指数及其组合)恰好两两可比;野生函数可以靠振荡逃出排序。(本课未详述,思维扩展——但每一步武器都是已学的。)

随堂小测 / Quick Check

无限次尝试,零压力。七道题,把三把尺子和那个大红叉各敲一遍。

Q1. f(n) = Ω(g(n)) 的定义是:存在 c > 0 和 n₀ ∈ ℕ,使得——

Q2. 「Big-O 描述最坏情况,Big-Omega 描述最好情况」——这个说法?

Q3. 0.01n² = Ω(n) 这个命题?

Q4. 「LinearSearch 最坏情况时间复杂度是 O(n¹⁰⁰)」——这句话?

Q5. n⁵ + 1888n³ + n·log n = Θ(n⁶) 这个命题?

Q6. f = O(g) 恒等价于下面哪句话?

Q7. 下面哪个是真命题?