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

具體如何衡量不同算法之間的優(yōu)劣呢？

主要還是從算法所占的【時(shí)間】和【空間】?jī)蓚€(gè)維度去考量。

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

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

因此，評(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í)間就自然而然知道了。

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

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

通過(guò)【大O符號(hào)表示法】，這段代碼的時(shí)間復(fù)雜度為：O(n),why?

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

假設(shè)每行代碼的執(zhí)行時(shí)間都是一樣的，我們用1顆粒時(shí)間來(lái)表示，那么這個(gè)例子的第一行耗時(shí)是1個(gè)顆粒，第三行的執(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)表示法并不是用于來(lái)真實(shí)代表算法的執(zhí)行時(shí)間的，它是用來(lái)表示代碼執(zhí)行時(shí)間的增長(zhǎng)變化趨勢(shì)的。

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

常見(jià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ù)雜度越來(lái)越大，執(zhí)行的效率越來(lái)越低。

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

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

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

2.線性階O(n)

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

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

在while循環(huán)里面，每次都將i乘以2，乘完之后，i距離n就越來(lái)越近了。我們?cè)囍蠼庖幌?，假設(shè)循環(huán)x次之后，i就大于2了，此時(shí)這個(gè)循環(huán)就退出了，也就是說(shuō)2的x次方等于n，那么x = log2^n 也就是說(shuō)當(dāng)循環(huán)log2^n次以后，就結(jié)束，因此這個(gè)代碼的時(shí)間復(fù)雜度為：O(log)

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

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

5. 平方階O(n2)

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

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

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

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

二、空間復(fù)雜度

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

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

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

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

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

它的空間復(fù)雜度s(n)=O(1)

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

有循環(huán)，但沒(méi)有再分配新的空間，因此，這段代碼的空間復(fù)雜度主要看第一行即可，即 S(n) = O(n)。