漸近分析

漸近分析是這樣一種做法：評判一個演算法，看的是當輸入規模趨向無窮時它的代價如何變化，而不是某一個具體輸入下精確的步數。「漸近」不過是「越走越遠」的意思。它背後的洞見是：對小輸入來說，幾乎什麼都夠快——真正決定現實成敗的差距，只有當 n 很大時才顯現出來。所以我們故意拉遠鏡頭，去研究趨勢，而不是那一個點。正是這種推理，產出了「合併排序是 O(n log n)」「氣泡排序是 O(n^2)」這樣的論斷。

這樣一來，分析既更簡單也更誠實。因為我們只關心大 n 下的行為，我們就有理由丟掉常數因子和低階項——這正是大 O 所編碼進去的那條簡化。我們不說「這在我筆電上要花 4n + 7 微秒」，因為這個數字很脆弱：更快的 CPU、更好的編譯器、不同的語言都會改變它，可它們當中沒有一個能改變代價究竟是像 n 那樣長還是像 n^2 那樣長。把這些機器相關的雜訊扔掉，漸近分析就分離出了一個演算法身上真正屬於演算法本身的那一部分。

它有三種值得記住的口味。大 O（O）給出上界——增長不會比這更糟。大 Omega 給出下界——不會比這更好。大 Theta 把它夾在兩者之間——一個緊界。我們還區分最好、平均、最壞情況：快速排序平均是 O(n log n)，可在它的最壞情況下是 O(n^2)。正是漸近分析這門功夫，讓兩個工程師能在白板上比較設計——遠在任何一個人寫下一行程式碼之前——並就「哪一個能隨規模擴展」達成一致。