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

• 先驗(yàn)分析 - 這是一種算法的理論分析。通過假定所有其他因素(例如處理器速度)是恒定的并且對實(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ì)算算法所需的最大存儲空間來測量。

算法f(n)的復(fù)雜性以算法n所需的運(yùn)行時(shí)間和/或存儲空間為輸入數(shù)據(jù)的大小。

空間復(fù)雜性

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

• 固定部分，是存儲某些數(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)隨著輸入尺寸的增加而線性增長。