一個天花板，而非碼錶
在上一篇導覽中，我們約定不再計較常數與低階項，只看成本如何隨輸入規模成長。大O 是第一個把這個約定變成精確承諾的記號。當我們寫一個演算法跑在 O(n^2)，意思是一旦輸入夠大，它的成本成長不會比某個固定的 n^2 倍率更快。它是成長的天花板，就像「這趟車最多三小時」是時間的天花板——一個對成長最壞情況的保證，而非宣稱它總是達到那個最壞值。
為什麼是天花板而不是確切數字？因為我們通常無法精準知道成本，也不需要。如果我答應車程最多三小時，即使有些趟兩小時就到，你也能安排一天的計畫。大O對演算法扮演同樣的角色：它給你一個能跨越機器與輸入而可靠的最壞情況成長，而不逼你釘死每個細節。這種寬鬆是一項優點，但它有代價，我們會在最後誠實面對。
定義：兩個見證者
以下是精確意義。若存在一個正常數 c 與一個門檻 n0，使得對所有 n >= n0 都有 f(n) <= c 乘 g(n)，則稱 f(n) 為 O(g(n))。c 與 n0 這兩個數就是 見證者，把它們拿出來，字面上就是證明一個大O宣稱的全部內容。常數 c 回答「在幾倍之內？」，吸收例如 5n 與 n 的差別；門檻 n0 回答「從多大的規模開始？」，讓你忽略小 n 時低階項可能主導的雜亂行為。
看這兩個見證者在一個小證明裡現身。宣稱：3n^2 + 5n + 2 是 O(n^2)。對所有 n >= 1，有 n <= n^2 與 1 <= n^2，故 5n <= 5n^2 且 2 <= 2n^2，因此 3n^2 + 5n + 2 <= 3n^2 + 5n^2 + 2n^2 = 10n^2。我們就此給出了 c = 10、n0 = 1，而不等式從此永遠成立。整個動作就是把每個較小的項換成 n^2 的某個倍數——這正是 證明一個漸進界 的標準技巧。
界的代數
你很少從頭重證每個界，因為少數幾條 和與積的規則 已扛起大部分工作。和的規則：有限多項之和是其最大項的大O，所以 O(n^2) + O(n) + O(1) 收縮成 O(n^2)。這就是低階項消失的原因——它們被主導項吞掉。常數的規則：一個常數乘上函數不改變其階，所以 O(100n) 就是 O(n)。兩者合起來說：要讀出一個大O，就找最大的項，其餘全部捨去。
積的規則處理巢狀。若一塊工作花 O(f)，而對其中每一單位你又多做 O(g)，總量就是 O(f 乘 g)。這正是一個迴圈套在另一個之內時發生的事。界的相乘是巢狀迴圈背後的代數，正如相加是「一個階段做完接著做下一個」背後的代數。有了這兩種運算，你能用眼睛估算多數日常程式的大O，完全不必寫下任何一個 c 或 n0。
成長動物園的排序
要用大O，你得對哪個函數「最大」有感覺。成長率階層 把常見成本函數從最溫和到最猛烈排序：常數 O(1)、對數 O(log n)、線性 O(n)、線性對數 O(n log n)、平方 O(n^2)、立方 O(n^3)、更高次多項式 O(n^k)、指數 O(2^n)，以及怪獸般的階乘 O(n!)。隨著 n 成長，每一級都被下一級壓得渺小，所以當和的規則問哪一項最大時，這個階梯告訴你是哪個。
用 n = 1000 感受這些差距：log n 約為 10，n 為 1000，n log n 約為 10000，n^2 為一百萬，而 2^n 已有約三百位數。階梯上最關鍵的分界在多項式與指數之間：無論次方多高的多項式，最終都會被任何指數壓垮。這個 多項式對指數 的鴻溝，正是電腦科學家在「能有效率解決」與僅僅「尚不知如何」之間畫下的分界線。
從迴圈讀出大O
你真正用上這一切最常見的地方，就是迴圈。計算迴圈迭代次數 的規則很簡單：一個迴圈的成本，是它的迴圈體執行的次數，乘以迴圈體跑一次的成本。一個跑 n 次、迴圈體成本為常數的單迴圈是 O(n)。一個每步把剩餘工作減半的迴圈——就像 二分搜尋 的內部運作——只跑約 log2(n) 次，所以是 O(log n)。計數器的算術決定了次數。
巢狀迴圈相乘，由積的規則而來。巢狀迴圈分析 的微妙處在於：內層迴圈的次數可能依賴外層索引。看看下面的三角形樣式：外層索引為 i 時內層迴圈體跑 i 次，所以總數是 1 + 2 + ... + n。這個和等於 n(n+1)/2，即 (1/2)n^2 + (1/2)n。由和與常數的規則，(1/2)n 項與 (1/2) 倍率都被捨去，剩下 O(n^2)。一個常見的失誤是把 n 乘 n 直接叫做 n^2「因為有兩個迴圈」——這裡誠實的次數是三角和，恰好落在同一階，但你該靠數出來、而非靠反射動作得到它。
for i = 1 to n: # outer runs n times
for j = 1 to i: # inner runs i times when outer = i
do one O(1) step
# total body runs = 1 + 2 + ... + n = n(n+1)/2 -> O(n^2)大O沒告訴你的事
大O之所以強大，正因為它隱藏了常數與低階項——但同樣的隱藏也是它的主要陷阱。兩個演算法可以都是 O(n log n)，而其中一個在實務上慢十倍；記號看不見那個常數。更糟的是，對小輸入，一個 O(n log n) 的方法可能輸給一個 O(n^2) 的方法，因為「較好」演算法被丟掉的常數可能很大。這就是為什麼像 合併排序 這類快速排序，常在子陣列變小時改用簡單的插入排序：在小 n 時，常數取勝。
再帶走兩個誠實之處。第一，大O通常描述規模 n 的輸入下的最壞情況；平均情況取決於假設的輸入分布，而同一個演算法的最壞情況界與平均情況界可能差很多。第二，上界不是每個規模下的判決——它告訴你最終誰勝，而非 n = 5 時誰勝。大O恰好回答一個問題：成本「最多」能成長多快？至於對應的問題「它至少必須成長多快？」，我們接下來轉向 Omega 與 Theta。