同一個問題可以用不同的演算法實現，而演算法是有優劣之分的。我們經常需要對演算法進行分析，以便於選擇合適的演算法和改進演算法。

通常我們從兩個維度來描述演算法的優劣：程序代碼的執行時間和代碼佔用的內存空間。兩者分別叫做演算法的時間複雜度和演算法的空間複雜度，合稱演算法的複雜度。

時間複雜度和空間複雜度可以反映出演算法的效率。

時間複雜度

時間複雜度用來衡量演算法的執行時間，用 O 表示。

事實上，代碼執行時所耗費的時間，只有在機器上運行後才能知道，從理論上是不能算出來的。為了方便，我們用執行到的語句數量來表示執行的時間。語句執行次數越多，代碼所耗費的時間越長。

舉些栗子。

function isEven(num) {

let isEven = num % 2 === 0

return isEven

}

這是一個判斷一個數是否為偶數的函數，運行時執行到了兩條語句，它的時間複雜度為 O(2)。

function sum(arr) {

let total = 0

for (let i = 0; i < arr.length; i++) {

total += arr[i]

}

return total

}

這是一個求和的函數，它的時間複雜度取決於參數數組的大小。演算法的執行時間往往取決於要處理的數據的大小，通常我們把要處理的數據的大小叫做問題的規模，用 n 表示。在這個示例中，n 就是數組的長度。

所以，這個求和演算法的複雜度為 O(3n + 3)。

說實話，計算這個複雜度還挺麻煩的。很多時候，我們不需要計算得那麼精確，我們只需要知道演算法的大致時間就好了。對於計算機來說，多執行幾條命令在時間上效率並沒有提高多少。

為了方便計算和比較不同的時間複雜度，我們需要對結果去掉低階項，去掉常數項，去掉高階項的常參。這話涉及到多項式的知識，可能比較難理解，可以看下面示例。

O(3) = O(99999) = O(1)

O(2n + 4) = O(n + 999) = O(n)

O(2n^2) = O(3n^2 + 8) = O(8n^2 + 4n + 7) = O(n^2)

O(n^3 + 2n^2) = O(n^3)

這樣的話，計算時間複雜度就方便很多了。

如果一個演算法的時間複雜度是個常數，即隨著問題的規模（n）的增大，它的時間複雜度不變，那麼演算法的時間複雜度為 O(1)。

let sum = 0

for (let i = 1; i <= 100; i++) {

sum += sum

}

比如這個求 1 + 2 + 3 + ... + 100 的演算法，它的時間複雜度是 O(1)。因為它的時間複雜度是個常數，大概 300 多，我們不需要知道具體的值是多少。

function sort(arr) {

for (let out = 0; out < arr.length - 1; out++) {

for (let j = 0; j < arr.length - out - 1; j++) {

if (arr[j] > arr[j + 1]) {

let tmp = arr[j]

arr[j] = arr[j + 1]

arr[j + 1] = tmp

}

}

}

return arr

}

這是冒泡排序法，用到了二重循環，每重循環的次數大概為 n（arr.length），因此它的時間複雜度為 O(n^2)。

一個簡單的判斷時間複雜度的方法就是，如果演算法中只用到了一重循環，並且循環的次數大致為 n，那麼演算法的時間複雜度為 O(n)；如果演算法中用到了二重循環，每重循環的次數大概為 n，因此它的時間複雜度為 O(n^2)；以此類推。

我們再來看一個函數。

function find(arr, num) {

for (let i = 0; i < arr.length; i++) {

if (arr[i] === num) {

return true

}

}

return false

}

這是一個判斷數組中是否存在一個目標數的函數。它的執行時間更是不確定的。如果要查找的數在數組的第一個，那麼它只需要執行幾條語句能完成了。如果目標數是數組的最後一個，或者在數組中不存在，那麼要執行的時間就很久了。通常我們在討論演算法的時間複雜度時，指的是在最壞的情況下，演算法的時間複雜度。因此，這個演算法的時間複雜度是 O(n)。

我們再來看一個例子：

for (let i = 1; i <= n; i *= 2) {

console.log(i)

}

在這個示例中，i 是指數增長的，我們假設執行的次數為 m，那麼 2^m = n，即 m = logx2(n)。因此，時間複雜度為 log2(n)。

常見的時間複雜度

常見的時間複雜度有下面這些（按數量級遞增排列）：

常數階O(1) -> 對數階O(log2n) -> 線性階O(n) -> 線性對數階O(nlog2n) -> 平方階O(n^2) -> 立方階O(n^3) -> k次方階O(n^k) -> 指數階O(2^n)。

空間複雜度

空間複雜度用來表示演算法的執行時所需存儲空間的度量。

計算的方法和時間複雜度類似，這裡不再贅述。

比如上面的冒泡排序法，空間複雜度為 O(1)。

應用

前面說過，我們經常對演算法進行分析，以便於選擇合適的演算法和改進演算法。

在改進演算法方面，如果程序注重運行時間，有時我們會選擇犧牲空間複雜度的方式來換取演算法的時間複雜度。

比如 LeetCode 的第一道演算法題（有興趣自行百度 LeetCode Two Sum），一般情況下我們採用雙重循環來做，時間複雜度為 O(n)，這樣的話代碼的執行時間就會超出限制的時間。所以只好採用一重循環 + Map 的思路來做。這是一個典型的「以空間換時間的」的例子。

熟悉演算法複雜度的概念，也可以幫助我們選擇適合的演算法。

比如我們知道了冒泡排序法的平均時間複雜度為 O(n^2)，空間複雜度為 O(1)，快速排序法是的平均時間複雜度為 O(log2(n))，空間複雜度為 O(1)。那麼很顯然，當數據量比較大的時候，快速排序法明顯會比冒泡排序法更加高效。

當然，演算法複雜度並不是衡量演算法時唯一考慮的因素。很多時候，我們還需要考慮演算法是否容易實現、代碼可讀性等等。

就以上面的排序演算法來說。快速排序演算法不是穩定的，而冒泡排序是穩定的演算法，穩定性也是選擇排序演算法考慮的因素之一。

更多優質內容推薦：

2017優就業就業促進計劃：http://www.ujiuye.com/zt/jycj/?wt.bd=zdy35845tt

中公教育「勤工儉學計劃」，給你一個真正0元學習IT的機會！

http://www.ujiuye.com/zt/qgjx/?wt.bd=zdy35845tt

IT職業教育：http://xue.ujiuye.com/

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！