大O記號（big-O notation）
/ big oh /
假設你想說某個東西有多大，卻不想釘死它的精確值——就像說人群「數以千計」，而不去一個一個數人頭。大O記號正是給函數用的這種誠實的上界。當我們寫 f(x) = O(g(x)) 時，是在斷言：在我們關心的那個極限下（x 趨於無窮，或 x 趨於零），f 的增長永遠不會快過 g，至多差一個固定的常數倍。
精確的含義是：當 x 趨於某極限時 f(x) = O(g(x))，意思是存在一個常數 C 以及該極限附近的一個鄰域，在其中 f(x) 的絕對值始終小於 C 乘以 g(x) 的絕對值。所以 O(g) 就是所有最終被 g 的某個常數倍所壓住的函數構成的集合。例如，當 x 趨於無窮時 3x^2 + 5x = O(x^2)，因為 x 大時是 x^2 項定下尺度，取常數 C = 4 就綽綽有餘。在 x = 0 附近，同樣的記號要反過來讀：sin x - x = O(x^3) 表示減去 x 之後剩下的部分，在 x 很小時不會大過 x^3 的一個常數倍。
這是一切漸近分析的基本語法，處處可見：泰勒展開的誤差項（f(x) = f(0) + f'(0) x + O(x^2)）、演算法的代價（排序為 O(n log n)）、以及漸近級數的餘項。一個誠實的提醒是：大O完全隱藏了常數。O(x^2) 告訴你增長的形狀，卻不告訴你那個常數是 0.001 還是 10^9，所以兩個同為 O(n^2) 的方法在實踐中可能天差地別。
當 x 趨於 0 時 e^x = 1 + x + x^2/2 + O(x^3)；當 x 趨於無窮時 x^2 + 100x = O(x^2)。
同一個符號 O 既能描述在 0 附近的微小餘項，也能描述在無窮處的增長率——所取的極限必須每次都講清楚。
f = O(g) 是單向的斷言，而非真正的等式：不能把 O 「消去」，也不能反過來寫成 g = O(f)。它只用 g 給 f 一個上界，僅此而已。