《算法導論（原書第3版）》一第3章 函數的增長

第2章中定義的算法運作時間的增長量級簡單地刻畫了算法效率，并且還允許我們比較可選算法的相對性能。一旦輸入規模n變得足夠大，最壞情況運作時間為Θ(nlgn)的歸并排序将戰勝最壞情況運作時間為Θ(n2)的插入排序。正如我們在第2章中對插入排序所做的，雖然有時我們能夠确定一個算法的精确運作時間，但是通常并不值得花力氣來計算它以獲得多餘的精度。對于足夠大的輸入，精确運作時間中的倍增常量和低階項被輸入規模本身的影響所支配。

當輸入規模足夠大，使得隻有運作時間的增長量級有關時，我們要研究算法的漸近效率。也就是說，我們關心當輸入規模無限增加時，在極限中，算法的運作時間如何随着輸入規模的變大而增加。通常，漸近地更有效的某個算法對除很小的輸入外的所有情況将是最好的選擇。

本章給出幾種标準方法來簡化算法的漸近分析。下一節首先定義幾類“漸近記号”，其中，我們已經見過的一個例子是Θ記号。然後，我們給出貫穿本書使用的幾種記号約定。最後，我們回顧一下在算法分析中常見的若幹函數的行為。