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

這裏有三個變量ABC以及一個常量。 因此S(P)= 1 + 3。現在,空間取決於給定變量和常量類型的數據類型,並且它將相應地相乘。

時間複雜性

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

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