摘要：第三段，時間復雜度。五空間復雜度分析空間復雜度的話和時間復雜度類似推算。

時間復雜度和空間復雜度，我們在大學里的算法與數據結構課程中已經學習過，這回根據項目工作中整理一下，這個估計只是一個粗略的估計分析，并不是一個準確的估計分析。

1、學習時間復雜度和空間復雜度是很有必要的，這個屬于算法與數據結構的范疇，學這個是為了解決代碼中的“快”和“省”的問題。這樣才能使你的代碼運行效率更高，占用空間更小。代碼執行效率需要通過復雜度分析。

2、數據規模的大小會影響到復雜度分析。比如排序，如果是一個有序的數組，執行效率會更高；如果數據量很少的時候，這個算法看不出性能上差別。

3、比如說不同物理機環境不一樣，比如i3，i5，i7的cpu等等，運行內存1G，2G，4G，8G等等；時間上肯定有差別。

我們來看個簡單的例子，一個循環累加器。

function total(n) { 
      var sum = 0;   //t
      for (var i = 0; i < n; i++) {   // nt
        sum += i;   //nt
      } 
      return sum;  // t
    } 

分析：假設每一行代碼執行耗時都一樣，為t，這樣整個代碼總執行時間為（t+nt+nt+t）=(2n+2)t。

我們再來看一個栗子：

function total(n) { 
      var sum = 0;      // t
      for (var i = 0; i < n; i++) {   //nt
        for (var j = 0; j < n; j++) {     //n*n*t
          sum = sum + i + j;     //n*n*t
        }
      }
      return sum;      //t
    }

分析：假設每一行代碼執行耗時都一樣，為t，這樣整個代碼總執行時間為（t+nt+nnt2+t）=(2nn+n+2)t。

從數學角度來看，我們可以得出個規律：代碼的總執行時間 T(n) 與每行代碼的執行次數成正比.

所以上邊兩個函數的執行時間可以標記為 T(n) = O(2n+2) 和 T(n) = O(2n*n+n+2)。這就是大 O 時間復雜度表示法，它不代表代碼真正的執行時間，而是表示代碼隨數據規模增長的變化趨勢，簡稱時間復雜度。

而且當 n 很大時，我們可以忽略常數項，只保留一個最大量級即可。所以上邊的代碼執行時間可以簡單標記為 T(n) = O(n) 和 T(n) = O(n2)。

在分析的時候，只需要關心哪個代碼塊循環次數最多的那段代碼，比如說剛才的第一個例子，循環最多的代碼塊是這兩行，循環都是n次。

for (var i = 0; i < n; i++){
    sum += i;
}

執行了n次，所以事件復雜度就是O(n)。

function total(n) { 
      // 第一個 for 循環
      var sum1 = 0; 
      for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
          sum1 = sum1 + i + j; 
        }
      }
      // 第二個 for 循環
      var sum2 = 0;
      for(var i=0;i<1000;i++) {
        sum2 = sum2 + i;
      }
      // 第三個 for 循環
      var sum3 = 0;
      for (var i = 0; i < n; i++) {
        sum3 = sum3 + i;
      }
      return {sum1:sum1, sum2: sum2, sum3:sum3}
    }

分別分析每一段循環時間復雜度，取他們最大的量級決定整段代碼復雜度。

第一段，時間復雜度 O(n2)。

第二段，時間復雜度可以忽略，循環執行了 1000 次，是個常數量級，盡管對代碼的執行時間會有影響，但是當 n 無限大的時候，就可以忽略。

第三段，時間復雜度O(n)。

綜上所述，所以上述代碼的時間復雜度為 O(n2)。

舉個例子：

 function f(i) {
      var sum = 0;
      for (var j = 0; j < i; j++) {
        sum += i;
      }
      return sum;
    }
    function total(n) {
      var res = 0;
      for (var i = 0; i < n; i++) {
        res = res + f(i); // 調用 f 函數
      }
    }

分析一下：total方法時間復雜度O(n)，f方法的時間復雜度O(n)。

所以整段代碼的時間復雜度O(n2)。

最高量級的復雜度，效率是遞減的

如上圖可以粗略的分為兩類，多項式量級和非多項式量級。其中，非多項式量級只有兩個：O(2n) 和 O(n!) 對應的增長率如下圖所示

當數據規模 n 增長時，非多項式量級的執行時間就會急劇增加，所以，非多項式量級的代碼算法是非常低效的算法。

O(1) 只是常量級時間復雜度表示法，并不是代碼只有一行，舉個例子：

function total() {
      var sum = 0;
      for(var i=0;i<100;i++) {
        sum += i;
      }
      return sum;
    }

雖然有這么多行，即使 for 循環執行了 100 次，但是代碼的執行時間不隨 n 的增大而增長，所以這樣的代碼復雜度就為 O(1)。

（1）對數階時間復雜度的常見代碼如下:

 function total1(n) {
      var sum = 0;
      var i = 1;
      while (i <= n) {
        sum += i;
        i = i * 2;
      }
    }
    function total2(n) {
      var sum = 0;
      for (var i = 1; i <= n; i = i * 2) {
        sum += i;
      }
    }

上面函數total1和total2有一個相同點：變量 i 從 1 開始取值，每循環一次乘以 2，當大于 n 時，循環結束。

所以真正循環了x次。2x =n;，所以 x = log2n。

所以上面兩個函數時間復雜度都是 O(log2n)。

（2）我們在舉個例子：

 function total1(n) {
      var sum = 0;
      var i = 1;
      while (i <= n) {
        sum += i;
        i = i * 3;
      }
    }
    function total2(n) {
      var sum = 0;
      for (var i = 1; i <= n; i = i * 3) {
        sum += i;
      }
    }

同理可知：這兩個函數的時間復雜度為 O(log3n) 。

由于我們可以忽略常數，也可以忽略對數中的底數，所以在對數階復雜度中，統一表示為 O(logn)；那 O(nlogn) 的含義就很明確了，時間復雜度 為O(logn) 的代碼執行了 n 次。

舉個例子：

 function total(m,n) {
      var sum1 = 0;
      for (var i = 0; i < n; i++) {
        sum1 += i;
      }
      var sum2 = 0;
      for (var i = 0; i < m; i++) {
        sum2 += i;
      }
      return sum1 + sum2;
    }

因為我們無法評估 m 和 n 誰的量級比較大，所以就不能忽略掉其中一個，這個函數的復雜度是有兩個數據的量級來決定的，所以此函數的時間復雜度為 O(m+n)；那么 O(m*n) 的時間復雜度類似。

空間復雜度的話和時間復雜度類似推算。 所謂空間復雜度就是表示算法的存儲空間和數據規模之間的關系。

舉個例子：

function initArr(n) {
      var arr = [];
      for (var i = 0; i < n; i++) {
        arr[i] = i;
      }
    }

時間復雜度的推算，忽略掉常數量級，每次數組賦值都會申請一個空間存儲變量，所以此函數的空間復雜度為 O(n)。

常見的空間復雜度只有 O(1)、O(n)、O(n2)。其他的話很少會用到。

function total(n) {
      var sum = 0;
      for (var i = 1; i <= n; i++) {
        sum += i;
      }
      return sum;
    }

這段代碼我們很容易知道時間復雜度 O(n)。

但是我想把復雜度降一降，降低到常數階O(1)。

其實求和怎么求呢？等比數列，直接用公式，這就說明了數學好的人，算法應該高level點。

function total(n) {
      var sum = n*(n+1)/2
      return sum;
    }

上面函數的時間復雜度僅僅為 O(1)，在數據規模比較龐大的時候，下面的函數是不是明顯比上面的函數運算效率更高呢。

分析算法執行效率與數據規模之間的增長關系，可以粗略的表示，越高階復雜度的算法，執行效率越低。

復雜度學習之后，有時候可以避免寫出效率低的代碼。