Python數據結構與算法之算法分析詳解

0. 學習目標

我們已經知道算法是具有有限步驟的過程，其最終的目的是為瞭解決問題，而根據我們的經驗，同一個問題的解決方法通常並非唯一。這就產生一個有趣的問題：如何對比用於解決同一問題的不同算法？為瞭以合理的方式提高程序效率，我們應該知道如何準確評估一個算法的性能。

通過本節學習，應掌握以下內容：

• 瞭解算法分析的重要性
• 能夠熟練使用大O表示法分析算法的時間復雜度
• 掌握空間復雜度分析方法
• 瞭解 Python 列表和字典常見操作的時間復雜度

1. 算法的設計要求

算法分析的主要目標是從運行時間和內存空間消耗等方面比較算法。

1.1 算法評價的標準

一個好的算法首先應該是“正確”的，其對於每個輸入實例均能終止並給出正確的結果，能夠正確解決給定的計算問題。此外，還需要考慮以下方面：

• 高效性：執行算法所需要的時間；
• 低存儲量：執行算法所耗費的存儲空間，其中主要考慮輔助存儲空間；
• 可讀性：算法應易於理解，易於編碼，易於調試等等。

1.2 算法選擇的原則

一個算法同時可以滿足存儲空間小、運行時間短、其它性能也好是很難做到的，很多情況下，我們不得不對性能進行取舍，在實際選擇算法時，我們通常遵循以下原則：

• 若該程序使用次數較少，則力求算法簡明易懂；
• 對於反復多次使用的程序，應盡可能選用快速的算法；
• 若待解決的問題數據量極大，機器的存儲空間較小，則相應算法主要考慮如何節省空間。

2. 算法效率分析

算法效率分析根據算法執行所需的時間進行分析和比較，這也稱為算法的執行時間或運行時間。要衡量算法的執行時間，一個方法就是做基準分析，這是一種事後統計的方法，其使用絕對的時間單位來記錄程序計算出結果所消耗的實際時間。在 Python 中，可以使用 time 模塊的 time 函數記錄程序的開始時間和結束時間，然後計算差值，就可以得到以秒為單位的算法執行時間。

以計算斐波那契數列第 n 項為例(斐波那契數列從第3項開始，每一項都等於前兩項之和)，在計算斐波那契數列第 n 項前後調用 time 函數，計算執行時間：

import time

def fibo(n):
    start = time.time()
    a, b = 1, 1
    if n > 2:
        for i in range(n-2):
            a, b = b, a + b
    end = time.time()
    running = end-start
    return b, running

for i in range(5):
    results = fibo(100000)
    print('It takes {:.8f} seconds to calculate the 10000th item of Fibonacci sequence'.format(results[1]))

代碼執行結果如下：

It takes 0.08275080 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08277822 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08176851 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08178067 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08081150 seconds to calculate the 10000th item of Fibonacci sequence

但是這種方法計算的是執行算法的實際時間，有兩個明顯的缺陷：1) 必須先運行依據算法編制的程序；2) 依賴於特定的計算機、編譯器與編程語言等軟硬件環境，容易掩蓋算法本身的優劣。因此，我們希望找到一個獨立於程序或計算機的指標，以用來比較不同實現下的算法。

2.1 大O表示法

為瞭擺脫與計算機硬件、軟件有關的因素，我們需要一種事前分析估算的方法。可以認為特定算法的“運行工作量”大小取決於問題的規模，或者說，它是問題規模的函數，這時我們就需要量化算法的操作或步驟。一個算法是由控制結構和基本操作構成的，因此可以將算法的執行時間描述成解決問題所需重復執行的基本操作數。需要註意的是，確定合適的基本操作取決於不同的算法。例如在計算斐波那契數列第 n 項時，賦值語句就是一個基本操作，而在計算矩陣乘法時，乘法運算則是其基本操作。

在上一節的 fibo 函數中，整個算法的執行時間與基本操作(賦值)重復執行的次數n 成正比，具體而言是 1 加上 n-2 個賦值語句，如果使用將其定義為函數可以表示為T(n)=n−1，其中 n為大於 2 的正整數。n常用於表示問題規模，我們可以使用問題規模 n的某個函數f(n) 表示算法中基本操作重復執行的次數，算法的時間量度可以表示如下：

T(n)=O(f(n))

隨問題規模n的增大，T(n) 函數的某一部分會比其餘部分增長得更快，算法間進行比較時這一起部分起決定性作用，T(n) 增長最快的部分也稱為數量級函數。算法執行時間的增長率和 f(n) 的增長率相同，稱作算法的漸近時間復雜度 (asymptotic time complexity)，簡稱時間復雜度。數量級 (order of magnitude) 常被稱作大O記法或大O表示法。

通過以上分析，我們可以將算法的漸近復雜度規則描述如下：

• 如果運行時間是一個多項式的和，那麼僅保留增長速度最快的項，去掉其他各項；
• 如果剩下的項是個乘積，那麼去掉所有常數。

假設某一算法的基本步驟數為T(n)=3n²+50n+2000，當 n nn 很小時 2000 對於函數的影響最大，但是隨著n 的增長n²將逐漸變得更重要，以至於可以忽略其他兩項以及n²的系數 3，因此可以說T(n) 的數量級是n²或寫為O(n2)。

算法的性能有時不僅依賴問題的規模，還取決於算法的輸入值，輸入令算法運行最慢的情況稱為最壞情況，輸入令算法運行最快的情況稱為最好情況，隨機輸入的情況下算法的性能介於兩種極端情況之間，稱為平均情況。

2.2 常見算法復雜度

下表列出瞭一些常見的大O表示法實例：

2.2.1 常數復雜度

常數復雜度表示，算法的漸進復雜度域輸入的規模無關，例如求列表的長度等都屬於常數復雜度。常數復雜度和代碼中是否包含循環沒有必然關系，例如循環打印 100 次 “Hello world”，這與輸入規模並沒有什麼關系，因此其也是屬於常數復雜度。

2.2.2 對數復雜度

對數復雜度表示函數的增長速度至少是輸入規模的對數，當我們談論對數復雜度時，我們並不關系對數的底數，這是由於可以使用換底公式，將原來底數的對數乘以一個常數轉換為另一個底數：

其中，a aa 和 b bb 均為常數。例如以下代碼，將一個正整數轉換為字符串：

def int_to_str(num):
    digits = "0123456789"
    result = ''
    if num == 0:
        result = '0'
    else:
        while num > 0:
            result = digits[num % 10] + result
            num = num // 10
    return result

上述代碼中隻包括一個循環，且沒有調用其它函數，因此我們隻需找出循環迭代次數——在 num 為 0 之前所需的整數除法的次數log_10ⁿ。因此函數 int_to_str 的復雜度是O(logn)。

2.2.3 線性復雜度

線性復雜度在列表中等序列數據類型總十分常見，因為算法通常需要遍歷處理序列中的每一個元素。例如將列表中的每個元素加上常數 10：

def add_constant(list_o):
    for i in range(len(list_o)):
        list_o[i] += 10

這個函數的復雜度就與列表的長度成線性關系，也就是O(n)。

2.2.4 線性對數復雜度

線性對數復雜度是兩項的乘積，每個項都依賴於輸入的規模，例如將列表中每一項正整數轉換為字符串。很多實用算法的復雜度都是對數線性的。

2.2.5 多項式復雜度

多項式復雜度的增長速度是輸入規模的 k kk 次冪，其中最常見的是平方復雜度，例如求列表 list_a 和 list_b 的交集：

def intersect(list_a, list_b):
    # 第一部分
    temp = []
    for i in list_a:
        for j in list_b:
            if i == j:
                temp.append(i)
                break
    # 第二部分
    result = []
    for i in temp:
        if i not in result:
            result.append(i)
    return result

intersect 函數第一部分的復雜度顯然是O(len(list_a))∗O(len(list_b))，第二部分代碼用於去除第一部分得到結果列表中的重復元素，雖然其中僅包含一個循環語句，但是測試條件 if i not in result 需要檢查 result 中的每個元素，因此第二部分的復雜度為O(len(temp))∗O(len(result))，tmp 和 result 的長度取決於 list_a 和 list_b 中長度較小的那個，根據漸進復雜度規則可以將其忽略。最終，intersect 函數的復雜度就是O(n²)。

2.2.6 指數復雜度

指數復雜度算法的解決時間隨輸入規模的指數增長。在以下示例中，由於 1 左移 num 位得到 end，因此 end 實際上等於2^num，因此循環中計算瞭2^num次加法，時間復雜度為O(2ⁿ)。

def calculate(num):
    result = 0
    end = 1 << num
    for i in range(end):
        result += i
    return result

2.3 復雜度對比

為瞭直觀的觀察到各種復雜度的增長情況，使用統計圖來對比各種復雜度算法的運行時間增長速度。

從上圖可以看出，對數復雜度隨問題規模的增長，運行時間的增長很小，幾乎和常數復雜度算法一樣優秀，通常隻有當輸入規模很大時才能直觀的看出兩者之間的差別，而線性復雜度和對數復雜度的區別在輸入規模很小時就非常明顯瞭。

雖然O(logn) 的增長速度很慢，但是在線性乘法因子的加持下，其增長速率高於線性復雜度，但與平方復雜度的增長速度相比，就不值一提瞭，因此在實際情況下，具有O(nlogn) 復雜度的算法執行速度還是很快的。而指數復雜度除瞭對那些規模特別小的輸入，其運行時間都是不現實的，即使立方復雜度和其相比都相形見絀。

3. 算法的存儲空間需求分析

在以上內容中討論的都是代碼的時間復雜度。這是由於，與時間復雜度相比，要想感覺到空間復雜度 (space complexity) 的影響比較困難。對於用戶來說，程序運行完成需要 1 分鐘還是 10 分鐘是明顯能夠感覺到的，但程序使用的內存是 1 兆字節還是 10 兆字節則無法直觀覺察。這也就是時間復雜度通常比空間復雜度更受關註的原因。通常隻有當運行程序所需的存儲空間超過瞭計算機內存時，空間復雜度才會受到關註。

類似於算法的時間復雜度，空間復雜度作為算法所需存儲空間的量度，可以表示為：

S(n)=O(f(n))

一個程序的執行除瞭需要存儲空間來寄存本身所用指令、常數變量和輸入數據外，也需要一些輔助空間用於存儲數據處理的中間數據。若輸入數據所占空間隻取決於問題本身，和算法無關，則隻需要分析除輸入和程序之外的額外空間，否則應同時考慮輸入本身所需空間。若額外空間相對於輸入數據量來說是常數，則稱此算法為原地工作。

4. Python內置數據結構性能分析

由於在之後的學習中，我們需要經常使用列表和字典作為構建其他數據結構的基石，因此瞭解這些數據結構操作的時間復雜度是必要的。

4.1 列表性能分析

Python 列表常見操作的時間復雜度如下表所示：

在列表中雖然 append() 操作和 insert() 操作都是向列表中添加一個元素，不同的是 append() 向列表末尾追加一個元素，而 insert() 在指定位置處插入元素，其後的元素都要向後移一位，因此它們的時間復雜度也不相同。

為瞭獲取執行時間，這裡使用 timeit 模塊，該模塊能夠在一致的環境中執行函數。要使用 timeit 模塊，首先需要創建一個 Timer 對象，其接受兩個參數：第 1 個參數是要為之計時的 Python 語句；第 2 個參數是建立測試的 Python 語句。timeit 模塊會統計多次執行語句要用多久，默認情況下，timeit 會執行 100 萬次語句，並在完成後返回一個浮點數格式的秒數，可以給 timeit 傳入參數 number，以指定語句的執行次數。

import timeit
import random
append_timeit = timeit.Timer('x.append(1)', 'from __main__ import x')
insert_timeit = timeit.Timer('x.insert(0, 1)', 'from __main__ import x')
for i in range(10000, 2000000, 20000):
    x = list(range(i))
    # 測試函數運行 1000 次所花的時間
    append_time = append_timeit.timeit(number=1000)
    x = list(range(i))
    # 測試函數運行 1000 次所花的時間
    insert_time = insert_timeit.timeit(number=1000)
    print("{}, {}, {}".format(i, append_time, insert_time))

在上例中，計時的語句是對 append 和 insert 操作的調用。建立測試的語句是初始化代碼或構建環境導入語句，是執行代碼的準備工作，示例中的 from __main__ import x 將 x 從 __main__ 命名空間導入到 timeit 設置計時的命名空間，用於在測試中使用列表對象 x，這麼是為瞭在一個幹凈的環境中運行計時測試，以免某些變量以某種意外的方式幹擾函數的性能。

從上圖中可以看出，列表越長，insert 操作的耗時也隨之變長，而 append 操作的耗時很穩定，符合O(n)和O(1) 的特征。

4.2 字典性能分析

Python 字典常見操作的時間復雜度如下表所示：

對比兩表可以發現，即使是同一操作使用不同數據結構其復雜度也是不同的，例如包含操作 in。為瞭驗證它們之間的不同，編寫以下程序進行實驗：

import timeit
import random
for i in range(10000, 1000000, 20000):
    t = timeit.Timer('random.randrange({}) in x'.format(i), 'from __main__ import random, x')
    x = list(range(i))
    list_time = t.timeit(number=1000)
    x = {j: j for j in range(i)}
    dict_time = t.timeit(number=1000)
    print("{}, {}, {}".format(i, list_time, dict_time))

從上圖可以看出，隨著規模的增長，對於字典而言，包含操作的耗時始終是基本恒定的，而對於列表而言，其包含操作的耗時呈線性增長。 

以上就是Python數據結構與算法之算法分析詳解的詳細內容，更多關於Python算法分析的資料請關註WalkonNet其它相關文章！

推薦閱讀：

• Python字典和列表性能之間的比較
• python如何進行基準測試
• Python大數據用Numpy Array的原因解讀
• python函數運行內存時間等性能檢測工具
• 詳解如何用Python實現感知器算法