正式工作也有3年的時間了，想要寫出更加優雅的代碼。

所以最近在刷leetcode補充數據結構和演算法方面的知識。

學校里雖然學過，但是僅僅是有個大概的認識。只有實際工作過幾年以後，才會明白數據結構和演算法的重要性。

如果是通信專業出身的同學，或者是硬體出身的同學一定知道：對於一個信號，我們可以從時域和頻域兩個方面去分析。

那麼計算機科學或者說軟體開發中的演算法怎麼去分析呢？ 有兩個衡量優劣的維度：時間複雜度和空間複雜度。

• 時間複雜度：執行當前演算法所消耗的’時間’。
• 空間複雜度：執行當前演算法所佔用的內存。

在這邊博文中，我們來好好分析一下時間複雜度。

• 時間複雜度真的是計算’時間’嗎？
• 時間複雜度公式：大O符號表示法
• 常見時間複雜度類型及代碼分析
  • 常數型O(1)
  • 對數型O(log n)
  • 線性型O(n)
  • 線性對數型O(n log n)
  • 平方型O(n^2)、立方型O(n^3)、K次方型O(n^k)
  • 平方底指數型O(2^n)、立方底指數型O(3^n)、K次底指數型O(k^n)
  • 階乘型O(n!)
• 如何理解斐波那契數列的時間複雜度O(2^N)?
• 如何理解階乘型時間複雜度O(n!)？
• 參考資料

時間複雜度真的是計算’時間’嗎？

把演算法的執行時間當做時間複雜度？

這種方式是最為直觀也是最容易想到的方式。

但是有一個問題，那就是代碼在不同性能的機器上運行，以及在不同的狀態下運行，會呈現出完全不同的運行時間。 比如說我有一台內存為32GB內存的mbp，還有一台8GB的台式機，假設其它的硬體條件比如cpu，主板以及機器負載狀態一致。通常情況下，32GB的內存要比8GB的內存運行更快。而且這種理想狀態下的只有單一變數的狀態也是很難做到的。

所以不能通過計算演算法的消耗時間作為時間複雜度。

那我們通常所說的’時間’複雜度中的’時間’到底是指什麼呢？

聰明的前輩們想到了一種方式：大O表示法。

大O表示法內部有非常複雜的數學計算邏輯，我們偷個懶，不去證明公式，把公式用好就很厲害了。

為什麼不去證明一下或者演算一遍？ 我在大一曾經上過一門叫做高等代數的課，有道題目叫做：請證明1+1=2。

看到這個題目應該知道為什麼不深究大O表示法背後的數學了吧。

時間複雜度公式：大O符號表示法

T(n) = O(f(n))

• f(n)是指每行代碼執行次數之和
• f(n)可以是這些值：1，log n，n，nlog n，n^2，n^3，n^k，2^n，n!
• f(n)與O正相關
• O(f(n))可以是這些值：O(1)，O(log n)，O(n)，O(nlog n)，O(n^2)，O(n^3)，O(n^k)，O(2^n)，O(n!)
• 大O表示法實際表示的是代碼執行時間的增長變化趨勢，不是真實的運行時間，是一種趨勢預估
• 大O表示法中的f(n)是近似值。很多時候不會完全是1，log n，n，nlog n，n^2，n^3，n^k，2^n，n!這些完整的值。例如斐波那契數列的真實時間複雜度為O(2^N-1)，由於N->∞，所以可以近似為O(2^N)。

更多的斐波那契數列時間複雜度的分析可以查看下文中的：如何理解斐波那契數列的時間複雜度O(2^N)?

常見時間複雜度類型及代碼分析

理論扯了一大堆了，到精彩絕倫的Show me the code環節了。 先來看一張大O複雜度曲線圖。

以下時間複雜度根據最佳->較好->一般->較差->糟糕的順序排列。

• 常數型O(1)
• 對數型O(log n)
• 線性型O(n)
• 線性對數型O(n log n)
• 平方型O(n^2)、立方型O(n^3)、K次方型O(n^k)
• 平方底指數型O(2^n)、立方底指數型O(3^n)、K次底指數型O(k^n)
• 階乘型O(n!)

常數型O(1)

• 常見於賦值和引用等簡單操作
• 演算法消耗不隨變數增長而增長，性能最佳
• 無論代碼執行多少行，即使有幾千幾萬行，時間複雜度都為O(1)
• 實際開發過程中，一次遞歸的時間複雜度也為O(1)。因為O(1^n)無論n為多少都為O(1)

let i = 0;
let j = 9;
i++;
j--;
let k = i + j;

代碼分析： i為1，j為10，k為11。 時間複雜度為O(1)。

對數型O(log n)

• 常用代碼執行次數為x，n為目標數字。符合2^x=n，推導出x=log2(n)（log n）的情況
• 演算法消耗隨n的增長而增長，性能較好

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

代碼分析： i為128。 n為100，時間複雜度為O(log2(100))。 因為Math.log2(100)≈6.64，所以最終的時間複雜度為O(6.65)。

線性型O(n)

• 常見於一次for循環，while循環
• 演算法消耗隨n的增長而增長，性能一般
• 無論n值有多大，即使是Inifinity，時間複雜度都為O(n)

let n = 100;
let j = 0;
for(let i = 0;i<n;i++){
    j = i;
}

代碼分析： i為100，j為99。 n為100，時間複雜度為O(100)。

線性對數型O(n log n)

• 常用於一個對時間複雜度為O(log2(n))的代碼執行一個n次循環
• 演算法消耗隨n的增長而增長，性能較差

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

代碼分析： i為128。 m為100，n為100，時間複雜度為O(m log2(n))。 因為100* Math.log2(100)≈664.39，所以最終的時間複雜度為O(664.39)。

平方型O(n^2)、立方型O(n^3)、K次方型O(n^k)

• 最常見的演算法時間複雜度，可用於快速開發業務邏輯
• 常見於2次for循環，或者3次for循環，以及k次for循環
• 演算法消耗隨n的增長而增長，性能糟糕
• 實際開發過程中，不建議使用K值過大的循環，否則代碼將非常難以維護

let n = 100
let v = 0;
for(let i =0;i<n;i++){
    for(let j = 0; j<n; j++){
        v = v+j+i;
    }
}

代碼分析： v為990000，i為100，j為100. n為100，時間複雜度為O(100^2)。 也就是O(10000)。

立方型O(n^3)、K次方型O(n^k)和平方型O(n^2)類似，無非是多了幾次循環。

// 立方型O(n^3)
for(let i =0;i<n;i++){
    for(let j = 0; j<n; j++){
        for(let m = 0; m<n; m++){

        }
    }
}
// K次方型O(n^k)
for(let i =0;i<n;i++){
    for(let j = 0; j<n; j++){
        for(let m = 0; m<n; m++){
            for(let p = 0; p<n; p++){
                ... // for循環繼續嵌套下去，k值不斷增大
            }
        }
    }
}

平方底指數型O(2^n)、立方底指數型O(3^n)、K次底指數型O(k^n)

• 常見於2次遞歸的情況，3次遞歸以及k次遞歸的情況
• 演算法消耗隨n的增長而增長，性能糟糕
• 實際開發過程中，k為1時，一次遞歸的時間複雜度為O(1)。因為O(1^n)無論n為多少都為O(1)。

斐波那契數列（兔子數列、黃金分割數列）：1、1、2、3、5、8、13、21、34··· 題目：leetcode 509 斐波那契數

題解：509.斐波那契數

/**
 * @param {number} N
 * @return {number}
 */
var fib = function (N) {
  /**
   * 解法1: 遞歸
   * 性能:  88ms 34.2MB
   * 時間複雜度：O(2^N)
   */
  if (N <= 1) return N;
  return fib(N - 1) + fib(N - 2);
};

假設N等於100。 代碼分析： 結果為 xxx。 因為瀏覽器直接卡死。nodejs中也運行不出來。 具體原因則是2的100次方真的太大了。算不來。 N為100，時間複雜度為O(2^100)。 因為Math.pow(2, 100)= 1.2676506002282294e+30，所以最終的時間複雜度為O(1.2676506002282294e+30)。大到爆表。

立方底指數型O(3^n)、K次底指數型O(k^n)與平方底指數型O(2^n)類似，只不過基數變為了3和k。

O(Math.pow(3, n))
O(Math.pow(k, n))

假設n為100，假設k為5。 Math.pow(3, n)為5.153775207320113e+47。 Math.pow(5, n)為7.888609052210118e+69。 時間複雜度也是巨高，真的是指數爆炸 。

更多的斐波那契數列時間複雜度O(2^N）的分析可以查看下文中的：如何理解斐波那契數列的時間複雜度O(2^N)?

階乘型O(n!)

• 極其不常見
• 演算法消耗隨n的增長而增長，性能糟糕

function nFacRuntimeFunc(n) {
  for(let i=0; i<n; i++) {
      nFacRuntimeFunc(n-1);
  }
}

階乘型O(n!)的時間複雜度按照(n!+(n-1)!+(n-2)!+ ··· + 1) +((n-1)!+(n-2)!+ ··· + 1)+ ··· 的方式去計算。 注意哦，這裡是多個階乘的和。不僅僅是n * (n-1) * (n-2) * (n-3)···1。 假設n從0到10，它的演算法複雜度O(n!)依次為1，4，15，64，325，1956，13699，109600，986409，9864100··· 為了和上文中的其它演算法複雜度做比較，n為100時是多少呢？ O(2^n)為10才是1024，n為100時O(2^n)直接瀏覽器卡死了。 O(n!)才為10就接近1000萬了，真要是n設置成100，計算到機器燒了也計算不出吧。 所以n為100時的O(n!)就不要想了，龐大到恐怖的一個數字。

更多的階乘型時間複雜度O(n!)的分析可以查看下文中的：如何理解階乘型演算法複雜度O(n!)？

如何理解斐波那契數列的時間複雜度O(2^N)?

O(2^N)

• Math.pow(base, ex)，2個遞歸所以base是2。
• N的話是因為N->∞，但其實真正是O(2^(N-1))。

/**
 * @param {number} N
 * @return {number}
 */
var fib = function (N) {
    /**
     * 解法1: 遞歸
     * 性能:  88ms 34.2MB
     */
    console.log('foo');
    if (N <= 1) return N;
    return fib(N - 1) + fib(N - 2)
};

N列印foo數O(2^N)11O(2^0)22^1 + 1O(2^1)32^2 + 1O(2^2 )42^3 + 1O(2^3 )52^4 + 1O(2^4 )

通過上表我們分析得到： 如果包含1的話，嚴格來講時間複雜度是O(2^(N-1))。 如果從N>1開始計算，時間複雜度確實是O(2^N)。 斐波那契數列非常長，N->∞，因此可以將斐波那契數列的時間複雜度直接看做是O(2^N)。

如何理解階乘型時間複雜度O(n!)？

O(N!)

我們把上面的代碼改造一下，增加一個count用來統計O(n!)。

let count = 0;
function nFacRuntimeFunc(n) {
  for(let i=0; i<n; i++) {
      count++;
      nFacRuntimeFunc(n-1);
  }
}

階乘型O(n!)的時間複雜度按照(n!+(n-1)!+(n-2)!+ ··· + 1) +((n-1)!+(n-2)!+ ··· + 1) 的方式去計算。 注意哦，這裡是多個階乘的和。不僅僅是n * (n-1) * (n-2) * (n-3)···1。 上述示例中的count即為複雜度的值。

n多次n! + (n-1)! + ··· + 1!countO(n!)111O(1)2(2!+1!) +(1!)4O(4)3(3!+(2!+1!)+1!)+((2!+1!)+1!)+(1!)15O(15)4…64O(64)5…325O(325)6…1956O(1956)7…13699O(13699)8…109600O(109600)9…986409O(986409)10…9864100O(9864100)

快看看這個表格吧，n為10的時候O(n!)達到了O(9864100)，接近了O(一千萬)。這種演算法的性能真的是糟糕到極致了。