快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)與算法之算法分析詳解

更新時(shí)間：2021年12月28日 09:04:30 作者：盼小輝丶

算法分析的主要目標(biāo)是從運(yùn)行時(shí)間和內(nèi)存空間消耗等方面比較算法。本文將為大家詳細(xì)介紹Python數(shù)據(jù)結(jié)構(gòu)與算法中的算法分析，需要的可以參考一下

0. 學(xué)習(xí)目標(biāo)

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

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

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

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

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

1.1 算法評(píng)價(jià)的標(biāo)準(zhǔn)

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

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

1.2 算法選擇的原則

一個(gè)算法同時(shí)可以滿(mǎn)足存儲(chǔ)空間小、運(yùn)行時(shí)間短、其它性能也好是很難做到的，很多情況下，我們不得不對(duì)性能進(jìn)行取舍，在實(shí)際選擇算法時(shí)，我們通常遵循以下原則：

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

2. 算法效率分析

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

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

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

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

2.1 大O表示法

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

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

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

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

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

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

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

算法的性能有時(shí)不僅依賴(lài)問(wèn)題的規(guī)模，還取決于算法的輸入值，輸入令算法運(yùn)行最慢的情況稱(chēng)為最壞情況，輸入令算法運(yùn)行最快的情況稱(chēng)為最好情況，隨機(jī)輸入的情況下算法的性能介于兩種極端情況之間，稱(chēng)為平均情況。

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

下表列出了一些常見(jiàn)的大O表示法實(shí)例：

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

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

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

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

其中，a aa 和 b bb 均為常數(shù)。例如以下代碼，將一個(gè)正整數(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

上述代碼中只包括一個(gè)循環(huán)，且沒(méi)有調(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ù)類(lèi)型總十分常見(jiàn)，因?yàn)樗惴ㄍǔＰ枰闅v處理序列中的每一個(gè)元素。例如將列表中的每個(gè)元素加上常數(shù) 10：

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

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

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

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

2.2.5 多項(xiàng)式復(fù)雜度

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

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

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

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

2.3 復(fù)雜度對(duì)比

為了直觀的觀察到各種復(fù)雜度的增長(zhǎng)情況，使用統(tǒng)計(jì)圖來(lái)對(duì)比各種復(fù)雜度算法的運(yùn)行時(shí)間增長(zhǎng)速度。

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

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

3. 算法的存儲(chǔ)空間需求分析

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

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

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

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

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

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

4.1 列表性能分析

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

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

為了獲取執(zhí)行時(shí)間，這里使用 timeit 模塊，該模塊能夠在一致的環(huán)境中執(zhí)行函數(shù)。要使用 timeit 模塊，首先需要?jiǎng)?chuàng)建一個(gè) Timer 對(duì)象，其接受兩個(gè)參數(shù)：第 1 個(gè)參數(shù)是要為之計(jì)時(shí)的 Python 語(yǔ)句；第 2 個(gè)參數(shù)是建立測(cè)試的 Python 語(yǔ)句。timeit 模塊會(huì)統(tǒng)計(jì)多次執(zhí)行語(yǔ)句要用多久，默認(rèn)情況下，timeit 會(huì)執(zhí)行 100 萬(wàn)次語(yǔ)句，并在完成后返回一個(gè)浮點(diǎn)數(shù)格式的秒數(shù)，可以給 timeit 傳入?yún)?shù) number，以指定語(yǔ)句的執(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))
    # 測(cè)試函數(shù)運(yùn)行 1000 次所花的時(shí)間
    append_time = append_timeit.timeit(number=1000)
    x = list(range(i))
    # 測(cè)試函數(shù)運(yùn)行 1000 次所花的時(shí)間
    insert_time = insert_timeit.timeit(number=1000)
    print("{}, {}, {}".format(i, append_time, insert_time))

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

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

4.2 字典性能分析

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

對(duì)比兩表可以發(fā)現(xiàn)，即使是同一操作使用不同數(shù)據(jù)結(jié)構(gòu)其復(fù)雜度也是不同的，例如包含操作 in。為了驗(yàn)證它們之間的不同，編寫(xiě)以下程序進(jìn)行實(shí)驗(yàn)：

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