数步数，别数秒数
你最初的直觉也许是拿秒表给算法计时。但秒数会骗人。同样的代码，在更新的笔记本上跑得快，开着别的程序时跑得慢，热身之后又快了些。计时告诉你的是*你这台机器今天*的情况，而不是算法本身。所以我们改去度量硬件改不了的东西：算法所执行的*基本步数*——一次比较、一次加法、一次交换。这个步数，才是这份食谱究竟做了多少功的诚实指纹。
但步数取决于输入大小，于是我们问一个更锋利的问题：当输入增长时，工作量是如何*随着*它增长的？数据翻一倍——工作量是翻倍、不变，还是爆炸？这种输入大小（我们记作 *n*）与步数之间的关系，就是算法的[[time-complexity|时间复杂度]]，而盯着它在 *n* 趋向巨大的过程，就叫[[asymptotic-analysis|渐近分析]]。无论如何，小输入都很快；真正把好算法和灾难区分开的，是大输入。
大O：只留下要紧的那个形状
[[big-o-notation|大O记号]]是一种把这种增长形状写得干净利落的方式。我们不在乎精确的步数——当 *n* 变大时，`3n + 7` 和 `n` 增长得一样——所以大O会扔掉两类杂质。丢掉常数倍数：`5n` 变成 O(n)。丢掉低阶项：`n² + 100n + 9` 变成 O(n²)，因为当 *n* 很大时，`n²` 那一项把其余一切都比得渺小。剩下的，就是增长那纯粹的*形状*——而这恰恰是无论谁的计算机来跑都不变的东西。
下面是你将一遍遍遇到的那几个形状，从最好到最坏。把 O(1) 读作「常数」，O(log n) 读作「对数」，O(n) 读作「线性」，O(n log n) 读作「线性对数」，O(n²) 读作「平方」。
approx. steps as n grows (lower is better): n O(1) O(log n) O(n) O(n log n) O(n^2) ---------------------------------------------------------------- 10 1 ~3 10 ~33 100 100 1 ~7 100 ~664 10,000 1,000 1 ~10 1,000 ~9,966 1,000,000 1,000,000 1 ~20 1,000,000 ~19,931,569 1,000,000,000,000 O(1) flat O(log n) barely grows O(n) keeps pace O(n log n) gentle climb O(n^2) blows up fast
从你自己的代码里读出大O
你常常一眼就能看出形状。几条没有循环的普通语句是 O(1)——工作量根本不取决于 *n*。一个把数据走一遍的循环是 O(n)。一个循环*套在*另一个循环里、每个都遍历数据，就是 O(n²)——因为对 n 项里的每一项，你都要再做 n 步。而任何每次都把问题*减半*的东西（你会在二分查找里看到）是 O(log n)。盯住循环，形状通常会自己显现。
int first = v[0]; // O(1): one step, ignores n
for (int i = 0; i < n; i++) // O(n): one pass over the data
sum += v[i];
for (int i = 0; i < n; i++) // O(n^2): a loop inside a loop
for (int j = 0; j < n; j++) // n items x n steps each
if (v[i] == v[j]) found++;