上一课我们把 LinearSearch 数成了 T(n) = an + b。可那个 a、那个 b 到底是多少,我们既不知道、也不关心。这一课要造一把"尺子",把无关紧要的常数一刀切掉,只留下真正决定命运的东西——增长率 (growth rate)。这把尺子就是 Big-O。
上一课的结论是:放弃绝对速度,改看可扩展性 (scalability)。可"可扩展性"听着抽象,这里给你一个特别具体的抓手——
把常见的几种 T(n) 都代进去算一遍。点表格任意一行,右边会放大讲解:
| 档次 Class | T(n) | T(10n) | 放大倍数 |
|---|---|---|---|
| 常数 constant | 42 | 42 | 1× (不变) |
| 线性 linear | 15n | 150n | 10× |
| 二次 quadratic | 0.3n2 | 30n2 | 100× |
| 三次 cubic | 82n3 | 82000n3 | 1000× |
| 指数 exponential | 1.5n | 1.510n ≈ 58n | 爆炸 💥 |
看规律:线性→10×、二次→100×、三次→1000×,而指数根本不服从"乘个固定倍数"的规矩——它是灾难级的。这就是为什么我们拼命想避开指数算法。
LinearSearch 的 T(n) = an + b 看着就是线性,理应落在"10×"那一档。可你真去代 10n,会发现它不精确。
差在那个 b vs 10b。只要 b ≠ 0,T(10n) 就不等于 10·T(n)。拿具体数字看更扎心——设 a = 10ms、b = 7ms(还是老规矩,瞎编的常数):
别看某一个 n 的"精确倍数",看 n 趋于无穷时那个倍数逼近什么。这一步就是"渐近 (asymptotic)"的全部含义。
为什么极限是 10?分子分母同除 n:(10a + b/n) / (a + b/n),当 n→∞ 时 b/n → 0,剩下 10a / a = 10。那个碍事的 b 被无穷大"稀释"掉了。
T(n) = an + b。逐行加大 n,看比值 T(10n)/T(n) 怎么爬向 10。换个夸张的 b 试试——极限照样是 10:
| n | T(n) | T(10n) | T(10n)/T(n) |
|---|
"渐近"还带来一个解放:小 n 处的胜负无所谓。哪怕线性函数在起点领先,只要增长率更低,迟早会被超过。亲眼看看这场赛跑。
前面所有直觉,浓缩成两句话。Big-O 的定义就是为了同时兑现这两句话而造的。
难点在于:怎么用一个数学上严格的定义,把"无视常数"和"无视小 n"这两件事同时说清楚?答案是——各配一个可以自由挑选的常数。往下看。
第一次读会觉得抽象——别急,我们把它拆成零件,再各配一个例子。
读法:f(n) = O(g(n)) 直觉上就是"f 的增长率不超过 g"(g 是 f 的一个上界档次)。注意这里的 "=" 是记号滥用——严格说应是 f ∈ O(g),O(g) 是"所有增长不快于 g 的函数"组成的一整个集合。这个坑第 9 节还会再提。
最能体现 c 作用的例子:证明 15n = O(n)。凭直觉它俩都是线性、显然同档;但没有 c 你根本写不出那个不等式。
目标:找 c, n₀ 使 15n ≤ c · n 对所有 n ≥ n₀ 成立。若不许用 c(即 c=1),15n ≤ n 永远不成立。但 c 可以随便挑——挑 c = 20:
拖动 c 和 n₀。蓝线是 f(n)=15n,紫线是 c·g(n)=c·n。目标:让紫线在阴影区(n ≥ n₀)里始终压住蓝线。
这个例子专门凸显 n₀。证明 n = O(n² − 100)。麻烦在于那个 −100 会让小 n 处彻底翻车。
目标:找 c, n₀ 使 n ≤ c·(n² − 100) 对所有 n ≥ n₀ 成立。看小 n:当 n ≤ 10 时,n² − 100 ≤ 0(比如 n=1 时是 −99),右边是负数或零,而左边 n 是正数——不等式彻底反了,无论 c 取多大都救不了。
怎么办?别管小 n,把门槛往后挪。取 n₀ = 11、c = 1:此时 n² − 100 已经稳稳超过 n(例如 n=11:121−100=21 > 11)。于是:
蓝线 f(n)=n,紫线 c·g(n)=c·(n²−100)。注意紫线在左边会钻到 0 以下——那正是小 n 翻车的地方。你的任务:把 n₀ 挪到翻车区右边。
把两个例子的套路固化下来,以后遇到"证 f = O(g)"照做即可。
比较 f 和 g 的最高次项系数,挑一个足够大的 c 把 f 的系数罩住。(例一里 15 → 挑 c=20)
找出低次项/负常数会捣乱的小 n 范围,把 n₀ 设在这个范围之后。(例二里 −100 到 n=10 都在捣乱 → 挑 n₀=11)
写出对所有 n ≥ n₀ 都有 f(n) ≤ c·g(n) 的推导。给得出一组能用的 (c, n₀) 就算证完。
Big-O 只说"不快于"。所以线性函数也是 O(n²)、O(n³)——只是不够紧 (tight)。要说"恰好同档",那是 Θ 记号,以后再讲。
f = O(g) 真正的意思是 f ∈ O(g)(集合成员)。所以能写 15n = O(n),但不能反过来写 O(n) = 15n。
渐近只看最高次项、且丢掉它的系数。8n²、0.3n²、1000n² 全是 O(n²)。
多项式里系数可丢,但指数的底数不能丢——2ⁿ 和 3ⁿ 不是一个量级。log 的底数倒是可丢(换底只差常数)。
从慢到快排好队。本课出现了常数、线性、二次、三次、指数;log 类这几课还没细讲,先混个脸熟,知道它们卡在哪就行。
无限次尝试。这套题专挑定义里最容易栽的点。