0. 學習目標

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

通過本節(jié)學習，應(yīng)掌握以下內(nèi)容：

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

1. 算法的設(shè)計要求

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

1.1 算法評價的標準

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

• 高效性：執(zhí)行算法所需要的時間；
• 低存儲量：執(zhí)行算法所耗費的存儲空間，其中主要考慮輔助存儲空間；
• 可讀性：算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。

1.2 算法選擇的原則

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

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

2. 算法效率分析

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

以計算斐波那契數(shù)列第 n 項為例(斐波那契數(shù)列從第3項開始，每一項都等于前兩項之和)，在計算斐波那契數(shù)列第 n 項前后調(diào)用 time 函數(shù)，計算執(zhí)行時間：

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]))

代碼執(zhí)行結(jié)果如下：

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

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

2.1 大O表示法

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

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

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

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

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

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

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

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

2.2 常見算法復(fù)雜度

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

2.2.1 常數(shù)復(fù)雜度

常數(shù)復(fù)雜度表示，算法的漸進復(fù)雜度域輸入的規(guī)模無關(guān)，例如求列表的長度等都屬于常數(shù)復(fù)雜度。常數(shù)復(fù)雜度和代碼中是否包含循環(huán)沒有必然關(guān)系，例如循環(huán)打印 100 次 “Hello world”，這與輸入規(guī)模并沒有什么關(guān)系，因此其也是屬于常數(shù)復(fù)雜度。

2.2.2 對數(shù)復(fù)雜度

對數(shù)復(fù)雜度表示函數(shù)的增長速度至少是輸入規(guī)模的對數(shù)，當我們談?wù)搶?shù)復(fù)雜度時，我們并不關(guān)系對數(shù)的底數(shù)，這是由于可以使用換底公式，將原來底數(shù)的對數(shù)乘以一個常數(shù)轉(zhuǎn)換為另一個底數(shù)：

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

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

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

2.2.3 線性復(fù)雜度

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

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

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

2.2.4 線性對數(shù)復(fù)雜度

線性對數(shù)復(fù)雜度是兩項的乘積，每個項都依賴于輸入的規(guī)模，例如將列表中每一項正整數(shù)轉(zhuǎn)換為字符串。很多實用算法的復(fù)雜度都是對數(shù)線性的。

2.2.5 多項式復(fù)雜度

多項式復(fù)雜度的增長速度是輸入規(guī)模的 k kk 次冪，其中最常見的是平方復(fù)雜度，例如求列表 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 函數(shù)第一部分的復(fù)雜度顯然是O(len(list_a))?O(len(list_b))，第二部分代碼用于去除第一部分得到結(jié)果列表中的重復(fù)元素，雖然其中僅包含一個循環(huán)語句，但是測試條件 if i not in result 需要檢查 result 中的每個元素，因此第二部分的復(fù)雜度為O(len(temp))?O(len(result))，tmp 和 result 的長度取決于 list_a 和 list_b 中長度較小的那個，根據(jù)漸進復(fù)雜度規(guī)則可以將其忽略。最終，intersect 函數(shù)的復(fù)雜度就是O(n²)。

2.2.6 指數(shù)復(fù)雜度

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

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

2.3 復(fù)雜度對比

為了直觀的觀察到各種復(fù)雜度的增長情況，使用統(tǒng)計圖來對比各種復(fù)雜度算法的運行時間增長速度。

從上圖可以看出，對數(shù)復(fù)雜度隨問題規(guī)模的增長，運行時間的增長很小，幾乎和常數(shù)復(fù)雜度算法一樣優(yōu)秀，通常只有當輸入規(guī)模很大時才能直觀的看出兩者之間的差別，而線性復(fù)雜度和對數(shù)復(fù)雜度的區(qū)別在輸入規(guī)模很小時就非常明顯了。

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

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

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

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

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

一個程序的執(zhí)行除了需要存儲空間來寄存本身所用指令、常數(shù)變量和輸入數(shù)據(jù)外，也需要一些輔助空間用于存儲數(shù)據(jù)處理的中間數(shù)據(jù)。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的額外空間，否則應(yīng)同時考慮輸入本身所需空間。若額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。

4. Python內(nèi)置數(shù)據(jù)結(jié)構(gòu)性能分析

由于在之后的學習中，我們需要經(jīng)常使用列表和字典作為構(gòu)建其他數(shù)據(jù)結(jié)構(gòu)的基石，因此了解這些數(shù)據(jù)結(jié)構(gòu)操作的時間復(fù)雜度是必要的。

4.1 列表性能分析

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

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

為了獲取執(zhí)行時間，這里使用 timeit 模塊，該模塊能夠在一致的環(huán)境中執(zhí)行函數(shù)。要使用 timeit 模塊，首先需要創(chuàng)建一個 Timer 對象，其接受兩個參數(shù)：第 1 個參數(shù)是要為之計時的 Python 語句；第 2 個參數(shù)是建立測試的 Python 語句。timeit 模塊會統(tǒng)計多次執(zhí)行語句要用多久，默認情況下，timeit 會執(zhí)行 100 萬次語句，并在完成后返回一個浮點數(shù)格式的秒數(shù)，可以給 timeit 傳入?yún)?shù) number，以指定語句的執(zhí)行次數(shù)。

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))
    # 測試函數(shù)運行 1000 次所花的時間
    append_time = append_timeit.timeit(number=1000)
    x = list(range(i))
    # 測試函數(shù)運行 1000 次所花的時間
    insert_time = insert_timeit.timeit(number=1000)
    print("{}, {}, {}".format(i, append_time, insert_time))

在上例中，計時的語句是對 append 和 insert 操作的調(diào)用。建立測試的語句是初始化代碼或構(gòu)建環(huán)境導入語句，是執(zhí)行代碼的準備工作，示例中的 from __main__ import x 將 x 從 __main__ 命名空間導入到 timeit 設(shè)置計時的命名空間，用于在測試中使用列表對象 x，這么是為了在一個干凈的環(huán)境中運行計時測試，以免某些變量以某種意外的方式干擾函數(shù)的性能。

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

4.2 字典性能分析

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

對比兩表可以發(fā)現(xiàn)，即使是同一操作使用不同數(shù)據(jù)結(jié)構(gòu)其復(fù)雜度也是不同的，例如包含操作 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))

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

以上就是Python數(shù)據(jù)結(jié)構(gòu)與算法之算法分析詳解的詳細內(nèi)容，更多關(guān)于Python算法分析的資料請關(guān)注腳本之家其它相關(guān)文章！