Python中算法的示例分析

小編給大家分享一下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中算法的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！