python 算法分析

算法分析

算法的效率可以在執行之前和執行之后的兩個不同階段進行分析。他們是以下 -

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

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

算法的復雜性

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

• 時間因素 - 時間通過計算關鍵操作的數量來衡量，如排序算法中的比較。

• 空間因子 - 空間通過計算算法所需的最大存儲空間來測量。

所述算法的復雜性 f（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）隨著輸入尺寸的增加而線性增長。