值得問的那個問題
在前一階，你學會了用基本步而非秒數來計算演算法的成本，使用的是與機器無關的成本模型。那給了我們一個誠實的數字——比方說，某方法在規模為 n 的輸入上做 5n + 3 步——但也讓我們淹沒在細節裡。那個 5 重要嗎？那個 +3 呢？如果朋友的方法改成做 7n + 100 步，我們該偏好哪一個，又是對哪些輸入而言？漸進就是刻意決定「該丟掉什麼」來回答這些問題的學問。
關鍵的轉變，是不再問「在這筆輸入上花多久？」，而改問「當輸入規模 n 無上限地變大時，成本如何成長？」這個轉變正是漸進分析的核心。它就像不是替某一場賽跑計時，而是預測當跑道越來越長時，未來每一場誰會勝出。我們在意的是趨勢，因為趨勢才是換了電腦、語言或輸入之後仍然成立的東西。
丟掉常數倍率
我們丟掉的第一樣東西是常數倍率——前面那個乘數。不管某方法做 5n 步還是 100n 步，兩者都隨 n 成直線比例成長：輸入加倍，成本就加倍。我們把它們歸為一類，都稱為「n 階」，也就是線性。理由很具體：更快的 CPU、更好的編譯器、或更底層的語言，各自都能讓每一步加速某個固定倍數，而那個倍數會乘上整個步數。所以前導常數是你的機器與工藝的性質，不是演算法構想的性質。
這正是為什麼教科書能在不指名任何一台電腦的情況下宣稱「合併排序的時間正比於 n log n」，而且數十年後在當時無人想像的硬體上依然成立。任何特定機器未知的「每秒步數」不過是另一個常數，而我們事先就約定不去追蹤常數。正是這個約定讓結論可以攜帶。
丟掉低階項
我們丟掉的第二樣東西是低階項——一個總和中較小的部分。假設仔細地數，得到 n^2 + 3n + 7 步。隨著 n 變大，n^2 那部分會接管全局，其餘的便淡入背景。理由是算術，不是含糊其辭：在 n = 1000 時，n^2 項是 1,000,000，而 3n + 7 不過 3,007——約佔總和的千分之三。在 n = 1,000,000 時，低階項完全看不見了。所以我們回報 n^2、丟掉其餘，因為我們保留的正是真正決定成長的那一部分。
把這兩個動作合起來，一個又長又囉嗦的式子就會塌縮成它的本質。成本 4n^2 + 100n + 9000 先失去低階項（100n 與 9000 在 n^2 旁邊消失），再失去前導常數（4 被吸收），只剩下 n^2。生動的心智圖像是：當 n 朝地平線前進時，只有那唯一成長最快的項還投下影子，而連那一項的係數也被沖淡了。剩下的就是成長的階——形狀，而非大小。
- 把成本寫成各項之和，例如 4n^2 + 100n + 9000。
- 找出唯一成長最快的項；這裡是 n^2 項。
- 刪掉每個成長較慢的項——它們對大的 n 會變成可忽略的分數。
- 丟掉前導常數；剩下的（這裡是 n^2）就是成長的階。
為什麼這是誠實的比較
把成本剝到只剩成長的階，讓我們能說出一句任何效能測試都說不出的真話：成長像 n^2 的方法「最終」會輸給成長像 n log n 的方法，無論在誰的筆電上跑。差距無上限地拉開，所以超過某個輸入規模後，成長較慢的方法勝出且再也不還回領先。這正是成長率階層的回報——一旦你知道兩個方法落在不同的級上，你不必跑任何東西就知道誰贏得大 n 的比賽。
但這裡有太多人略過的部分。因為我們丟掉了常數與低階項，漸進描述的是「規模化」，而不是每個規模下的判決。對小的 n，正是我們丟掉的那些細節，可能完全顛覆排名。當 n 很小時，若 O(n^2) 方法藏起來的常數很小，一個 O(n log n) 方法真的可能輸給它——這就是隱藏常數陷阱，也是為什麼真實的排序函式庫對短的清單會退回簡單的近似平方排序。「最終」這個詞在每個漸進宣稱裡都實實在在地在工作。
所以要把成長的階看成它的本來面目：只是對大輸入的承諾——這就是大 n 的限制。它並不說「較好」的方法在 n = 5、甚至 n = 50 時勝出；交叉點可能大得出人意料。把成長的階當作對規模化的預測，而當實際輸入規模重要時，去實測而非臆測。
成長從哪來：迴圈
具體地說，成長的階通常誕生於演算法的迴圈，而且你常常不必精確地加總就能直接讀出它。經驗法則很簡單：數最內層的工作跑了幾次。一個逐一碰過 n 個項目各一次的單層迴圈，做的工作正比於 n——線性、Theta(n)——因為主體跑了 n 次，每次花一個我們被允許忽略的常數。每次迭代的那個常數，會消失進我們早已同意丟掉的前導因子裡。
把一個迴圈套進另一個，次數就相乘。若外層跑 n 次、而對每一次內層也跑 n 次，主體就跑 n 乘 n 等於 n^2 次——平方。這正是那著名雙重迴圈的核心：比較 n 個項目的每一對，約做 n^2 的工作。即使內層長度會變，同樣的相乘直覺仍然成立，加總後也落在同一個階；例如當外層索引 i 從 1 爬到 n、內層跑 i 次，就做了 1 + 2 + ... + n = n(n+1)/2 步，等於 (1/2)n^2 + (1/2)n——丟掉常數與低階項後，那就是單純的 Theta(n^2)。
for i = 1 .. n: # outer runs n times
for j = 1 .. n: # inner runs n times each
do_constant_work # body runs n * n = n^2 times -> Theta(n^2)注意這兩個丟棄如何自然地再次出現。我們從沒以奈秒寫下單個迴圈主體的成本（那個常數被丟掉），而當確切的次數算出來是 (1/2)n^2 + (1/2)n 時，我們只保留 n^2（低階項被丟掉）。迴圈結構幾乎免費地把成長的階交給你——這正是本階其餘部分要磨利的技能，從大O符號的形式意義，到直接從真實程式碼讀出執行時間。