时间复杂度 Big-O：一把衡量算法的尺子，以及它骗你的三个地方

你写了两个排序程序，跑 100 条数据都很快。老板把数据量加到一百万，一个还在 0.2 秒内跑完，另一个跑了 将近三个小时。代码逻辑没错，变量类型没写错，机器是同一台——差的只是算法本身随规模增长的方式。

要描述这种"增长方式"，我们需要一把尺子。这把尺子叫 Big-O（大 O 记号）。它是算法领域被引用最多、也被误读最多的概念。本文讲三件事：它从哪来、它到底在说什么、以及它骗你的三个地方。

一、大 O 不是为计算机发明的

一个反直觉的事实：大 O 记号比计算机早生了半个世纪。

1894 年，德国数论学家 Paul Bachmann 在《解析数论》中第一次用大写 O 来描述函数增长的量级——他关心的是素数分布，不是程序跑多快。1909 年，Edmund Landau 在《素数分布教程》中把它系统化推广，所以今天欧洲文献仍称其为 Landau 符号。

真正把它带进算法分析的，是 Donald Knuth。1976 年，他在 SIGACT News 上发表了一篇只有几页的短文，标题直白得可爱：《Big Omicron and big Omega and big Theta》。文章里他做了一件影响深远的事——把数学家随手用的记号，确立成分析算法的标准语言，并强调必须把 O、Ω、Θ 三个符号区分清楚。

换句话说：这把尺子原本是量素数的，八十年后才被用来量代码。

二、大 O 到底在说什么

严格定义：f(n) = O(g(n))，当且仅当存在正常数 c 和 n₀，使得对所有 n ≥ n₀，都有 f(n) ≤ c · g(n)。

拆成大白话是两个动作：扔掉常数倍，扔掉低阶项，只看最高阶那一项怎么长。所以：

• 3n² + 100n + 7 → O(n²)：n 大了以后，n² 那一项压倒一切
• n² + n³ → O(n³)：低阶的 n² 被吞掉
• 1000000 · n → 还是 O(n)：常数倍不算数

这里是最常见的误读：O 是"上界"，不是"等于"。 说快排是 O(n²) 完全正确（因为它是上界），说快排是 O(n³) 也没错——但这信息毫无价值。真正想表达"恰好这个量级"时，要用 Θ；要表达"至少这么慢"时，用 Ω。Knuth 那篇短文的主要诉求就是这件事。

三、量级阶梯：差距有多大

图看不清的，看数字。假设机器每秒能做一亿次（10⁸）基本操作，n = 100 万时：

指数级更不讲道理。n = 60 时，2ⁿ ≈ 1.15 × 10¹⁸ 次操作，约 366 年；n = 100 时约 4 × 10¹⁴ 年——接近宇宙年龄的三万倍。这就是为什么旅行商、子集和问题在输入稍大时就必须放弃精确解，转向近似或启发式。

四、它骗你的三个地方

大 O 是最有用的尺子，但它是渐近尺子——描述的是 n 趋向无穷时的行为，而你手上的 n 往往是 1000。三个坑：

坑一：它把常数藏起来了

一个跑 1000n 的 O(n) 算法，和一个跑 10n log n 的 O(n log n) 算法，谁的复杂度低？前者。但真跑起来，在 n < 1000 时后者更快。

这不是抬杠，是有名的工程事实：插入排序是 O(n²)，快排是 O(n log n)，但几乎所有工业级排序在小数组上都会切回插入排序。Python 的 Timsort、Java 的双轴快排都这么做——不是因为理论上更优，是因为常数因子在小规模上才是老大。

坑二：它不谈内存，也不谈缓存

归并排序 O(n log n) 很漂亮，但它需要 O(n) 的额外空间；快排原地排序，缓存局部性还好。所以"理论更快的算法"在内存吃紧或数据量大到要落盘时，可能反而更慢。

更极端的是外部排序：数据在磁盘上时，真正的瓶颈不是比较次数，而是 I/O 次数。此时衡量算法的尺子要换成"磁盘读写次数"，大 O 让位给 B 树和多路归并。

坑三：它不说清是"最坏"还是"平均"

快排最坏 O(n²)，平均 O(n log n)；哈希查找平均 O(1)，最坏 O(n)（全部碰撞时）；动态数组尾部插入单次最坏 O(n)（扩容要搬家），但摊还下来是 O(1)。

只看一个 Big-O 就下结论，是把三种完全不同的语境揉在一起。问一句"这是最坏、平均还是摊还"，比记住复杂度本身更值钱。

五、有了尺子，下一步是量分治

大 O 能描述结果，但面对递归算法时，光有尺子不够——你得先把递推式解出来。

形如 T(n) = a·T(n/b) + f(n) 的递推式（把问题拆成 a 个、每个规模 n/b、外加 f(n) 的合并代价），主定理（Master Theorem）能让你一眼看出答案，不用画递归树、不用做代入法。归并排序是它的标准范例：T(n) = 2T(n/2) + O(n) → Θ(n log n)。

本课的 M2 模块（8 讲）会把主定理的三种情况、递归树、代入法、以及主定理管不到的边界情况全部讲透。你会看到：为什么二分查找是 O(log n)、为什么快排平均是 O(n log n)、以及哪些递推式不能硬套主定理。

六、结语：地图不是地形

大 O 是计算机科学里性价比最高的一件工具：几秒钟就能判断一个方案在数据量翻十倍后还成不成立。它能让你在写代码之前就否掉一半想法。

但它是一张地图，不是地形。地图告诉你大方向，不告诉你路上有多少坑；真正跑起来，常数因子、缓存、I/O、摊还这些"细节"随时可能反转结论。

先用大 O 划掉不可能，再用实测挑出最优。 顺序对了，这把诞生于 1894 年的尺子就能一直好用。