漸進只在大 n 時才重要

漸進記號，就其定義本身，只對「最終」的行為作宣稱——對 n 達到或超過某個門檻 n0 時。它對小輸入發生什麼隻字未提，而這不是需要道歉的缺陷，而是需要尊重的界線。「漸進預測擴展」的搭檔真理是「漸進對 n = 5 隻字未提」。

回想每個大O界都附帶一個隱藏的門檻 n0：f(n) <= c 乘 g(n) 的承諾只在 n >= n0 時才生效。在 n0 以下，什麼都可能發生——理應較慢的演算法可能更快，低階項可能主導，常數可能說了算。漸進較佳的演算法真正超越較差者的那一點，稱為交叉點，而它可能大得出人意料。若演算法 A 花 1000 n、演算法 B 花 n^2，那麼 B（平方）在 n = 1000 之前更便宜；只有對超過一千的輸入，那個「較佳」的線性演算法 A 才勝出。所以漸進是否相干，完全取決於你的真實輸入相對那個交叉點是否夠大。

實務教訓：在信任一個漸進比較之前，先問「我的輸入夠大、過了交叉點了嗎？」對於總是小或有界的資料，常數小、漸進較差的演算法往往是對的工程選擇，而且更簡單。對於無上限成長的資料，漸進變得有決定性，並壓過其他一切考量。要避免的錯誤是，在漸進不適用的範圍引用漸進判決——用一個大 n 定理去正當化 n = 10 的選擇。讓工具配合規模。