第 4 章分析算法 — 比较大 O 这把尺子¶

这一章讲什么: 怎么客观地说「这个算法比那个算法好」——答案是渐进记号, 全书只用其中一个大 O。它在全书链条里的位置:尺子章。第 3 章说了「同一 ADT 可以多种实现」,自然逼出「那怎么比」的问题;本章给尺子, 从第 5 章起每次说「快/慢」都是拿它量的。

1. 顶层全景¶

  问题:同一个 ADT 有好几个实现,怎么比?
    │
    ├─ 比什么:时间为主(空间通常随输入线性增长,没得挑)
    │
    ├─ 用什么比:渐进记号( input 规模 n 趋大时的增长阶 )
    │    └─ 五种记号 O / o / Θ / Ω / ω,全书用 O = 上界
    │
    ├─ 哪个口径:最好 / 最坏 / 平均 / 摊还(默认最坏)
    │
    └─ 换来的代价:时间 ↔ 空间可以置换(预计算换查询)

  图说:一章四问——比什么、用什么、哪个口径、换不换。答完就能量任何一个算法。

2. 主线例子:区间求和,两个版本的完整对照¶

这一章主线例子选书末「时间与空间置换」那节,因为它把全章概念一次用全: 有个长数字数组,要频繁求任意区间 [from, to] 的元素和¹。

版本 A(直接求和): 每次调用从头加到尾:

const sumRange = (arr, from, to) => {
  let sum = 0;
  for (let i = from; i <= to; i++) { sum += arr[i]; }
  return sum;
};

额外内存 O(1)(只要一个 sum 变量),但每次查询 O(长度)。假如数组有 10,000 个数、区间平均 5,000 个元素、查 1,000 次: 总工作量约 500 万次加法(这些数是为演示编的,不是真实数值)。

版本 B(预计算前缀和): 先花一次 O(n) 造一张「前 q 项和」表:

const precomputeSums = (arr) => {
  let partial = Array(arr.length);
  partial[0] = arr[0];
  for (let i = 1; i < arr.length; i++) { partial[i] = partial[i - 1] + arr[i]; }
};

之后任何区间和都是两次查表一次减法:

const sumRange2 = (partial, from, to) =>
  from === 0 ? partial[to] : partial[to] - partial[from - 1];

走一遍具体数(演示用数组 [22, 9, 60, 12, 4, 56]): partial 表 = [22, 31, 91, 103, 107, 163]。问 sumRange2(partial, 1, 3)(即 9+60+12):partial[3] - partial[0] = 103 − 22 = 81 ✓。问 sumRange2(partial, 0, 2):partial[2] = 91 ✓。同样的 1,000 次查询:预计算 1 万次加法 + 每次查询 1 次减法 ≈ 1.1 万次, 对 500 万次——两个数量级的差距,代价是一张等长的数组(O(n) 空间)²。

这个例子的结论就是全章的落脚点:用更多内存换更快的算法,还是省内存接受更慢, 取决于问题、取决于现在的性能能不能接受、甚至取决于内存够不够³。版本 B 的手法叫制表(tabulation),是第 5 章动态规划思想的第一次亮相。

3. 核心原理¶

3.1 渐进记号:描述「n 变大时怎么长」¶

算法分析不关心一次跑多快,关心输入规模 n 变大时耗时怎么长。记号一族五种,全书只用大 O(O 来自德语 Ordnung,「阶」)⁴:

记号	名字	意思
f(n) = o(g(n))	小 o	g 长得严格比 f 快
f(n) = O(g(n))	大 O	g 是 f 的上界(g 长得一样快或更快)
f(n) = Θ(g(n))	大 Θ	g 既是上界也是下界——两者同速
f(n) = Ω(g(n))	大 Ω	g 是 f 的下界
f(n) = ω(g(n))	小 ω	g 长得严格比 f 慢

为什么日常只说 O?因为精确表达式常常推不出来(书里坦白:有些算法的精确阶至今未知),而且 O 这个「上界」只要选得贴近原函数,就够用来比较⁵。书里还有个贴心的比喻:欠债欠几美元还是欠几百万,不用精确数字也知道哪种情况好。

一个有用的粗解读:O ≈ 最坏情况的上界,Ω ≈ 最好情况的下界,Θ ≈ 两头同速即性能稳定;小 o、小 ω 是「差得更远的界」,只用于粗略估计⁶。 Knuth 曾建议大 O 该用大 omicron(长得一样的另一个希腊字母)——没成⁷。

3.2 七个复杂度阶:从乖巧到不可用¶

常见的阶就七个,书里给了一张对照表(括号是书中给的例子)⁸:

阶	名字	输入放大 10 倍时	书中例子
O(1)	常数	时间不变	取链表首元素、弹栈顶(第 10 章)
O(log n)	对数	只多一个固定量	二分搜索(第 9 章)、BST 平均高度(第 12 章)
O(n)	线性	时间 ×10	无序数组搜索、中序遍历(第 12 章)
O(n log n)	对数线性	介于 ×10 和 ×100 之间,更接近 ×10	堆排序、快排平均(第 6 章)
O(n²)	二次	时间 ×100	冒泡排序、快排最坏(第 6 章)
O(kⁿ)	指数	翻 k 倍类地爆炸	二元公式重言式判定(k=2)、朴素斐波那契(k≈1.618)
O(n!)	阶乘	爆炸到不可用	旅行商最优解、随机排列排序(第 6 章)

两个要点。第一,「输入放大 10 倍」是量阶的直觉标尺⁹: O(n²) 在 n=10 时就是 100,图都画不下;后两阶「现实中不会用,长得太快」¹⁰。第二,常数倍无意义:O(n)、O(9n)、O(22n) 是同一类,n 够大时 O(n²) 永远超过它们的任何常数倍——这就是丢弃系数的理由,也是大 O 比较成立的基础¹¹。

3.3 四种口径:最好、最坏、平均、摊还¶

最好情况:理想输入下的表现(搜索第一个就中)。只是比较的基线(参照起点),不能当真¹²。
最坏情况:最慢的可能。默认口径——「总要假设它会发生,这是最安全(也最悲观)的分析」。
平均情况:典型/随机输入下的期望(各种可能性的平均结果)。第 6 章会看到快排平均 O(n log n) 尽管有坏输入。
摊还:一连串操作里的单次平均——个别操作很慢,但慢操作稀稀拉拉, 摊到长跑里单次成本可能远低于最坏情况¹³。

摊还的经典演示书里给了:往定长数组加元素,满了就复制到两倍大的新数组。单看那次翻倍是 O(n);但翻倍一次之后,n 次添加都是 O(1) 直写, 一串操作平均下来摊还 O(1)——贵操作被后面一长串便宜操作摊薄了。这正是第 10 章动态扩容数组、第 15 章惰性堆共同的会计原理。

3.4 两次完整演算:平均情况到底怎么算¶

演算一:线性搜索的平均情况。 在长度为 n 的有序数组里顺序找一个键: 最坏 O(n)(走完全程),最好 Ω(1)(第一个就中)。平均呢? 可能第 1 个命中、第 2 个命中……第 n 个命中,共 n 种等可能, 平均探测数 = (1+2+…+n)/n = [n(n+1)/2]/n = (n+1)/2 —— 与 n 成正比, 所以平均也是 O(n)¹⁴。书里还给了个不用代数的看法:第 1 个命中和第 n 个命中平均 (n+1)/2; 第 2 个和第 n−1 个平均也是 (n+1)/2;每对都如此,结论一样¹⁵。

演算二:二分搜索的平均情况(本章最硬的一段)。 在数组 [4, 9, 12, 22, 34, 56, 60] 里找 12:先看中点 22(大了),弃右半;在 [4, 9, 12] 里看中点 9(小了),弃左半; 单元素 [12] 命中¹⁶。一般地(设 n = 2ᵏ−1,保证每段都奇数长):1 个元素第 1 次命中,2 个第 2 次, 4 个第 3 次,8 个第 4 次……总比较数 S = 1×1 + 2×2 + 3×4 + … + k×2ᵏ⁻¹, 用一点微积分技巧求和(书中完整推导,注释明说可跳过证明只记结果), 平均比较数 = (k−1) + k/n,即 Θ(log n);失败的最坏情况也是 k 次,即 O(log n)¹⁷。这段推导的价值不在结果(记结论即可),在于让人看到「平均情况」是可以算出来的,不是猜的。顺带一提:之后大部分算法分析要解「递推式」, 形如 P(n)=aP(n−1)+f(n) 或 Q(n)=aQ(n/b)+f(n);后者有现成的主定理 (master theorem)可套——书里只点名,不展开¹⁸。

3.5 默认最坏:为什么本书用 O 当口径¶

把 3.3 与 3.1 接起来:O 是上界,最坏情况也是上界,所以「说一个算法是 O(f(n))」默认含意就是「最坏也就长到 f(n) 这样」。书里的原话:比较算法时按最坏情况想, 指望最好情况不现实¹⁹。这条规矩让全书所有「快/慢」的断言都有同一口径,可比。

4. 作者的判断与证据¶

「时间优先、空间随它」是经验断言:书中口径是「本书所有算法的空间复杂度都相当稳定,随输入线性增长,没有挑的余地;时间复杂度才有大差异」²⁰。这决定了全书几乎只谈时间。局限节里我们要给这个断言打半个问号。
「精确阶常常不可得」是文献事实(有算法的精确阶至今未知),用它论证「工作在阶的层面是合适的」——诚实的范围声明⁵。
数学节的自我定位极清楚:原注明说「本节比全书其他部分数学味重得多, 可以跳过证明只看结果,后面章节不会这么数学」——作者知道读者来这本书不是来上算法分析课的²¹。
十道习题是本章的另一半内容(它们「明显比全书其他习题数学化」,作者说可跳过): 答案十句话,把记号的代数性质钉死——传递性成立、自反性只到 O/Ω/Θ、 O 与 Ω 对称、首尾相接取大阶、嵌套循环阶相乘(见 5.1)。

判断(我们的,不是书里的): 本章把「大 O 至上界、默认最坏」立为全书口径是合理的教学选择,但读者要明白这是一种保守口径: 它系统性地高估了好算法的平均表现(快排是最著名的例子——平均 O(n log n) 却按 O(n²) 最坏记账)。工程上真正该问的常常是「摊还」和「平均」, 而本书恰好把摊还讲透了又用得少(直到第 15 章才回来)。 如果错,会错在: 若主人拿这本书的口径去做性能敏感的选型, 应该补一句「平均/摊还口径在 3.3 节」——不然会错过书里本来就有的更细粒度答案。

5. 边界与局限¶

空间复杂度基本被放弃:除了 3.5 的置换例子,全书不给空间分析的工具; 「空间都随 n 线性」对数组类结构成立,对哈希表、图的邻接表示等并不自动成立 (那些结构的空间形状是选型的一部分)——这是补充(不在书里,来自通用知识)。
主定理只点名:递推式求解技巧一句带过,想看证明得去别处¹⁸。
习题自陈可跳过:数学十题答案极短(一两句),适合当记号性质的速查, 不适合当练习——没有推导过程。
没有实测内容:本章全是纸面分析;「怎么真的测出一段 JS 要跑多久」 (第 1 章 performance.now() 之外)没有系统展开。

5.1 习题答案的速查价值(「Chapter 4」)¶

十题答案各一两句,合起来是一张记号性质表²²:

性质	答案的一句话
4.1 矛盾结果	宣称运行时间恰为 17n log n − 2n² + 48 不可能——n 够大时函数变负
4.2 松散界	n = O(n²) 成立,更贴切的说法是 o(n²);Ω/ω 不适用
4.3 O 且 Ω	同时成立 ⟺ f(n) = Θ(g(n)),仅当此时
4.4 传递性	O(及 Ω、Θ、o、ω)都可传递:f=O(g)、g=O(h) ⟹ f=O(h)
4.5 自反性	Θ、O、Ω 有自反性(f=Θ(f));小 o、小 ω 没有
4.6 对称性	f=O(g) ⟺ g=Ω(f);f=o(g) ⟺ g=ω(f)
4.7 顺序相接	两段先后执行,总阶 = 两者中较大的阶
4.8 循环套循环	内层 O(n²) 套在外层 O(n) 里,总阶 = 两者相乘,O(n³)
4.9 2ᵏ−1	倒推:1 ← 2×1+1=3 ← 2×3+1=7 ← …,归纳可得长为 2ᵏ−1
4.10 两头夹	最好 Ω(f) 且最坏 O(f) ⟹ 运行时间 Θ(f),仅当此时

4.7 和 4.8 是日常估算最常用的两条:先后相接取最大,内外相套取乘积。

6. 可带走的¶

大 O = 增长阶的上界;五种记号里只用 O,口径默认最坏情况。
七个阶背下来:O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(kⁿ) < O(n!); 后两个「现实中不可用」。
量阶直觉:输入放大 10 倍,O(n²) 慢 100 倍,O(log n) 只多一步。
常数倍无意义:O(n) 与 O(22n) 同类;n 够大时任何 O(n²) 都赢不了 O(n)。
四种口径:最好/最坏/平均/摊还;摊还 = 一串操作的单次平均(翻倍扩容数组是原型)。
平均情况是可以算的:线性搜索 (n+1)/2;二分搜索 Θ(log n)(推导可跳过,结论要记住)。
时间↔空间可以置换:预计算(制表)换查询速度——动态规划思想的第一次露面。
两条估算口诀:先后相接取大阶,循环相套取乘积。

7. 原文地图¶

主题	原书章	原文位置
五种记号	Performance	`text/13-fm-performance.txt:59`(搜「asymptotic notations」) · `text/13-fm-performance.txt:73`(搜「Table 4-1」)
只用 O 的理由	Performance	`text/13-fm-performance.txt:153`(搜「quite complex」)
粗解读 O/Ω/Θ	Performance	`text/13-fm-performance.txt:164`(搜「worst case」)
Knuth 注	Performance	`text/13-fm-performance.txt:161`(搜「omicron」)
七个阶	Performance	`text/13-fm-performance.txt:179`(搜「Table 4-2」)
输入放大 10 倍	Performance	`text/13-fm-performance.txt:297`(搜「10 times bigger」)
常数倍无意义	Performance	`text/13-fm-performance.txt:300`(搜「meaningless」)
四种口径	Performance	`text/13-fm-performance.txt:310`(搜「best-case」) · `text/13-fm-performance.txt:319`(搜「amortized」)
翻倍数组摊还	Performance	`text/13-fm-performance.txt:322`(搜「double-sized」) · `text/13-fm-performance.txt:350`(搜「amortized performance」)
数学节自陈可跳过	Performance	`text/13-fm-performance.txt:358`(搜「skip the demonstrations」)
线性搜索平均演算	Performance	`text/13-fm-performance.txt:371`(搜「(n + 1)/2」)
二分搜索走查	Performance	`text/13-fm-performance.txt:385`(搜「4, 9, 12」)
二分搜索平均 Θ(log n)	Performance	`text/13-fm-performance.txt:404`(搜「Whew」)
递推式与主定理	Performance	`text/13-fm-performance.txt:410`(搜「master theorem」)
区间求和两版本	Performance	`text/13-fm-performance.txt:426`(搜「sumRange」) · `text/13-fm-performance.txt:439`(搜「precomputeSums」) · `text/13-fm-performance.txt:451`(搜「trade-off」)
取决因素	Performance	`text/13-fm-performance.txt:454`(搜「acceptable」)
十道习题与一句话答案	Chapter 4	`text/67-ch04-chapter-4.txt:7`(搜「negative」) · `text/67-ch04-chapter-4.txt:43`(搜「greatest order」) · `text/67-ch04-chapter-4.txt:49`(搜「product」)

出处:「Performance」第 423 段(text/13-fm-performance.txt:423,搜「justified lines」)。原文:有「(long) array of numbers」,频繁要求求 from 到 to(含两端)的区间和;问题背景是文本断行。 ↩
出处:「Performance」第 451 段(text/13-fm-performance.txt:451,搜「trade-off」)。原文:预计算版用 O(n) 额外处理(只做一次)与 O(n) 额外内存,「提供 O(1) 的区间求和——你可以看到这种 trade-off:用更多内存换更快的算法,或省内存接受更慢的性能」。 ↩
出处:「Performance」第 454 段(text/13-fm-performance.txt:454,搜「acceptable」)。原文:「该选哪个版本?取决于问题,取决于当前性能是否可接受,甚至取决于是否有足够内存!」 ↩
出处:「Performance」第 59 段(text/13-fm-performance.txt:59,搜「asymptotic notations」)。原文:这族记号有五种;O 代表 order——更准确地说是德语 Ordnung。 ↩
出处:「Performance」第 153 段(text/13-fm-performance.txt:153,搜「quite complex」)。原文:大 Θ 比大 O 更精确,「但求得任何算法行为的精确表达式相当复杂(仍有许多算法的精确阶尚不为人知),所以工作在阶的层面是合适的」。 ↩↩
出处:「Performance」第 164 段(text/13-fm-performance.txt:164,搜「worst case」)。原文:大 O 上界可粗解读为最坏情况,大 Ω 为最好情况,大 Θ 意味着性能稳定。 ↩
出处:「Performance」第 161 段(text/13-fm-performance.txt:161,搜「omicron」)。原文注释:Knuth 曾建议大 O 应为看上去一样的大 omicron,「但没有实现」。 ↩
出处:「Performance」第 174–283 段(text/13-fm-performance.txt:179,搜「Table 4-2」)。原文给出 O(1) 到 O(n!) 七阶及书中例子;「最后两阶慢到现实中不会用,增长太快」见第 283 段(搜「way too fast」)。 ↩
出处:「Performance」第 297 段(text/13-fm-performance.txt:297,搜「10 times bigger」)。原文:输入放大 10 倍时,O(1) 不变,O(log n) 增一个固定量,O(n) 约 ×10,O(n²) 约 ×100,O(n log n) 居中且「更接近 O(n)」。 ↩
出处:「Performance」第 283 段(text/13-fm-performance.txt:283,搜「way too fast」)。原文:最后两阶「增长太快,不可用」。 ↩
出处:「Performance」第 300 段(text/13-fm-performance.txt:300,搜「meaningless」)。原文:「比较类时常数倍毫无意义:O(n²) 永远比 O(n) 长得快(也变得更大),即使给后者加上某个常数倍,n 足够大时亦然。」 ↩
出处:「Performance」第 310 段(text/13-fm-performance.txt:310,搜「best-case」)。原文:最好情况是理想条件下的行为,是基线,「但你永远不能假设总能得到这个最优性能」。 ↩
出处:「Performance」第 319 段(text/13-fm-performance.txt:319,搜「amortized」)。原文:摊还时间是一长串操作的总平均——单个操作可能差,但「考虑一长串操作的平均性能,整体摊还时间可能比最坏情况好得多」。 ↩
出处:「Performance」第 371 段(text/13-fm-performance.txt:371,搜「(n + 1)/2」)。原文:平均探测 (1+2+…+n)/n = (n+1)/2,「显然与 n 成正比,故平均行为确为 O(n)」。 ↩
出处:「Performance」第 379 段(text/13-fm-performance.txt:379,搜「hand waving」)。原文注释:第 1 个与第 n 个平均 (n+1)/2,第 2 个与第 n−1 个同样……「每次平均都一样,可更少代数得出同一结论」。 ↩
出处:「Performance」第 385 段(text/13-fm-performance.txt:385,搜「4, 9, 12」)。原文:数组 [4, 9, 12, 22, 34, 56, 60] 找 12:中点 22 弃右半,中点 9 弃左半,单元素 12 命中;找 13 则失败。 ↩
出处:「Performance」第 388–404 段(text/13-fm-performance.txt:388,搜「2k」)。原文:设 n=2ᵏ−1;S = 1×1+2×2+3×4+…+k×2ᵏ⁻¹;经 f(x) 求导技巧得平均比较数 (k−1)+k/n,即 Θ(log n);「失败的最坏情况需要 k 次测试,故二分搜索说是 O(log n) 算法是正当的」。 ↩
出处:「Performance」第 410 段(text/13-fm-performance.txt:410,搜「master theorem」)。原文:算法分析多涉及递推式,如 P(n)=aP(n−1)+f(n) 或 Q(n)=aQ(n/b)+f(n);「主定理能迅速给出 Q(n) 型递推的解,但整本书都可以写这个」。 ↩↩
出处:「Performance」第 371 段(text/13-fm-performance.txt:371,搜「hoping for the best」)。原文:「要按最坏情况思考;指望最好情况不现实。」 ↩
出处:「Performance」第 32 段(text/13-fm-performance.txt:32,搜「fairly stable」)。原文:「本书所有情形中,算法的空间复杂度都相当稳定,随输入元素数线性增长,因此没有选一个舍一个的依据;而时间复杂度结果多变,为选型提供扎实基础。」 ↩
出处:「Performance」第 358 段(text/13-fm-performance.txt:358,搜「skip the demonstrations」)。原文注释:本节数学味重得多,可以跳过证明只看结果;「本书其余部分不会深入这么多数学」。 ↩
出处:「Chapter 4」第 7、13、19、25、31、37、43、49、55、61 段(text/67-ch04-chapter-4.txt:7,搜「negative」;text/67-ch04-chapter-4.txt:43,搜「greatest order」;text/67-ch04-chapter-4.txt:49,搜「product」;text/67-ch04-chapter-4.txt:55,搜「induction」;text/67-ch04-chapter-4.txt:58,搜「best of times」)。答案依次:函数变负故不可能;n=O(n²) 且更贴切 o(n²);O 且 Ω ⟺ Θ;传递性普遍成立;自反性不及小 o/小 ω;O⟺Ω 对称、o⟺ω 对称;相接取大阶;相乘得 O(n³);归纳证明 2ᵏ−1;两头夹 ⟹ Θ。 ↩

第 4 章 分析算法 — 比较大 O 这把尺子¶