Python資料結構 » Python演算法分析

Python演算法分析

演算法的效率可以在執行之前和執行之後的兩個不同階段進行分析。 它們如以 -

  • 先驗分析 - 這是一種演算法的理論分析。通過假定所有其他因素(例如處理器速度)是恆定的並且對實現沒有影響來測量演算法的效率。

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

演算法的複雜性

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

  • 時間因素 - 時間通過計算關鍵操作的數量來衡量，如排序演算法中的比較。
  • 空間因素 - 空間通過計算演算法所需的最大儲存空間來測量。

演算法f(n)的複雜性以演算法n所需的執行時間和/或儲存空間為輸入資料的大小。

空間複雜性

演算法的空間複雜度表示該演算法在其生命週期中所需的儲存空間量。 演算法所需的空間等於以下兩個元件的總和 -

  • 固定部分，是儲存某些資料和變數所需的空間，與問題的大小無關。 例如，使用的簡單變數和常數，程式大小等
  • 變數部分是變數所需的空間，其大小取決於問題的大小。 例如，動態記憶體分配，遞回堆疊空間等。

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

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

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

時間複雜性

演算法的時間複雜度表示演算法執行完成所需的時間量。 時間要求可以定義為一個數值函式T(n)，其中T(n)可以測量為步數，如果每步消耗的時間不變。

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