為什麼我們丟掉細節
上一篇我們學會把執行時間寫成輸入大小 n 的函數，並對所有同樣大小的輸入取最壞情況。於是我們可能得到像「這個排序在最壞情況下要做 3n^2 + 5n + 17 次比較」這樣的式子。這很誠實，卻也很脆弱：換一台機器、改成數賦值而非比較、或微調內層迴圈，這些數字每一個都會變。3、5、17 都是記帳的偶然；真正的故事是那個 n^2。
解方是刻意把眼睛放模糊。我們約定忽略常數因子（那個 3）與低階項（那個 5n 與 17），只在意當 n 變大時代價的行為。這就是漸近分析：當 n 大到某一項遠遠壓過其餘項時的「極限」行為。回報是一種跨機器都穩定的比較，能熬過那些本就不該決定誰勝出的微小實作選擇。
三位親戚：O、Omega 與 Theta
大 O 是人人都掛在嘴邊的那一個，它捕捉的是成長的「上界」。說一個演算法跑在 O(n^2)，意思是：存在某個常數 c 與某個門檻 n0，使得對每個至少為 n0 的輸入大小 n，執行時間至多為 c * n^2。換句話說，「一旦忽略常數與小情況，它成長得不會比 n^2 更快。」這是一個天花板，是對事情能糟到什麼程度的承諾——而不是宣稱它真的就那麼慢。
大 O 有兩位親戚把這個家族補齊。大 Omega（用希臘字母 Omega 寫成）是它的鏡像：一個「下界」，「至少成長得這麼快」。一個是 Omega(n) 的演算法，對大的 n 不可能在少於 c * n 步內完成。大 Theta（希臘字母 Theta）則是緊夾的三明治：當 f 既是 O(g) 又是 Omega(g) 時，f 就是 Theta(g)，於是 g 同時從上方與下方釘住成長。當你想說「這就是個恰好 n-log-n 的演算法，不會更好也不會更差」時，你真正要的其實是 Theta。
成長速率的階梯
一旦我們同意以漸近方式讀代價，你這輩子會遇到的幾乎每個演算法都落在少數幾級階梯上。成長速率階梯把它們從最溫和排到最兇猛，而隨著 n 變大，每一級都徹底壓過它下面那一級：成長較慢的函數終究會比較小，無論它的常數多大。記住這道階梯的「順序」，比任何單一證明都值錢，因為它讓你一眼看出把輸入加倍是打個哈欠，還是一場大難。
rung grows like n=10 n=1000 everyday picture -------- ----------- ---------- -------------- ----------------------------- constant 1 1 1 look up a value by its key log log n ~3 ~10 binary search a sorted list linear n 10 1000 scan a list once linearith n log n ~33 ~10000 a good comparison sort quadratic n^2 100 1000000 compare every pair cubic n^3 1000 10^9 naive matrix multiply poly n^k ... ... still 'tame': one rung's family exp 2^n 1024 ~10^301 try every subset of n items factorial n! ~3.6e6 astronomically try every ordering of n items
這道階梯上最重要的一條界線，是多項式那幾級（n、n^2、n^3 等等——任何固定次方 n^k）與指數那幾級（2^n、n!，甚至更糟）之間的分界。線以下，成長是多項式的：把輸入加倍只會讓代價乘上一個固定倍數，所以更大的電腦與耐心跟得上更大的問題。線以上，你撞上指數爆炸，多加「一個」項目就可能讓工作量翻倍。那道懸崖正是下一篇把多項式時間單獨挑出來、當作可行性分界線的全部理由。
為什麼指數成長是一堵牆，而非一座山丘
人們很容易以為指數演算法只是「慢」，就像 n^3 比 n 慢那樣。它們根本不在同一個量級。想像一個會嘗試 n 個項目每一個子集的問題：總共有 2^n 個子集，所以每多加一個項目，工作量就翻倍。在 n=40 時大約是一兆個子集——在快機器上幾分鐘。在 n=60 時是它的一百萬倍。在 n=100 時，這個數目超過可觀測宇宙中原子的數量。再快的晶片、再大的資料中心、再聰明的快取都救不了你，因為每多一個項目，就在一步之內抹消了過去十年所有硬體的進步。
這正是理論家所說的難解性：不是「我們還沒找到快的方法」，而是「隨著輸入成長，所需資源超出任何物理上造得出的東西」。一個指數友善的多項式演算法能優雅地擴展；一個指數演算法則在某個固定、相當小的輸入大小上撞牆，從此一蹶不振。優雅對上災難——這種質的差異，正是這門領域把主要分界線畫在它所在之處的原因。
讀出一個界限：一個小小的實算例
讓我們把「忽略常數與小項」這句鬆散的話，變成一套你能一眼套用的食譜。假設我們數出某個程序的步數，在最壞情況下恰好是 T(n) = 4n^2 + 100n + 9。我們要最緊的簡單界限——能拿到 Theta 就拿 Theta。流程如下。
- 找出主導項——隨 n 增大時成長最快的那一項。在 4n^2、100n 與 9 之中，n^2 項勝出，因為對大的 n，任何二次項終究會掩埋任何線性項或常數項。
- 丟掉低階項。100n 與 9 被掃進塵土；我們剩下 4n^2。
- 丟掉常數因子。那個 4 是我們怎麼數的偶然，所以丟掉它，留下 n^2。
- 寫出界限。T(n) 是 O(n^2)（不會更糟）、Omega(n^2)（不會更好——主導項確實是二次的），因此是 Theta(n^2)：一個緊的、與機器無關的判決。
注意定義裡那個門檻悄悄在運作：4n^2 + 100n + 9 對每個 n 都大於 4n^2，所以它「不」能單被 4n^2 從上界住——但一旦 n 至少為 100，它「就」能被比如 5n^2 界住（試試看：在 n=100 時，100n + 9 終於塞得進那多出來的 n^2 裡）。那句「一旦 n 夠大」就是定義裡的 n0，也正是它准許我們忽略小輸入的混亂、報出乾淨的 Theta(n^2)。