1. 博客背景

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

2. 復雜度的表示方式

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

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

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

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

f(n)表示的是代碼執行的總次數

舉個例子

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

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

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

然后之前說了時間復雜度看的是一個代碼執行的時間的趨勢， 所以說在N，也就是規模比較大的時候，那些常量是起不到決定性的作用的，所以這個時候我們忽略這些常量，這里的例子是一個單段的代碼，這里只看最大量級的循環就可以了

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

大家可以想想一下數據中平方的曲線圖

3. 時間復雜度

3.1 時間復雜度的定義

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

3.2 幾種常見的時間復雜度

最簡單的O(n)

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

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

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

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

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

T(n) = O(n²)

上邊的例子已經說了一個了兩層循環的那種，在舉一個時間復雜度多塊代碼的情況時間復雜度的計算方式

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); // 這里是重點 }}

在上邊的代碼種第二段代碼里邊調用了第一段代碼，所以說在這個代碼里邊是

go：（1+n）

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

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