如何進行算法分析呢？
最簡單方法是分別運行解決同一個問題的兩個算法進行比較，但這樣做法在很多時候并不理想。面對這樣的困難迫使我們求助于數(shù)學工具，雖然我們不能對一個還沒有完整實現(xiàn)的程序使用運行比較法，但卻能通過數(shù)學分析了解程序性能的大致輪廓并預估改進版本的有效性。
大多數(shù)算法都有影響運行時間的主要參數(shù) N，這里的 N 是所解決問題的大小的抽象度量，比如對于一個排序算法來說，N 是待排序元素的個數(shù)。我們的目標是盡可能地使用簡單的數(shù)學公式，用 N 表達出程序的運行效率。
函數(shù)的增長
對于將要比較的兩個算法，我們并不滿足于簡單地描述為“一個算法比另一個算法快”，而是希望能夠通過數(shù)學函數(shù)直觀地感受到二者的差異，具體來說，是希望知道“一個算法比另一個算法快多少”。
一些函數(shù)在算法分析中極為常見：
- 1。如果程序中的大多數(shù)指令只運行 1 次或幾次，與問題的規(guī)模無關，我們就說程序運行的時間是常量的。小高斯的算法就是典型的常量時間。
- lg?N。隨著問題規(guī)模的增長，程序運行時間增長較慢，可以認為程序的運行時間小于一個大常數(shù)。雖然對數(shù)的底數(shù)會影響函數(shù)的值，但影響不大。鑒于計算機是 2 進制的，所以通常取 2 為底數(shù)，lg?N=log2(?N)，這與數(shù)學中略有差別（數(shù)學中 lg?N=log10?(N)）。當 N=1024 時，lg?N=10；當 N 增長了 10 倍時，lg?N≈13，僅有略微的增長；只有當 N 增長到 N^2 時，lg?N 才翻倍。如果一個算法是把一個大問題分解為若干個小問題，而每個小問題的運行時間是常數(shù)，那么我們認為這個算法的運行時間是 lg?N，二分查找就其中的典型。
- √N。比 lg?N 稍大，當問題規(guī)模翻倍時，運行時間比翻倍少一點；當 N 增長了 100 倍時，程序運行時間增長 10 倍。開銷是 √N 時間的程序通常對程序的終止條件做了處理，比如 ，在判斷一個數(shù)是否是素數(shù)時，邊界值是這個數(shù)的平方根，而不是這個數(shù)本身。
- N。這就是通常所說的線性時間，如果問題規(guī)模增大了 M 倍，程序運行時間也增大 M 倍。1 到 100 的蠻力求和法就是線性時間，這類方法通常帶有一個以問題規(guī)模為終點的循環(huán)。
- N lg?N。當問題規(guī)模翻倍時，如果運行時間比翻倍多一點，我們就簡單地說程序運行的時間是 N lg?N。當 N=1024 時，N lg?N=10240；如果 N=2048 ，N lg?N=22528。N lg?N 與 lg?N 都是把一個大問題分解為若干個能過在常數(shù)時間內運行的小問題，區(qū)別在于是否需要合并這些小問題，如果合并，就是 N lg?N；如果不合并，就是 lg?N。大多數(shù)歸并問題的運行時間可以簡單地看作 N lg?N。
- N²。如果問題規(guī)模翻倍，運行時間增長 4 倍；問題規(guī)模增長 10 倍，運行時間增長 100 倍。
- N³。如果問題規(guī)模翻倍，運行時間增長 8 倍；問題規(guī)模增長 10 倍，運行時間增長 1000 倍。
- 2^N。真正要命的增長。如果 N=10，2^N=1024；N 翻倍后，2^N=1048576。復雜問題的蠻力法通常具有這樣的規(guī)模，這類算法通常不能應用于實際。
來看一下這些函數(shù)的增長曲線，如圖 1 所示。
▲ 圖 1 函數(shù)增長的曲線
以上函數(shù)能夠幫助我們直觀地理解算法的運行效率，讓我們很容易區(qū)分出快速算法和慢速算法。大多數(shù)時候，我們都簡單地把程序運行的時間稱為“常數(shù)”、“線性”、“平方次”等。對于小規(guī)模的問題，算法的選擇不那么重要，一旦問題達到一定規(guī)模，算法的優(yōu)劣就會立馬體現(xiàn)出來。代碼 4-2 展示了當問題規(guī)模是 10、100、1000、10000、100000、1000000 時 lg?N 、√N 、N、N lg?N 、N² 、N³ 的增長規(guī)模。
▼代碼 2 函數(shù)的增長規(guī)模 C4_2.py
01 import math
02
03 fun_list = ['lgN', 'sqrt(N)', 'N', 'NlgN', 'N^2', 'N^3'] # 函數(shù)列表
04 print(' ' * 10, end='')
05 for f in fun_list:
06 print('%-15s' % f, end='')
07 print('n', '-' * 100)
08
09 N_list = [10 ** n for n in range(7)] # 問題規(guī)模
10 for N in N_list: # 函數(shù)在不同問題規(guī)模下的增長
11 print('%-8s%-2s' % (N, '|'), end='')
12 print('%-15d' % round(math.log2(N)), end='')
13 print('%-15d' % round(math.sqrt(N)), end='')
14 print('%-15d' % N, end='')
15 print('%-15d' % round(N * math.log2(N)), end='')
16 print('%-15d' % N ** 2, end='')
17 print(N ** 3)
運行結果如圖 4.2 所示。
圖 2 告訴我們，該問題規(guī)模是 1 的時候，所有算法都同樣有效，問題規(guī)模越大，不同復雜度的算法運行效率相差得越大。
2^N 增長得太過迅猛，作為一個另類單獨列出。
▼ 代碼 3 2^N 的增長
01 for N in range(10, 110, 10):
02 print('2**{0} = {1}'.format(N, 2 ** N))
運行結果如圖 3 所示。
▲ 圖 4.3 2^N 的增長
這些運行結果告訴我們，有些時候，選擇正確的算法是解決問題的唯一途徑。對于函數(shù)的輸出結果來說，如果把 100 看作 1 秒，那么 10000 就是 100 秒，超過 1 分半。這意味著對于一個規(guī)模是 1000000 的問題來說，一個是 lg?N 復雜度的算法可以立刻得出結果，√N 復雜度的算法耗時約 10 秒，N 復雜度的算法耗時將超過 2.7 小時，N^3 復雜度則需要 3 萬多年！也許我們可以忍受一運行 10 秒或 2.7 小時的程序，但一定沒法容忍有生之年看不到結果的程序。
