复习 · #0 / 11

大O复杂度

当输入规模增长时，工作量增长得有多快？

complexity · growth race

input size 1,000,000 elements

drag the slider — every mode updates live

动手试试：把 N 滑块从 4 一路拉到 4k，每停一站就点一次 run experiment。在 N=4 时，每根柱子看起来都一样高；到了 N=4k，O(n²) 那根柱子会把其余的全部碾压。这道鸿沟，正是大O想要提醒你警惕的东西。

为什么它重要

接下来 10 节课里你会遇到的每一种数据结构，都是在用一种代价去换取另一种代价。数组的读取是 O(1)，但插入是 O(n)。哈希表的查找是 O(1)，但没有顺序。平衡树牺牲了一些常数因子上的速度，换来了 O(log n) 的最坏情况保证。在你真正感受到这些差异随着 N 增长会变成什么样子之前，这些词对你来说毫无意义。

这正是本节课的目的。暂时不写代码——先看曲线。

大O到底在度量什么

一个算法所执行的基本操作的次数，作为输入规模的函数，在最坏情况下，忽略常数项与低阶项。

这里有三个承重的关键部分：

作为输入规模的函数。 它是一条曲线，而不是一个数字。"这件事花了多少次比较？"没有答案；"对于 N 个元素，这件事花了多少次比较？"才有答案。
最坏情况。 在 1,000 个元素里做线性查找，也许第一次就命中了目标。但如果你要把这段代码发到生产环境，你必须为最坏情况做打算——把全部 1,000 个都检查一遍。
忽略常数项与低阶项。 3n + 5 和 n 都是 O(n)。随着 N 增长，常数会被淹没。它们在做基准测试时有意义，但对渐近的形状无关紧要。

O、Θ、Ω——三种界

工程师们随口都说"大O"，但教科书会区分三种记号。它们描述的是对一个函数增长速度的不同的界。

渐近记号: O(f(n)) — 上界。T(n) = O(f(n)) 表示 T 的增长速度至多和 f 一样快。"代价不超过。"; Ω(f(n)) — 下界。T(n) = Ω(f(n)) 表示 T 的增长速度至少和 f 一样快。"代价不低于。"; Θ(f(n)) — 紧界。同时满足 O(f(n)) 和 Ω(f(n))。"代价恰好成正比。"
一个具体的例子——归并排序: O(n log n) — 它的最坏情况不会比 n log n 更糟。正确但宽松：它同样是 O(n²)、O(n³)……任何上界都成立。; Ω(n log n) — 它的最好情况至少是 n log n（依据信息论的论证，任何基于比较的排序都有这个下界）。; Θ(n log n) — 这个紧的表述：归并排序恰好就在 n log n 这个量级上，不更快也不更慢。

复习时为什么这很重要： 当一本教科书写下 Θ(n) 时，它声称这个算法同时被 n 上界和下界所约束——这是一个比 O(n) 更强的论断。二分查找是 O(log n)（最坏情况）、Ω(1)（最好情况——第一次探测就命中），而整体上并不是 Θ(log n)——但在最坏情况下是 Θ(log n)。在挑选记号之前，先弄清楚你说的是哪一种情况。

最好、最坏、平均

与上面那些界相伴相生的，是你度量的是哪一种输入：

最坏情况 — 让工作量最大化的输入。当你不加限定地说"大O"时，默认就是它。
最好情况 — 让工作量最小化的输入。快速排序的最好情况是 Θ(n log n)；最坏情况是 Θ(n²)。
平均情况 — 在某个输入分布上的期望工作量。哈希表查找平均是 O(1)，但最坏是 O(n)。
摊还（均摊） — 在对同一数据结构的一串操作上取平均。动态数组的追加摊还是 O(1)，因为那次罕见的 O(n) 扩容，被前面 n 次便宜的追加分摊掉了。证明见数组和堆两节课。

看懂这张图

每根柱子都是一种经典操作，运行在同一个长度为 N 的输入数组上：

各个量级: O(1) lookup arr[42] — 一次 CPU 操作，与 N 无关; O(log n) binary search — 每一步把搜索空间对半砍; O(n) find max — 每个元素都摸一遍; O(n log n) merge sort — n 个元素，每个都要在 log n 层归并中被搬动一次; O(n²) find all pairs — 每一种 (i,j) 组合
两根柱子分别代表什么: predicted 公式在这个 N 处的取值（渐近线）; actual 在一个真实数组上运行算法得到的实际操作次数

这些柱子在 x 轴上用的是对数刻度。只有这样，O(1) = 1 次操作和 O(n²) = 8 million 次操作才能挤进同一张图。在对数轴上靠肉眼估算距离会产生误导——要读数字。

小 N 陷阱

在 N = 4 时，这些柱子在视觉上根本分不出来。O(1) = 1，O(n²) = 6。六"基本上等于没有"。这就是为什么初出茅庐的工程师会写出那种在测试里能跑却在生产里熔毁的 O(n²) 代码——测试夹具只有 10 行，而生产表有 1000 万行。

到了 N = 1024：

1024 个元素的代价: O(1) 1 次操作; O(log n) ~10 次操作; O(n) 1,024 次操作; O(n log n) ~10,240 次操作; O(n²) 523,776 次操作

同样的算法，同样的机器——它们之间却隔着五个数量级。

再深入一些

下面是几条经验法则，在后面的课程里你会反复用到：

如果你看到对输入的一重循环，那你至少有 O(n)。
如果你看到嵌套循环、两层都在遍历输入，那你就到了 O(n²)。
如果每一步工作量都减半（递归、二分查找、平衡树下降），那就是 O(log n)。
对基于比较的数据排序是 O(n log n)——在一般情况下你无法做得更快（信息论下界）。
哈希把循环坍缩成 O(1) 的期望——代价是放弃了顺序和最坏情况的保证。

好了——接下来，进入真正的数据结构。

📈 大O复杂度