算法復(fù)雜度包括哪些

算法復(fù)雜度包括哪些？針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

算法復(fù)雜度：

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

在計(jì)算機(jī)科學(xué)中，時(shí)間復(fù)雜性，又稱時(shí)間復(fù)雜度，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。這是一個(gè)代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無(wú)窮時(shí)的情況。

為了計(jì)算時(shí)間復(fù)雜度，我們通常會(huì)估計(jì)算法的操作單元數(shù)量，每個(gè)單元運(yùn)行的時(shí)間都是相同的。因此，總運(yùn)行時(shí)間和算法的操作單元數(shù)量最多相差一個(gè)常量系數(shù)。

相同大小的不同輸入值仍可能造成算法的運(yùn)行時(shí)間不同，因此我們通常使用算法的最壞情況復(fù)雜度，記為T(n)，定義為任何大小的輸入n所需的最大運(yùn)行時(shí)間。另一種較少使用的方法是平均情況復(fù)雜度，通常有特別指定才會(huì)使用。時(shí)間復(fù)雜度可以用函數(shù)T(n) 的自然特性加以分類，舉例來(lái)說(shuō)，有著T(n) =O(n) 的算法被稱作“線性時(shí)間算法”；而T(n) =O(M^n) 和M= O(T(n)) ，其中M≥n> 1 的算法被稱作“指數(shù)時(shí)間算法”。

一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(n)。
　　一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，T（n)/f (n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
　　在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)雜度為O(1),另外，在時(shí)間頻度不相同時(shí)，時(shí)間復(fù)雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為O(n2)。

時(shí)間頻度

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(n)。

空間復(fù)雜度

與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。記作:

S(n)=O(f(n))

算法執(zhí)行期間所需要的存儲(chǔ)空間包括3個(gè)部分：

• 算法程序所占的空間；

• 輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間；

• 算法執(zhí)行過(guò)程中所需要的額外空間。

在許多實(shí)際問(wèn)題中，為了減少算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)。

關(guān)于算法復(fù)雜度包括哪些問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。