Python - 演算法分析

演算法的效率可以在兩個不同的階段進行分析，即實現之前和實現之後。它們如下所示：

• 先驗分析 - 這是對演算法的理論分析。透過假設所有其他因素（例如處理器速度）都是恆定的並且對實現沒有影響來衡量演算法的效率。

• 後驗分析 - 這是對演算法的經驗分析。選擇的演算法使用程式語言實現。然後在目標計算機上執行此操作。在此分析中，收集實際統計資料，例如執行時間和所需空間。

演算法複雜度

假設X是一個演算法，n是輸入資料的大小，演算法X使用的 時間和空間是決定X效率的兩個主要因素。

• 時間因素 - 透過計算關鍵操作的數量（例如排序演算法中的比較）來衡量時間。

• 空間因素 - 透過計算演算法所需的最大記憶體空間來衡量空間。

演算法的複雜度f(n)給出演算法的執行時間和/或儲存空間，以n（作為輸入資料的大小）表示。

空間複雜度

演算法的空間複雜度表示演算法在其生命週期中所需的記憶體空間量。演算法所需的空間等於以下兩個組成部分之和：

• 一個固定部分，即用於儲存某些資料和變數的空間，這些資料和變數與問題的規模無關。例如，使用的簡單變數和常量、程式大小等。

• 一個可變部分，即變數所需的空間，其大小取決於問題的規模。例如，動態記憶體分配、遞迴堆疊空間等。

任何演算法P的空間複雜度S(P)為S(P) = C + SP(I)，其中C是固定部分，S(I)是演算法的可變部分，它取決於例項特徵I。以下是一個簡單的例子，試圖解釋這個概念：

演算法：SUM(A, B)

步驟 1 - 開始

步驟 2 - C ← A + B + 10

步驟 3 - 停止

這裡我們有三個變數A、B和C以及一個常量。因此S(P) = 1 + 3。現在，空間取決於給定變數和常量型別的數 據型別，並且將相應地進行乘法。

時間複雜度

演算法的時間複雜度表示演算法執行到完成所需的時間量。時間需求可以定義為一個數值函式T(n)，其中T(n)可以衡量為步驟數，前提是每個步驟消耗恆定的時間。

例如，兩個n位整數的加法需要n個步驟。因此，總計算時間為T(n) = c * n，其中c是兩個位相加所需的時間。在這裡，我們觀察到T(n)隨著輸入大小的增加而線性增長。