python 算法分析

算法分析

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

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

• 后驗分析 - 這是對算法的經(jīng)驗分析。 所選擇的算法使用編程語言來實現(xiàn)。然后在目標(biāo)計算機上執(zhí)行。在此分析中，收集實際的統(tǒng)計數(shù)據(jù)，如運行時間和所需空間。

算法的復(fù)雜性

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

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

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

所述算法的復(fù)雜性 f（n） 給出的運行時間和/或在以下方面由該算法所需的存儲空間 ? 作為輸入數(shù)據(jù)的大小。

空間復(fù)雜性

算法的空間復(fù)雜度表示算法在其生命周期中所需的內(nèi)存空間量。算法所需的空間等于以下兩個組件的總和 -

• 固定部分，是存儲某些數(shù)據(jù)和變量所需的空間，與問題的大小無關(guān)。例如，使用的簡單變量和常量，程序大小等

• 變量部分是變量所需的空間，其大小取決于問題的大小。例如，動態(tài)內(nèi)存分配，遞歸堆?？臻g等。

任何算法p的空間復(fù)雜度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.現(xiàn)在，空間取決于給定變量和常量類型的數(shù)據(jù)類型，并且它將相應(yīng)地相乘。

時間復(fù)雜性

算法的時間復(fù)雜度表示算法運行完成所需的時間量。時間要求可以定義為一個數(shù)值函數(shù)t（n），其中t（n）可以測量為步數(shù)，只要每步消耗的時間恒定。

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