大 O 記法（big-O notation）
/ big-OH /
當你描述一輛車的油費如何隨距離成長時，你不會為每一趟旅程列出一個數值；你會說「油費大致隨里程線性上升」。大 O 記法對執行時間做的是同一件事：它丟掉不重要的細節（確切的常數、較小的低階項），只留下決定可擴展性的那一件事，也就是主導的成長率。它是我們用來說「這個演算法成長得像 n 平方」而不必綁定某台特定機器或某個特定常數的語言。
精確地說，我們寫 f(n) = O(g(n))，意思是：當 n 夠大時，f(n) 至多是 g(n) 的某個常數倍：存在常數 c > 0 與 n0，使得對所有 n >= n0 都有 f(n) <= c 乘以 g(n)。所以 3n^2 + 5n + 2 = O(n^2)，因為對大 n 而言 n^2 項淹沒其餘，而像 c = 4 這樣的常數就吸收了附加項。大 O 是一個上界。它的兩位夥伴補完全圖：大 Omega，寫成 f(n) = Omega(g(n))，是下界（f 至少和 g 一樣快地成長）；大 Theta，f(n) = Theta(g(n))，則表示兩者同時成立（f 在常數倍意義下成長得恰好像 g）。三者合起來，就是成長率的文法。
大 O 在本學科裡無所不在，它帶著兩個誠實的警告。第一，它是成長的上界，不是確切的執行時間：說一個演算法是 O(n^2)，並不禁止它同時也是 O(n^3)，也不保證它真的花 n^2 步。要把成長精確釘住，你需要大 Theta。第二，大 O 隱藏了常數與低階項，這對問「它能否擴展？」很好，但若被藏起來的常數巨大無比就很危險。一個 10^100 乘以 n 的演算法是 O(n)，卻毫無用處。用大 O 來比較成長率，而不是用它預測時鐘。
取 T(n) = 7n^2 + 100n + 4000。對小 n 而言 +4000 佔主導，但隨著 n 變大，7n^2 項勝出，所以 T(n) = O(n^2)，同時也是 Theta(n^2)。說 T(n) = O(n^3) 是對的，但較弱；說 T(n) = O(n) 則是錯的，因為沒有任何 n 的常數倍能對所有大 n 都壓在 7n^2 之上。
大 O 保留主導項，丟掉常數與低階項。
大 O 是「上界」，不是等式：O(n^2) 也允許 O(n^3)，並不主張演算法真的花 n^2 步；要表達確切的成長率請用大 Theta。