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)隨着輸入尺寸的增加而線性增長。