目錄

• 算法的復(fù)雜度
• • 一、算法時(shí)間復(fù)雜度
  • 二、算法的空間復(fù)雜度

算法的復(fù)雜度

算法的復(fù)雜度分為：空間復(fù)雜度和時(shí)間復(fù)雜度。
我們研究算法的復(fù)雜度，側(cè)重的是研究算法隨著輸入規(guī)模擴(kuò)大增長(zhǎng)量的一個(gè)抽象，而不是精確地定位需要執(zhí)行多少次。因?yàn)槿绻菢拥脑?#xff0c;我們還要考慮編譯器的優(yōu)化問(wèn)題等等一些其他的問(wèn)題。
我們?cè)谟?jì)算算法的復(fù)雜度時(shí)不用關(guān)心編寫程序所用的語(yǔ)言時(shí)什么，也不用關(guān)心這些程序?qū)⑴茉谑裁礃拥挠?jì)算機(jī)上，我們只關(guān)心它所實(shí)現(xiàn)的算法。不計(jì)那些循環(huán)索引的遞增和循環(huán)終止條件、變量聲明、打印結(jié)果等操作。
最終，在分析程序的運(yùn)行時(shí)間時(shí)，最重要的是把程序看成是獨(dú)立于程序設(shè)計(jì)語(yǔ)言的算法或一系列步驟。

我們?cè)诜治鲆粋€(gè)算法的運(yùn)行時(shí)間時(shí)，重要的是把基本操作的數(shù)量和輸入模式關(guān)聯(lián)起來(lái)。

一、算法時(shí)間復(fù)雜度

定義：在進(jìn)行算法分析時(shí)，語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度。記作：T(n)=O(f(n))。它表示隨著問(wèn)題規(guī)模n的擴(kuò)大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。其中f(n)是問(wèn)題規(guī)模n的函數(shù)。

一般情況下，隨著輸入規(guī)模n的增加，T(n)增長(zhǎng)最慢的算法為最優(yōu)算法。

如何分析一個(gè)算法的時(shí)間復(fù)雜度呢？
用常數(shù)1取代運(yùn)行時(shí)間中的所有的加法。
在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
如果最高階項(xiàng)存在且不是1，則除去與這個(gè)項(xiàng)相乘的常數(shù)。
得到的最后結(jié)果就是時(shí)間復(fù)雜度。
例：

上面程序的時(shí)間復(fù)雜度按理說(shuō)應(yīng)為O(n^2+n),但其實(shí)不是這樣的。按照上面的概念可知時(shí)間復(fù)雜度為O(n ^2)這是因?yàn)楫?dāng)n特別大的時(shí)候O(n)對(duì)原來(lái)時(shí)間復(fù)雜度的增加效果不明顯，就可以忽略了。


由上圖可知：常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次為：O(1)<O(logn)<O(n)<O(nlogn)<O(n ^2 )<
(n ^ 3)<O(2^n)<O(n!)<O(n ^n)

二、算法的空間復(fù)雜度

算法的空間復(fù)雜度通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法的空間復(fù)雜度的計(jì)算公式記作：S(n)=O(f(n))，其中，n為問(wèn)題的規(guī)模，f(n)為語(yǔ)句關(guān)于n所占存儲(chǔ)空間的函數(shù)。
通常，我們都是用 “ 時(shí)間復(fù)雜度 ” 來(lái)指運(yùn)行時(shí)間的需求，用 “ 空間復(fù)雜度 ” 來(lái)指空間需求。當(dāng)題目中要讓我們求 “ 復(fù)雜度 ” 時(shí)，通常指的是時(shí)間復(fù)雜度。

總結(jié)

以上是生活随笔為你收集整理的算法的复杂度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。