為什麼要把這些動物排成一列
到目前為止，你已能把 大O符號 讀成天花板，把 Theta（漸進緊界） 讀成緊湊的判決。但一個 Theta(n log n) 的執行時間，要等你對 n log n 落在哪裡有了直覺後才真正有意義——它接近線性，還是接近 n^2？這篇指南的目的就是建立那份直覺。我們會把演算法分析中一再出現的那幾個函數，排成一個嚴格的高下順序，也就是 成長率階層，這樣當一個 Theta 落在其中之一時，你立刻就知道成本是怎麼隨規模變化的。
這是那個著名的排列，成長最慢的在左邊，以 Theta 類別寫出：Theta(1) < Theta(log n) < Theta(sqrt n) < Theta(n) < Theta(n log n) < Theta(n^2) < Theta(n^3) < Theta(2^n) < Theta(n!)。這裡的「<」是嚴格壓倒關係：每個函數終究會被它右邊那個，以任意你想要的常數倍超越。這正是上一篇講過的 小o 關係——log n = o(sqrt n)、n^2 = o(2^n)，沿著這一列一路如此。
溫和的一端：常數、對數與線性
Theta(1)，常數時間，是夢寐以求的：工作量完全不隨輸入成長。用索引查一個陣列元素，或往堆疊壓入一個值，無論 n 是十還是一百億，成本都一樣。Theta(log n)，對數時間，幾乎一樣好——它會成長，但懶得驚人。感受對數最乾淨的方式是反覆減半：log2(n) 數的是你能把 n 減半幾次才到 1。從 n = 1000 走到 n = 1,000,000，輸入乘了一千倍，但 log2(n) 卻只從約 10 升到約 20。這就是二分搜尋的祕密：把乾草堆加倍，只多探查一次。
Theta(n)，線性時間，是把每個元素碰一次的自然成本：掃過一個串列、加總一個陣列、找出最大值。當答案真的取決於全部輸入時，它往往是你能盼到的最好結果，因為你至少得讀過所有東西才能確認它。介於對數與線性之間的是 Theta(sqrt n)，平方根——比對數慢、比線性快——它出現在像區塊分解這類技巧中：你把 n 個項目切成約 sqrt n 個、每塊約 sqrt n 個的區塊。它是動物園裡較罕見的動物，但值得知道牠就住在那兩位著名鄰居之間。
中段的主力：線性對數與多項式
緊挨在線性之上的是 Theta(n log n)，線性對數時間——像合併排序這類最好的通用比較排序的執行時間。它只比線性慢一絲：當 n = 1,000,000 時對數因子約為 20，所以 n log n 大約是 n 的二十倍，而不是兩萬倍。關鍵在於，n log n 比起 n^2 要更接近 n；把一個 n log n 的排序當成「基本上是線性」是個公允的工作直覺，但當成「基本上是平方」就嚴重高估了成本。這也是比較排序下界所說、單靠比較無法突破的地板。
接著是 多項式：兩層巢狀迴圈的 Theta(n^2)，像樸素矩陣乘法那樣三層巢狀的 Theta(n^3)，以及更高的次方。在多項式內部，規則很簡單：對大 n 而言指數較大的勝出——n^3 終究以任意倍數壓過 n^2——而 加法與乘法規則 告訴你如何把它們合起來：在加法裡，最大項吞掉其餘（n^2 + 5n + 99 是 Theta(n^2)），而把一個迴圈跑在另一個之內則是把兩者的成本相乘。這兩條規則就是日常讀執行時間的大部分算術。
懸崖：指數與階乘
越過每個多項式之後是一道懸崖。Theta(2^n)，指數時間，是試遍 n 個項目所有子集的成本——而它不是成長，是引爆。每多一個元素就讓工作量加倍，於是 2^n 在 n = 10 時是 1024，在 n = 20 時約一百萬，在 n = 30 時約十億。一個像 n^3 的多項式在 n = 30 時不過 27,000；差距已是天文數字，且每一步都在擴大。這就是 多項式與指數的分界，整個動物園裡最重要的那條線；我們會在後面的階段看到，它正是我們稱為可解的問題與一般而言不可解的問題之間的界線。
而在那之後，連 Theta(n!)，階乘時間，都在咆哮——這是試遍 n 個項目所有排序（排列）的成本，也就是用檢查每條路線的樸素方式攻擊旅行推銷員問題。階乘跑得比 2^n 快，因為 n! = 1 * 2 * 3 * ... * n 每一步乘上一個越來越大的因子，而 2^n 永遠只乘上 2。到 n = 20 時，n! 已超過兩百京（2.4 * 10^18），而 2^20 不過一百萬。如果一個方法在枚舉排列，它就只能用於極小的 n，沒有第二句話。
n log2 n n^2 2^n n! 10 ~3.3 100 1,024 3,628,800 20 ~4.3 400 1,048,576 2.4 x 10^18 50 ~5.6 2,500 ~1.1 x 10^15 ~3.0 x 10^64 100 ~6.6 10,000 ~1.3 x 10^30 ~9.3 x 10^157
如何當場比較兩隻動物
你不會總是碰到已經在排列裡的函數；有時你得比較兩個陌生的，像 n^2 對上 n * (log n)^3，或 2^(sqrt n) 對上 n^5。可靠的工具是你在 極限觀點 學過的比值法：構造比值 f(n)/g(n)，問它隨 n 增大往哪走。若趨於 0，則 f = o(g) 且 g 勝；若趨於無窮，則 f 勝；若穩定在一個正常數，則它們是同一個 Theta 類別。整個階層不過就是把這個比較套用到那些常見形狀上。
- 先剝掉常數與低階項：3n^2 + n 化為 n^2，因為漸進分析對兩者都視而不見。
- 把兩側各依族別歸位：n 的次方壓倒 log n 的次方，而指數壓倒每個多項式。
- 若兩者都帶指數味，就比較指數本身：2^(sqrt n) 對 2^n 化約成 sqrt n 對 n，所以 2^n 勝。
- 若快速比較仍不清楚，就取比值 f(n)/g(n)（或比較兩者的對數），看它趨於 0、一個正常數，還是無窮。
排列藏起了什麼——以及它真正的意思
這個階層是關於大 n 的陳述，而且只關於大 n。因為 漸進分析只在某個門檻之後才生效，一個在動物園裡漸進位置較高的方法，在小輸入上可能真的會贏，那裡是被捨棄的常數當家。一個帶極小常數的 Theta(2^n) 程序，在某個交叉點 n 之前可能贏過帶巨大常數的 Theta(n^3) 程序，只有越過那一點，指數的厄運才接管全局。排列告訴你的是最終誰贏，從不是 n = 8 時誰贏——後者取決於正是符號丟掉的那些常數。
話雖如此，整幅圖裡影響最深遠的一刀，仍是多項式與指數之間那一刀。所有對固定 k 為 Theta(n^k) 的，我們非正式地稱為 有效率的，而所有 2^n 及其之上的，我們稱為最壞情況下不可解——這就是那道懸崖的實務意涵。這個區分之所以穩固，正是因為它在常數面前屹立不搖：沒有任何固定常數能救 2^n 免於終究輸給 n^100，也沒有任何常數能讓 n^100 永遠壓在 2^n 之上。多項式與指數的邊界，正是這座階梯其餘部分——一路上到 P 對 NP——所圍繞建構的那道分水嶺。