成長率階層

並非所有「變大」都一樣。有些成本隨輸入成長幾乎不動，有些穩定攀升，有些則爆炸。成長率階層就是把常見的成本函數從最溫和到最猛烈做標準排序，讓你一眼就能判斷兩個演算法中哪個最終會勝出。

從成長最慢（最好）到最快（最差），常見的階梯是：常數 Theta(1)；對數 Theta(log n)；線性 Theta(n)；線性對數 Theta(n log n)；平方 Theta(n^2)；立方 Theta(n^3)；更一般地，固定 k 的多項式 Theta(n^k)；指數 Theta(2^n)（或任何大於 1 的底數）；以及階乘 Theta(n!)，它比指數還糟。每一級都是下一級的小o：log n = o(n)、n = o(n log n)、n log n = o(n^2)、對每個固定 k 有 n^k = o(2^n)、且 2^n = o(n!)。感受這些差距，取 n = 1000：log n 約為 10，n 為 1000，n log n 約為 10000，n^2 為一百萬，2^n 約有 300 位數，而 n! 還要天文倍地大。

這個階梯是「效率」背後的心智地圖。從一級跳到較低的一級，可能把一夜的運算變成瞬間完成。階梯上最關鍵的分界在多項式與指數之間：無論次方多高的多項式，最終都會被任何指數壓得微不足道，這正是多項式時間成為「可解」分界線的原因。階梯隱藏的一個提醒：這些是漸進排名，所以在 n 很小時，順序可能被常數打亂——但隨著 n 成長，階梯總會重新確立自己。