一文聊聊算法的時(shí)間復(fù)雜度和空間復(fù)雜度

本篇文章來了解一下算法，介紹一下算法的時(shí)間復(fù)雜度和空間復(fù)雜度，希望對(duì)大家有所幫助！

算法（Algorithm）是指用來操作數(shù)據(jù)、解決程序問題的一組方法。對(duì)于同一個(gè)問題，使用不同的算法，也許最終得到的結(jié)果是一樣的，但在過程中消耗的資源和時(shí)間卻會(huì)有很大的區(qū)別。

那么我們應(yīng)該如何去衡量不同算法之間的優(yōu)劣呢？

主要還是從算法所占用的「時(shí)間」和「空間」兩個(gè)維度去考量。

• 時(shí)間維度：是指執(zhí)行當(dāng)前算法所消耗的時(shí)間，我們通常用「時(shí)間復(fù)雜度」來描述。

• 空間維度：是指執(zhí)行當(dāng)前算法需要占用多少內(nèi)存空間，我們通常用「空間復(fù)雜度」來描述。

因此，評(píng)價(jià)一個(gè)算法的效率主要是看它的時(shí)間復(fù)雜度和空間復(fù)雜度情況。然而，有的時(shí)候時(shí)間和空間卻又是「魚和熊掌」，不可兼得的，那么我們就需要從中去取一個(gè)平衡點(diǎn)。

下面我來分別介紹一下「時(shí)間復(fù)雜度」和「空間復(fù)雜度」的計(jì)算方式。

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

我們想要知道一個(gè)算法的「時(shí)間復(fù)雜度」，很多人首先想到的的方法就是把這個(gè)算法程序運(yùn)行一遍，那么它所消耗的時(shí)間就自然而然知道了。

這種方式可以嗎？當(dāng)然可以，不過它也有很多弊端。

這種方式非常容易受運(yùn)行環(huán)境的影響，在性能高的機(jī)器上跑出來的結(jié)果與在性能低的機(jī)器上跑的結(jié)果相差會(huì)很大。而且對(duì)測(cè)試時(shí)使用的數(shù)據(jù)規(guī)模也有很大關(guān)系。再者，并我們?cè)趯懰惴ǖ臅r(shí)候，還沒有辦法完整的去運(yùn)行呢。

因此，另一種更為通用的方法就出來了：「 大O符號(hào)表示法 」，即 T(n) = O(f(n))

我們先來看個(gè)例子：

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

通過「 大O符號(hào)表示法 」，這段代碼的時(shí)間復(fù)雜度為：O(n) ，為什么呢?

在 大O符號(hào)表示法中，時(shí)間復(fù)雜度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代碼執(zhí)行次數(shù)之和，而 O 表示正比例關(guān)系，這個(gè)公式的全稱是：算法的漸進(jìn)時(shí)間復(fù)雜度。

我們繼續(xù)看上面的例子，假設(shè)每行代碼的執(zhí)行時(shí)間都是一樣的，我們用 1顆粒時(shí)間 來表示，那么這個(gè)例子的第一行耗時(shí)是1個(gè)顆粒時(shí)間，第三行的執(zhí)行時(shí)間是 n個(gè)顆粒時(shí)間，第四行的執(zhí)行時(shí)間也是 n個(gè)顆粒時(shí)間（第二行和第五行是符號(hào)，暫時(shí)忽略），那么總時(shí)間就是 1顆粒時(shí)間 + n顆粒時(shí)間 + n顆粒時(shí)間 ，即 (1+2n)個(gè)顆粒時(shí)間，即： T(n) = (1+2n)*顆粒時(shí)間，從這個(gè)結(jié)果可以看出，這個(gè)算法的耗時(shí)是隨著n的變化而變化，因此，我們可以簡(jiǎn)化的將這個(gè)算法的時(shí)間復(fù)雜度表示為：T(n) = O(n)

為什么可以這么去簡(jiǎn)化呢，因?yàn)榇驩符號(hào)表示法并不是用于來真實(shí)代表算法的執(zhí)行時(shí)間的，它是用來表示代碼執(zhí)行時(shí)間的增長(zhǎng)變化趨勢(shì)的。

所以上面的例子中，如果n無限大的時(shí)候，T(n) = time(1+2n)中的常量1就沒有意義了，倍數(shù)2也意義不大。因此直接簡(jiǎn)化為T(n) = O(n) 就可以了。

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

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

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

• 線性階O(n)

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

• 平方階O(n2)

• 立方階O(n3)

• K次方階O(n^k)

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

上面從上至下依次的時(shí)間復(fù)雜度越來越大，執(zhí)行的效率越來越低。

下面選取一些較為常用的來講解一下（沒有嚴(yán)格按照順序）：

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

無論代碼執(zhí)行了多少行，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)，那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)，如：

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

上述代碼在執(zhí)行的時(shí)候，它消耗的時(shí)候并不隨著某個(gè)變量的增長(zhǎng)而增長(zhǎng)，那么無論這類代碼有多長(zhǎng)，即使有幾萬幾十萬行，都可以用O(1)來表示它的時(shí)間復(fù)雜度。

• 線性階O(n)

這個(gè)在最開始的代碼示例中就講解過了，如：

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

這段代碼，for循環(huán)里面的代碼會(huì)執(zhí)行n遍，因此它消耗的時(shí)間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時(shí)間復(fù)雜度。

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

還是先來看代碼：

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

從上面代碼可以看到，在while循環(huán)里面，每次都將 i 乘以 2，乘完之后，i 距離 n 就越來越近了。我們?cè)囍蠼庖幌拢僭O(shè)循環(huán)x次之后，i 就大于 2 了，此時(shí)這個(gè)循環(huán)就退出了，也就是說 2 的 x 次方等于 n，那么 x = log2^n

也就是說當(dāng)循環(huán) log2^n 次以后，這個(gè)代碼就結(jié)束了。因此這個(gè)代碼的時(shí)間復(fù)雜度為：O(logn)

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

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

就拿上面的代碼加一點(diǎn)修改來舉例：

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

• 平方階O(n2)

平方階O(n2) 就更容易理解了，如果把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是 O(n2) 了。

舉例：

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

這段代碼其實(shí)就是嵌套了2層n循環(huán)，它的時(shí)間復(fù)雜度就是 O(n*n)，即 O(n2)

如果將其中一層循環(huán)的n改成m，即：

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

那它的時(shí)間復(fù)雜度就變成了 O(m*n)

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

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

除此之外，其實(shí)還有 平均時(shí)間復(fù)雜度、均攤時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度、最好時(shí)間復(fù)雜度 的分析方法，有點(diǎn)復(fù)雜，這里就不展開了。

二、空間復(fù)雜度

既然時(shí)間復(fù)雜度不是用來計(jì)算程序具體耗時(shí)的，那么我也應(yīng)該明白，空間復(fù)雜度也不是用來計(jì)算程序?qū)嶋H占用的空間的。

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的一個(gè)量度，同樣反映的是一個(gè)趨勢(shì)，我們用 S(n) 來定義。

空間復(fù)雜度比較常用的有：O(1)、O(n)、O(n2)，我們下面來看看：

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

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

舉例：

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

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

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

我們先看一個(gè)代碼：

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

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

以上，就是對(duì)算法的時(shí)間復(fù)雜度與空間復(fù)雜度基礎(chǔ)的分析，歡迎大家一起交流。