數步數，別數秒數
你最初的直覺也許是拿碼錶給演算法計時。但秒數會騙人。同樣的程式碼，在更新的筆電上跑得快，開著別的程式時跑得慢，熱身之後又快了些。計時告訴你的是*你這台機器今天*的情況，而不是演算法本身。所以我們改去度量硬體改不了的東西：演算法所執行的*基本步數*——一次比較、一次加法、一次交換。這個步數，才是這份食譜究竟做了多少功的誠實指紋。
但步數取決於輸入大小，於是我們問一個更鋒利的問題：當輸入增長時，工作量是如何*隨著*它增長的？資料翻一倍——工作量是翻倍、不變，還是爆炸？這種輸入大小（我們記作 *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++;