摘要：以上是我對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度的一些認(rèn)識(shí)，有不足或者不對(duì)的地方，希望指出來(lái)

今天有同事在檢查代碼的時(shí)候，由于函數(shù)寫(xiě)的性能不是很好，被打回去重構(gòu)了，細(xì)思極恐，今天和大家分享一篇用js講解的時(shí)間復(fù)雜度和空間復(fù)雜度的博客

之前有看過(guò)的，你可能會(huì)看到這么一串東西

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

這個(gè)叫做大O表示法，其中的T代表的是算法需要執(zhí)行的總時(shí)間

S表示的算法需要的總空間

f(n)表示的是代碼執(zhí)行的總次數(shù)

舉個(gè)例子

function go(n) { 
  var item = 0;      // 這里執(zhí)行了一次
  for (var i = 0; i < n; i++) {   //這里執(zhí)行了N次
    for (var j = 0; j < n; j++) {     //這里執(zhí)行了n*n次
      item = item + i + j;     //這里執(zhí)行了n*n次
    }
  }
  return item;  //這里執(zhí)行了一次
}

所以說(shuō)上邊這段代碼是 1+n+n*n*2+1=2+n+2n2

也就是說(shuō) T(n) = O(f(2+n+2n2))

然后之前說(shuō)了時(shí)間復(fù)雜度看的是一個(gè)代碼執(zhí)行的時(shí)間的趨勢(shì)， 所以說(shuō)在N，也就是規(guī)模比較大的時(shí)候，那些常量是起不到?jīng)Q定性的作用的，所以這個(gè)時(shí)候我們忽略這些常量，這里的例子是一個(gè)單段的代碼，這里只看最大量級(jí)的循環(huán)就可以了

所以最后的這個(gè)代碼的時(shí)間復(fù)雜度是T(n) = O(n2)

大家可以想想一下數(shù)據(jù)中平方的曲線圖

首先什么是時(shí)間復(fù)雜度，時(shí)間復(fù)雜度這個(gè)定義如果在之前沒(méi)有接觸過(guò)的話，你可能會(huì)認(rèn)為他代表的是一個(gè)代碼執(zhí)行的時(shí)間，其實(shí)不然，算法的時(shí)間復(fù)雜度就是說(shuō)一個(gè)算法的執(zhí)行時(shí)間根據(jù)數(shù)據(jù)規(guī)模增長(zhǎng)的一個(gè)趨勢(shì)，并不是說(shuō)代碼執(zhí)行的具體時(shí)間

最簡(jiǎn)單的O(n)

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

通俗易懂，這段代碼的執(zhí)行時(shí)間完全由N來(lái)控制，所以說(shuō)T(n) = O(n)

當(dāng)然還有個(gè)更簡(jiǎn)單的O(1)

function total(n) {

  console.log(1)

}

無(wú)論怎么樣，這段函數(shù)不受任何參數(shù)影響，代碼走一遍就完事，這種的代碼用T(n) = O(1) 表示

T(n) = O(n2)

上邊的例子已經(jīng)說(shuō)了一個(gè)了兩層循環(huán)的那種，在舉一個(gè)時(shí)間復(fù)雜度多塊代碼的情況時(shí)間復(fù)雜度的計(jì)算方式

function go(i) {
  var sum = 0;
  for (var j = 0; j < i; j++) {
    sum += i;
  }
  return sum;
}
function main(n) {
  var res = 0;
  for (var i = 0; i < n; i++) {
    res = res + go(i); // 這里是重點(diǎn)
  }
}

在上邊的代碼種第二段代碼里邊調(diào)用了第一段代碼，所以說(shuō)在這個(gè)代碼里邊是

go：（1+n）

在main函數(shù)里邊的時(shí)候是(1+n*go)=(1+n+n*n)

所以最后的時(shí)間復(fù)雜度是T(n) = O(n2)

上邊距離說(shuō)明的T(n) = O(n2) ，是一個(gè)函數(shù)在另一個(gè)函數(shù)里邊被調(diào)用，這種情況是被把兩個(gè)函數(shù)的時(shí)間復(fù)雜度相乘。

還有另外一種情況，就是說(shuō)在一個(gè)函數(shù)里邊有多塊代碼，但是并沒(méi)有被相互調(diào)用，那么這種情況的時(shí)候，我們只需要取復(fù)雜度最大的代碼塊就可以了

比如說(shuō)

        function go(n) { 

          for (var i = 0; i < n; i++) {
            for (var j = 0; j < n; j++) {
              console.log(1)
            }
          }


          for (var i = 0; i < n; i++) {
           console.log(2)
          }
        }
        

上邊這塊代碼中，第一塊代碼有兩層循環(huán)，通過(guò)上邊的例子我們已經(jīng)得知復(fù)雜度是
n2

下邊這塊代碼，是n

那么在這種情況的時(shí)候，當(dāng)N接近無(wú)限大的時(shí)候N是對(duì)n2起不到?jīng)Q定性作用的，所以上邊這塊代碼的時(shí)間復(fù)雜度就是取最大值的n2

var i = 1;
while (i <= n) {
        i = i * 10;
}

在這段代碼中，可以看到while里邊，作為判斷條件的i被每次*10，那么所以說(shuō)最后循環(huán)的次數(shù)并不是n次，而是說(shuō)十分之一n次，所以說(shuō)這個(gè)時(shí)候的時(shí)間復(fù)雜度是10i=n，
i=logn

所以得出結(jié)論就是時(shí)間復(fù)雜度是T(n)=O(logn)

然后還有一種情況就是通過(guò)改變的變量去增加循環(huán)次數(shù)的，同理是增加了時(shí)間復(fù)雜度

還有一些其他的情況比如時(shí)間復(fù)雜度相加

function go(m,n) {

  for (var i = 0; i < n; i++) {
    console.log(1)
  }

  for (var i = 0; i < m; i++) {
    console.log(2)
  }

}

請(qǐng)看上邊這一段，這段代碼里邊一個(gè)函數(shù)里邊有兩個(gè)循環(huán)，但是形參有兩個(gè)，我們現(xiàn)在無(wú)法得知n和m到底誰(shuí)大誰(shuí)小，所以說(shuō)這個(gè)時(shí)候代碼的時(shí)間復(fù)雜度是O(m+n)

上邊說(shuō)了那么一大堆的時(shí)間復(fù)雜度，相比各位已經(jīng)比較了解了，就名字來(lái)看，時(shí)間復(fù)雜度看的是代碼的執(zhí)行時(shí)間的趨勢(shì)，那么同理的，空間復(fù)雜度就是指的占用內(nèi)存的趨勢(shì)

空間復(fù)雜度沒(méi)有時(shí)間復(fù)雜度那么復(fù)雜，常見(jiàn)的就那么幾種

畢竟我感覺(jué)不會(huì)有人一直循環(huán)著各種花樣的聲明變量吧。。。

如果有，那么請(qǐng)打死。。。。

O(1)

let a = 1;
let b = 1;
let c = 1;
let d = 1;

很簡(jiǎn)單，O(1)

O(n)

let arr =Array(n)

看這句代碼，代碼中創(chuàng)建了一個(gè)n長(zhǎng)度的數(shù)組，很明顯數(shù)組的長(zhǎng)度根據(jù)n來(lái)決定，所以說(shuō)
O(n)

這里需要說(shuō)明一下，這里沒(méi)有用循環(huán)，是因?yàn)橹灰皇窃谘h(huán)里邊不停的聲明變量，只改變值的話是不會(huì)層架空間復(fù)雜度的

O(n2)

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

怎么樣，猛的一看這個(gè)代碼是不是很刺激，我覺(jué)得如果有這種情況的話，一般都會(huì)被亂棍打死了。。。

再說(shuō)優(yōu)化之前我先盜一張圖給大家看一下各個(gè)復(fù)雜度的曲線圖，方便大家有一個(gè)直觀的認(rèn)識(shí)

舉個(gè)比較簡(jiǎn)單的優(yōu)化的例子

console.time("a")
function go(n) {
      var item = 0;
      for (var i = 1; i <= n; i++) {
        item += i;
      }
      return item;
}
console.timeEnd("a")

console.time("b")
function go2(n) {
  var item = n*(n+1)/2
  return item;
}
console.timeEnd("b")

go(1000)
go2(1000)

大家可以打印一下看一下

希望大家原諒我數(shù)學(xué)不好，記得之前看到過(guò)一個(gè)等差數(shù)列的例子，想不到其他的性能優(yōu)化的例子

希望大家看完之后可以了解這些概念，有的時(shí)候這個(gè)東西真的很重要，找一個(gè)曲線比較高的例子

斐波那契，就是從第三項(xiàng)開(kāi)始依次等于前兩項(xiàng)的和

斐波那契定義

function Fibonacci(n) {
    if (n <= 1 ) {
        return n;
    } else {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

console.time("b")
Fibonacci(????)
console.timeEnd("b")

有興趣的可以試試打印一下，看看時(shí)間，不過(guò)大概50次的時(shí)候你得瀏覽器就應(yīng)該沒(méi)有響應(yīng)了，具體請(qǐng)往上看曲線圖。。。。

以上是我對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度的一些認(rèn)識(shí)，有不足或者不對(duì)的地方，希望指出來(lái)

 
    o(*￣▽￣*)ブ