1. 博客背景

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

2. 復(fù)雜度的表示方式

之前有看過的，你可能會看到這么一串東西

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

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

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

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

舉個例子

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í)行了一次}

所以說上邊這段代碼是 1+n+n*n*2+1=2+n+2n²

也就是說 T(n) = O(f(2+n+2n²))

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

所以最后的這個代碼的時間復(fù)雜度是T(n) = O(n²)

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

3. 時間復(fù)雜度

3.1 時間復(fù)雜度的定義

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

3.2 幾種常見的時間復(fù)雜度

最簡單的O(n)

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

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

當(dāng)然還有個更簡單的O(1)

function total(n) {console.log(1)}

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

T(n) = O(n²)

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

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ào)用了第一段代碼，所以說在這個代碼里邊是

go：（1+n）

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

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

3.3 多塊代碼的時間復(fù)雜度

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

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

比如說

    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)，通過上邊的例子我們已經(jīng)得知復(fù)雜度是
n²

下邊這塊代碼，是n

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

3.4 對數(shù)階和相加情況

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

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

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

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

還有一些其他的情況比如時間復(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) }}

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

4. 空間復(fù)雜度

4.1 空間復(fù)雜度的定義

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

4.2 常見的空間復(fù)雜度

空間復(fù)雜度沒有時間復(fù)雜度那么復(fù)雜，常見的就那么幾種

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

如果有，那么請打死。。。。

• O(1)

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

很簡單，O(1)

• O(n)

let arr =Array(n)

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

這里需要說明一下，這里沒有用循環(huán)，是因為只要不是在循環(huán)里邊不停的聲明變量，只改變值的話是不會層架空間復(fù)雜度的

• O(n²)

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

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

復(fù)雜度的優(yōu)化

再說優(yōu)化之前我先盜一張圖給大家看一下各個復(fù)雜度的曲線圖，方便大家有一個直觀的認(rè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é)不好，記得之前看到過一個等差數(shù)列的例子，想不到其他的性能優(yōu)化的例子

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

斐波那契，就是從第三項開始依次等于前兩項的和

斐波那契定義

function Fibonacci(n) {  if (n <= 1 ) {    return n;  } else {    return Fibonacci(n - 1) + Fibonacci(n - 2);  }}console.time('b')Fibonacci(????)console.timeEnd('b')

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

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

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，謝謝大家對武林網(wǎng)的支持。