python 算法分析

算法分析

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

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

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

算法的復(fù)雜性

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

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

• 空間因子 - 空間通過計(jì)算算法所需的最大存儲(chǔ)空間來測量。

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

空間復(fù)雜性

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

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

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

任何算法p的空間復(fù)雜度s（p）是s（p）= c + sp（i），其中c是固定部分，s（i）是算法的可變部分，取決于實(shí)例特征i.是一個(gè)簡單的例子，試圖解釋這個(gè)概念 -

algorithm: sum(a, b)
step 1 -  start
step 2 -  c ← a + b + 10
step 3 -  stop

這里我們有三個(gè)變量a，b和c以及一個(gè)常量。因此s（p）= 1 + 3.現(xiàn)在，空間取決于給定變量和常量類型的數(shù)據(jù)類型，并且它將相應(yīng)地相乘。

時(shí)間復(fù)雜性

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

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