如何進行算法分析呢？

最簡單方法是分别運行解決同一個問題的兩個算法進行比較，但這樣做法在很多時候并不理想。面對這樣的困難迫使我們求助于數學工具，雖然我們不能對一個還沒有完整實現的程序使用運行比較法，但卻能通過數學分析了解程序性能的大緻輪廓并預估改進版本的有效性。

大多數算法都有影響運行時間的主要參數 N，這裡的 N 是所解決問題的大小的抽象度量，比如對于一個排序算法來說，N 是待排序元素的個數。我們的目标是盡可能地使用簡單的數學公式，用 N 表達出程序的運行效率。

對于将要比較的兩個算法，我們并不滿足于簡單地描述為“一個算法比另一個算法快”，而是希望能夠通過數學函數直觀地感受到二者的差異，具體來說，是希望知道“一個算法比另一個算法快多少”。

一些函數在算法分析中極為常見：

1. 1。如果程序中的大多數指令隻運行 1 次或幾次，與問題的規模無關，我們就說程序運行的時間是常量的。小高斯的算法就是典型的常量時間。
2. lg⁡N。随着問題規模的增長，程序運行時間增長較慢，可以認為程序的運行時間小于一個大常數。雖然對數的底數會影響函數的值，但影響不大。鑒于計算機是 2 進制的，所以通常取 2 為底數，lg⁡N=log2(⁡N)，這與數學中略有差别（數學中 lg⁡N=log10⁡(N)）。當 N=1024 時，lg⁡N=10；當 N 增長了 10 倍時，lg⁡N≈13，僅有略微的增長；隻有當 N 增長到 N^2 時，lg⁡N 才翻倍。如果一個算法是把一個大問題分解為若幹個小問題，而每個小問題的運行時間是常數，那麼我們認為這個算法的運行時間是 lg⁡N，二分查找就其中的典型。
3. √N。比 lg⁡N 稍大，當問題規模翻倍時，運行時間比翻倍少一點；當 N 增長了 100 倍時，程序運行時間增長 10 倍。開銷是 √N 時間的程序通常對程序的終止條件做了處理，比如 ，在判斷一個數是否是素數時，邊界值是這個數的平方根，而不是這個數本身。
4. N。這就是通常所說的線性時間，如果問題規模增大了 M 倍，程序運行時間也增大 M 倍。1 到 100 的蠻力求和法就是線性時間，這類方法通常帶有一個以問題規模為終點的循環。
5. N lg⁡N。當問題規模翻倍時，如果運行時間比翻倍多一點，我們就簡單地說程序運行的時間是 N lg⁡N。當 N=1024 時，N lg⁡N=10240；如果 N=2048 ，N lg⁡N=22528。N lg⁡N 與 lg⁡N 都是把一個大問題分解為若幹個能過在常數時間内運行的小問題，區别在于是否需要合并這些小問題，如果合并，就是 N lg⁡N；如果不合并，就是 lg⁡N。大多數歸并問題的運行時間可以簡單地看作 N lg⁡N。
6. N²。如果問題規模翻倍，運行時間增長 4 倍；問題規模增長 10 倍，運行時間增長 100 倍。
7. N³。如果問題規模翻倍，運行時間增長 8 倍；問題規模增長 10 倍，運行時間增長 1000 倍。
8. 2^N。真正要命的增長。如果 N=10，2^N=1024；N 翻倍後，2^N=1048576。複雜問題的蠻力法通常具有這樣的規模，這類算法通常不能應用于實際。

來看一下這些函數的增長曲線，如圖 1 所示。

▲ 圖 1 函數增長的曲線

以上函數能夠幫助我們直觀地理解算法的運行效率，讓我們很容易區分出快速算法和慢速算法。大多數時候，我們都簡單地把程序運行的時間稱為“常數”、“線性”、“平方次”等。對于小規模的問題，算法的選擇不那麼重要，一旦問題達到一定規模，算法的優劣就會立馬體現出來。代碼 4-2 展示了當問題規模是 10、100、1000、10000、100000、1000000 時 lg⁡N 、√N 、N、N lg⁡N 、N² 、N³ 的增長規模。

▼代碼 2 函數的增長規模 C4_2.py

01importmath 02 03fun_list=['lgN','sqrt(N)','N','NlgN','N^2','N^3']#函數列表 04print(''*10,end='') 05forfinfun_list: 06print('%-15s'%f,end='') 07print('\n','-'*100) 08 09N_list=[10**nforninrange(7)]#問題規模 10forNinN_list:#函數在不同問題規模下的增長 11print('%-8s%-2s'%(N,'|'),end='') 12print('%-15d'%round(math.log2(N)),end='') 13print('%-15d'%round(math.sqrt(N)),end='') 14print('%-15d'%N,end='') 15print('%-15d'%round(N*math.log2(N)),end='') 16print('%-15d'%N**2,end='') 17print(N**3)

運行結果如圖 4.2 所示。

圖 2 告訴我們，該問題規模是 1 的時候，所有算法都同樣有效，問題規模越大，不同複雜度的算法運行效率相差得越大。

2^N 增長得太過迅猛，作為一個另類單獨列出。

▼ 代碼 3 2^N 的增長

01forNinrange(10,110,10): 02print('2**{0}={1}'.format(N,2**N))

運行結果如圖 3 所示。

▲ 圖 4.3 2^N 的增長

這些運行結果告訴我們，有些時候，選擇正确的算法是解決問題的唯一途徑。對于函數的輸出結果來說，如果把 100 看作 1 秒，那麼 10000 就是 100 秒，超過 1 分半。這意味着對于一個規模是 1000000 的問題來說，一個是 lg⁡N 複雜度的算法可以立刻得出結果，√N 複雜度的算法耗時約 10 秒，N 複雜度的算法耗時将超過 2.7 小時，N^3 複雜度則需要 3 萬多年！也許我們可以忍受一運行 10 秒或 2.7 小時的程序，但一定沒法容忍有生之年看不到結果的程序。

上文 [遇見] 授權節選自北大出版社《程序員數學從零開始》

270餘幅插圖 90餘段Python代碼 20餘個原理剖析，教你學會程序員必須掌握的數學及算法背後的數學原理。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!