成長率的階梯（the ladder of growth rates）

成長率不是一個平滑的旋鈕；它們以可辨認的階級出現，學會這道階梯能讓你瞬間直覺判斷一個演算法是否能擴展。從底部（最快、最好）到頂部（最慢、最差），常見的階級是：常數 O(1)、對數 O(log n)、線性 O(n)、n 乘 log n 的 O(n log n)、平方 O(n^2)、立方 O(n^3)、一般多項式 O(n^k)、指數 O(2^n)、階乘 O(n!)。隨著 n 成長，每一階都比下一階顯著地慢；從多項式到指數的那一躍，正是把「可解」與「不可解」分開的峽谷。

對數字有感覺能讓這道階梯變得鮮明。對數意味著把輸入加倍只增加固定量的工作，就像二分搜尋把電話簿對半切。線性意味著把輸入加倍，工作就加倍。平方意味著把輸入加倍，工作就變四倍。但指數是另一種怪獸：每多一個輸入元素就讓總工作量加倍，所以從 n = 40 走到 n = 41，就把一個 2^40（約一兆）步的計算加倍。階乘更糟：10! 約 360 萬，但 20! 約 2.4 乘以 10^18，那是檢查一份清單所有排列的領域。任何固定次數的多項式都待在峽谷溫和的那一側；任何 2^n 或更高的都跌下懸崖。

這道階梯正是複雜度理論在多項式與指數之間畫出那條大分界線的原因，也是 P 類（多項式時間）成為「高效」標準替身的原因。它也解釋了常見的演算法設計目標：把一個平方演算法變成 n-log-n 演算法，在大數據上是實實在在的勝利；而把一個指數暴力搜尋變成任何多項式方法，往往就是「不可能」與「家常便飯」之間的差別。把這道階梯記在腦中，大多數效率問題瞄一眼就能自行解答。