一、定義

時(shí)間和空間是程序的一個(gè)硬性指標(biāo)，一個(gè)用來衡量 代碼執(zhí)行的速度 ，一個(gè)用來衡量 存儲(chǔ)空間的大小

程序 = ?數(shù)據(jù)結(jié)構(gòu) + 算法

• 時(shí)間復(fù)雜度：就是執(zhí)行程序的快慢，速度越快，時(shí)間復(fù)雜度就越好。

• 空間復(fù)雜度：就是執(zhí)行程序需要的存儲(chǔ)空間的大小，執(zhí)行程序需要的存儲(chǔ)空間越小就越好。

二、時(shí)間復(fù)雜度的計(jì)算

表示方法

我們一般用 大O符號(hào)表示法來表示時(shí)間復(fù)雜度：T(n) = O(f(n)) n是影響復(fù)雜度變化的因子，f(n)是復(fù)雜度具體的算法。

常見的時(shí)間復(fù)雜度量級(jí)

• 常數(shù)階O(1)

• 線性階O(n)

• 對(duì)數(shù)階O(logN)

• 線性對(duì)數(shù)階O(nlogN)

• 平方階O(n2)

• 立方階O(n3)

• K次方階O(n^k)

• 指數(shù)階(2^n)

接下來再看一下不同的復(fù)雜度所對(duì)應(yīng)的算法類型。

常數(shù)階O(1)

int?a?=?1; int?b?=?2; int?c?=?3; 123

我們假定每執(zhí)行一行代碼所需要消耗的時(shí)間為1個(gè)時(shí)間單位，那么以上3行代碼就消耗了3個(gè)時(shí)間單位。那是不是這段代碼的時(shí)間復(fù)雜度表示為O(n)呢 ？其實(shí)不是的，因?yàn)榇驩符號(hào)表示法并不是用于來真實(shí)代表算法的執(zhí)行時(shí)間的，它是用來表示代碼執(zhí)行時(shí)間的增長變化趨勢的。上面的算法并沒有隨著某個(gè)變量的增長而增長，那么無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時(shí)間復(fù)雜度。

線性階O(n)

for(i?=?1;?i?<=?n;?i++)?{j?=?i;j++; } 1234

看這段代碼會(huì)執(zhí)行多少次呢？第1行會(huì)執(zhí)行1次，第2行和第3行會(huì)分別執(zhí)行n次，總的執(zhí)行時(shí)間也就是 2n + 1 次，那它的時(shí)間復(fù)雜度表示是 O(2n + 1) 嗎？No ! 還是那句話：“大O符號(hào)表示法并不是用于來真實(shí)代表算法的執(zhí)行時(shí)間的，它是用來表示代碼執(zhí)行時(shí)間的增長變化趨勢的”。所以它的時(shí)間復(fù)雜度其實(shí)是O(n);

對(duì)數(shù)階O(logN)

int?i?=?1; while(i?<?n)?{i?=?i?*?2; } 1234

可以看到每次循環(huán)的時(shí)候 i 都會(huì)乘2，那么總共循環(huán)的次數(shù)就是log2n，因此這個(gè)代碼的時(shí)間復(fù)雜度為O(logn)。這兒有個(gè)問題，為什么明明應(yīng)該是O(log2n）,卻要寫成O(logn)呢？其實(shí)這里的底數(shù)對(duì)于研究程序運(yùn)行效率不重要，寫代碼時(shí)要考慮的是數(shù)據(jù)規(guī)模n對(duì)程序運(yùn)行效率的影響，常數(shù)部分則忽略，同樣的，如果不同時(shí)間復(fù)雜度的倍數(shù)關(guān)系為常數(shù)，那也可以近似認(rèn)為兩者為同一量級(jí)的時(shí)間復(fù)雜度。

線性對(duì)數(shù)階O(nlogN)

for(m?=?1;?m?<?n;?m++)?{i?=?1;while(i?<?n)?{i?=?i?*?2;} } 123456

線性對(duì)數(shù)階O(nlogN) 其實(shí)非常容易理解，將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是 n * O(logN)，也就是了O(nlogN)。

平方階O(n2)

for(x?=?1;?i?<=?n;?x++){for(i?=?1;?i?<=?n;?i++)?{j?=?i;j++;} } 123456

把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是 O(n2) 了。

立方階O(n3)、K次方階O(n^k)

參考上面的O(n2) 去理解就好了，O(n3)相當(dāng)于三層n循環(huán)，其它的類似。

三、空間復(fù)雜度計(jì)算

空間復(fù)雜度 O(1)

如果算法執(zhí)行所需要的臨時(shí)空間不隨著某個(gè)變量n的大小而變化，即此算法空間復(fù)雜度為一個(gè)常量，可表示為 O(1)。

int?i?=?1; int?j?=?2; ++i; j++; int?m?=?i?+?j; 12345

代碼中的 i、j、m 所分配的空間都不隨著處理數(shù)據(jù)量變化，因此它的空間復(fù)雜度 S(n) = O(1)。

空間復(fù)雜度 O(n)

int[]?m?=?new?int[n] for(i?=?1;?i?<=?n;?++i)?{j?=?i;j++; } 12345

這段代碼中，第一行new了一個(gè)數(shù)組出來，這個(gè)數(shù)據(jù)占用的大小為n，后面雖然有循環(huán)，但沒有再分配新的空間，因此，這段代碼的空間復(fù)雜度主要看第一行即可，即 S(n) = O(n)。

總結(jié)

評(píng)價(jià)一個(gè)算法的效率主要是看它的時(shí)間復(fù)雜度和空間復(fù)雜度情況。可能有的開發(fā)者接觸時(shí)間復(fù)雜度和空間復(fù)雜度的優(yōu)化不太多（尤其是客戶端），但在服務(wù)端的應(yīng)用是比較廣泛的，在巨大并發(fā)量的情況下，小部分時(shí)間復(fù)雜度或空間復(fù)雜度上的優(yōu)化都能帶來巨大的性能提升，是非常有必要了解的。

大家好，下面是我的另一個(gè)號(hào)，會(huì)發(fā)一些比較私密的內(nèi)容，歡迎大家關(guān)注！

---

總結(jié)

以上是生活随笔為你收集整理的时间复杂度和空间复杂度，一看就懂，面试前必过一遍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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