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

時(shí)間復(fù)雜度和空間復(fù)雜度，我們?cè)诖髮W(xué)里的算法與數(shù)據(jù)結(jié)構(gòu)課程中已經(jīng)學(xué)習(xí)過，這回根據(jù)項(xiàng)目工作中整理一下，這個(gè)估計(jì)只是一個(gè)粗略的估計(jì)分析，并不是一個(gè)準(zhǔn)確的估計(jì)分析。

1、學(xué)習(xí)時(shí)間復(fù)雜度和空間復(fù)雜度是很有必要的，這個(gè)屬于算法與數(shù)據(jù)結(jié)構(gòu)的范疇，學(xué)這個(gè)是為了解決代碼中的“快”和“省”的問題。這樣才能使你的代碼運(yùn)行效率更高，占用空間更小。代碼執(zhí)行效率需要通過復(fù)雜度分析。

2、數(shù)據(jù)規(guī)模的大小會(huì)影響到復(fù)雜度分析。比如排序，如果是一個(gè)有序的數(shù)組，執(zhí)行效率會(huì)更高；如果數(shù)據(jù)量很少的時(shí)候，這個(gè)算法看不出性能上差別。

3、比如說不同物理機(jī)環(huán)境不一樣，比如i3，i5，i7的cpu等等，運(yùn)行內(nèi)存1G，2G，4G，8G等等；時(shí)間上肯定有差別。

我們來看個(gè)簡(jiǎn)單的例子，一個(gè)循環(huán)累加器。

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

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

我們?cè)賮砜匆粋€(gè)栗子：

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
    }

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

從數(shù)學(xué)角度來看，我們可以得出個(gè)規(guī)律：代碼的總執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比.

所以上邊兩個(gè)函數(shù)的執(zhí)行時(shí)間可以標(biāo)記為 T(n) = O(2n+2) 和 T(n) = O(2n*n+n+2)。這就是大 O 時(shí)間復(fù)雜度表示法，它不代表代碼真正的執(zhí)行時(shí)間，而是表示代碼隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，簡(jiǎn)稱時(shí)間復(fù)雜度。

而且當(dāng) n 很大時(shí)，我們可以忽略常數(shù)項(xiàng)，只保留一個(gè)最大量級(jí)即可。所以上邊的代碼執(zhí)行時(shí)間可以簡(jiǎn)單標(biāo)記為 T(n) = O(n) 和 T(n) = O(n2)。

在分析的時(shí)候，只需要關(guān)心哪個(gè)代碼塊循環(huán)次數(shù)最多的那段代碼，比如說剛才的第一個(gè)例子，循環(huán)最多的代碼塊是這兩行，循環(huán)都是n次。

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

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

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

分別分析每一段循環(huán)時(shí)間復(fù)雜度，取他們最大的量級(jí)決定整段代碼復(fù)雜度。

第一段，時(shí)間復(fù)雜度 O(n2)。

第二段，時(shí)間復(fù)雜度可以忽略，循環(huán)執(zhí)行了 1000 次，是個(gè)常數(shù)量級(jí)，盡管對(duì)代碼的執(zhí)行時(shí)間會(huì)有影響，但是當(dāng) n 無限大的時(shí)候，就可以忽略。

第三段，時(shí)間復(fù)雜度O(n)。

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

舉個(gè)例子：

 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); // 調(diào)用 f 函數(shù)
      }
    }

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

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

最高量級(jí)的復(fù)雜度，效率是遞減的

如上圖可以粗略的分為兩類，多項(xiàng)式量級(jí)和非多項(xiàng)式量級(jí)。其中，非多項(xiàng)式量級(jí)只有兩個(gè)：O(2n) 和 O(n!) 對(duì)應(yīng)的增長(zhǎng)率如下圖所示

當(dāng)數(shù)據(jù)規(guī)模 n 增長(zhǎng)時(shí)，非多項(xiàng)式量級(jí)的執(zhí)行時(shí)間就會(huì)急劇增加，所以，非多項(xiàng)式量級(jí)的代碼算法是非常低效的算法。

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

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

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

（1）對(duì)數(shù)階時(shí)間復(fù)雜度的常見代碼如下:

 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;
      }
    }

上面函數(shù)total1和total2有一個(gè)相同點(diǎn)：變量 i 從 1 開始取值，每循環(huán)一次乘以 2，當(dāng)大于 n 時(shí)，循環(huán)結(jié)束。

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

所以上面兩個(gè)函數(shù)時(shí)間復(fù)雜度都是 O(log2n)。

（2）我們?cè)谂e個(gè)例子：

 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;
      }
    }

同理可知：這兩個(gè)函數(shù)的時(shí)間復(fù)雜度為 O(log3n) 。

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

舉個(gè)例子：

 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;
    }

因?yàn)槲覀儫o法評(píng)估 m 和 n 誰的量級(jí)比較大，所以就不能忽略掉其中一個(gè)，這個(gè)函數(shù)的復(fù)雜度是有兩個(gè)數(shù)據(jù)的量級(jí)來決定的，所以此函數(shù)的時(shí)間復(fù)雜度為 O(m+n)；那么 O(m*n) 的時(shí)間復(fù)雜度類似。

空間復(fù)雜度的話和時(shí)間復(fù)雜度類似推算。 所謂空間復(fù)雜度就是表示算法的存儲(chǔ)空間和數(shù)據(jù)規(guī)模之間的關(guān)系。

舉個(gè)例子：

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

時(shí)間復(fù)雜度的推算，忽略掉常數(shù)量級(jí)，每次數(shù)組賦值都會(huì)申請(qǐng)一個(gè)空間存儲(chǔ)變量，所以此函數(shù)的空間復(fù)雜度為 O(n)。

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

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

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

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

其實(shí)求和怎么求呢？等比數(shù)列，直接用公式，這就說明了數(shù)學(xué)好的人，算法應(yīng)該高level點(diǎn)。

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

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

分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系，可以粗略的表示，越高階復(fù)雜度的算法，執(zhí)行效率越低。

復(fù)雜度學(xué)習(xí)之后，有時(shí)候可以避免寫出效率低的代碼。