前端數據結構—複雜度分析

• 2021 年 4 月 12 日
• 筆記
• 前端數據結構, 數據結構, 時間複雜度分析

為什麼需要複雜度分析

　　我們可以把程式碼跑一遍，然後通過一些工具來統計、監控就能得到演算法執行的時間和佔用的記憶體大小。為什麼還要做時間、空間複雜度分析呢？這種分析方法能比我實實在在跑一遍得到的數據更準確嗎？

　　首先，肯定的說這種評估演算法執行效率的方法是正確的。很多數據結構和演算法書籍還給這種方法起了一個名字，叫事後統計法。但是這種統計方法存在一定的局限性。

1、測試結果依賴測試的環境以及數據規模的影響

　　比如，我們拿同樣一段程式碼，再不同的機器以及不同的數據規模可能會有不同的結果。

2、掌握複雜度分析，將能編寫出性能更優的程式碼

所以我們需要一個不用具體的測試環境、測試數據來測試，就可以粗略地估計演算法的執行效率的方法，這就是我們需要的時間、空間複雜度分析方法。

大 O 複雜度表示法

　　演算法的執行效率，簡單的說就是程式碼執行的時間。但是怎麼樣在不運行程式碼的情況下，用「肉眼」得到一段程式碼的執行時間呢？這裡有段非常簡單的程式碼，求 1,2,3…n 的累加和。現在來估算一下這段程式碼的執行時間。

1 function countSum(n) {
2    let sum = 0;
3    console.log(n)
4    for (i = 0; i <= n; ++i) {
5      sum = sum + i;
6    }
7    return sum;
8  }

每行程式碼對應的 CPU 執行的個數、執行的時間都不一樣，所以只是粗略估計，我們可以假設每行程式碼執行的時間都一樣為 unit_time。在這個假設的基礎之上，這段程式碼的總執行時間是多少呢？

第 2、3 行程式碼分別需要 1 個 unit_time 的執行時間，第 4、5 行都運行了 n 遍，所以需要 2n * unit_time 的執行時間，所以這段程式碼總的執行時間就是 (2n+2) * unit_time。

儘管我們不知道 unit_time 的具體值，但是通過程式碼執行時間的推導過程，我們可以得到一個非常重要的規律，那就是所有程式碼的執行時間 T(n) 與程式碼的執行次數 f(n) 成正比。

我們可以把這個規律總結成一個公式，這個公式就是數據結構書上說的大O表示法。

我來具體解釋一下這個公式：

• T(n) 表示程式碼執行的時間
• n 表示數據規模的大小
• f(n) 表示程式碼執行的次數總和

　　因為這是一個公式，所以用 f(n) 來表示。公式中的 O，表示程式碼的執行時間 T(n) 與 f(n) 表達式成正比。

　　所以，上面例子中的 T(n) = O(2n+2)，這就是大 O 時間複雜度表示法。大 O 時間複雜度實際上並不具體表示程式碼真正的執行時間，而是表示程式碼執行時間隨數據規模增長的變化趨勢，所以，也叫作漸進時間複雜度（asymptotic time complexity），簡稱時間複雜度。

時間複雜度分析

分析大O一般的步驟如下：

1. 用常數1代替運行中的所有的加法常數 n + 2 + 3 + 4 等於 n + 1
2. 在修改後的運行次數函數中，只保留最高階項 如 n^3 + n^2 等於 n^3
3. 如果最高階項存在且不為1，則去掉與這個項相乘的常數 如 3n^2 等於 n^2

通過上面三個步驟可以總結出幾個方法

1. 只關注循環執行次數最多的一段程式碼

大 O 這種複雜度表示方法只是表示一種變化趨勢。通過上面的公式我們會忽略掉公式中的常量、低階、係數，只需要記錄一個最大階的量級。所以我們在分析一個演算法、一段程式碼的時間複雜度的時候，也只關注循環執行次數最多的那一段程式碼就可以了。這段核心程式碼執行次數的 n 的量級，就是整段要分析程式碼的時間複雜度。

2.加法法則：總複雜度等於量級最大的那段程式碼的複雜度

如果是很長的一個程式碼段，可以把他們拆分計算時間複雜度，然後再加起來

 1 function countSum(n) {
 2    let sum_1 = 0;
 3    console.log('計算：sum_1')
 4    for (let p = 0; p < 100; ++p) {
 5      sum_1 = sum_1 + p;
 6    }
 7 
 8    let sum_2 = 0;
 9    console.log('計算：sum_2')
10    for (let q = 0; q < n; ++q) {
11      sum_2 = sum_2 + q;
12    }
13  
14    let sum_3 = 0;
15    console.log('計算：sum_3')
16    for (let i = 0; i <= n; ++i) {
17      j = 1; 
18      for (let j = 0; j <= n; ++j) {
19        sum_3 = sum_3 +  i * j;
20      }
21    }
22  
23    return sum_1 + sum_2 + sum_3;
24  }

這個程式碼分為三部分，分別是求 sum_1、sum_2、sum_3。我們可以分別分析每一部分的時間複雜度，然後把相加，再取一個量級最大的作為整段程式碼的複雜度。

第一段的時間複雜度是多少呢？這段程式碼循環執行了 100 次，所以是一個常量的執行時間，跟 n 的規模無關。強調一下，即便這段程式碼循環 10000 次、100000 次，只要是一個已知的數，跟 n 無關，照樣也是常量級的執行時間。當 n 無限大的時候，就可以忽略。儘管對程式碼的執行時間會有很大影響，但是回到時間複雜度的概念來說，它表示的是一個演算法執行效率與數據規模增長的變化趨勢，所以不管常量的執行時間多大，我們都可以忽略掉。因為它本身對增長趨勢並沒有影響。

那第二段程式碼和第三段程式碼的時間複雜度應該很容易分析出來是 O(n) 和 O(n^2)。

綜合這三段程式碼的時間複雜度，我們取其中最大的量級。所以，整段程式碼的時間複雜度就為 O(n^2)。也就是說：總的時間複雜度就等於量級最大的那段程式碼的時間複雜度。

3.乘法法則：嵌套程式碼的複雜度等於嵌套內外程式碼複雜度的乘積

假設有一個嵌套的循環，我們把第一層循環叫T1,那麼T1(n)=O(f(n))，第二層循環叫T2，那麼T2(n)=O(g(n))，總共時間 T(n)=T1(n)*T2(n) = O(f(n))*O(g(n))= O(f(n) * g(n))

假設 T1(n) = O(n)，T2(n) = O(n^2)，則 T1(n) * T2(n) = O(n^3)。在具體的程式碼上，我們可以把乘法法則看成是嵌套循環

如上面計算sum_3的程式碼段 兩個循環為O(n^2)。

常見時間複雜度實例分析

O(1)

O(1) 只是常量級時間複雜度的一種表示方法，並不是指只執行了一行程式碼。比如這段程式碼，即便有 3 行，它的時間複雜度也是 O(1），而不是 O(3)。

1 const i = 8; 
2 const j = 6; 
3 const sum = i + j;

只要程式碼的執行時間不隨 n 的增大而增長，這樣程式碼的時間複雜度我們都記作 O(1)。或者說，一般情況下，只要演算法中不存在循環語句、遞歸語句，即使有成千上萬行的程式碼，其時間複雜度也是Ο(1)。

O(logn)

對數階時間複雜度非常常見，如

1 i=1;
2 while (i <= n) {
3   i = i * 2; 
4 }

根據說的複雜度分析方法，第三行程式碼是循環執行次數最多的。所以，我們只要能計算出這行程式碼被執行了多少次，就能知道整段程式碼的時間複雜度。從程式碼中可以看出，變數 i 的值從 1 開始取，每循環一次就乘以 2。當大於 n 時，循環結束。實際上變數 i 的取值就是一個等比數列。如果我把它一個一個列出來，就應該是這個樣子的：

 所以，我們只要知道 x 值是多少，就知道這行程式碼執行的次數了。通過 2x=n 求解 x 這個問題我們想高中應該就學過了，我就不多說了。x=log2n，所以，這段程式碼的時間複雜度就是 O(log2n)。

O(n)

O(n)級別有個非常顯著的特徵就，它會存在一個循環，且循環的次數是和n相關

1 function countSum (n) {
2   let sum = 0
3   for (let i = 0; i < n; i++) {
4     sum += i
5   }
6 }

O(n^2) 

O(n^2)級別的有雙重循環

function countSum (n) {
  let sum = 0
  for (let i = 0; i < n; i++) {
    sum += i
    for (let J = 0; J < n; i++) {
      // do some thing
   }
  }
}

不是所有的雙重循環都是n^2

1 function countSum (n, m) {
2   let sum = 0
3   for (let i = 0; i < n; i++) {
4     sum += i
5     for (let J = 0; J < m; i++) {
6       // do some thing
7    }
8   }
9 }

這種是由兩個數據規模n、m來決定的時間複雜度，所以是O(n * m)，關鍵還是要分析嵌套的循環跟外面那層循環的關係。

時間複雜度耗費時間從小到大依次排列

　　O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

常見排序演算法對應的時間複雜度

空間複雜度

 時間複雜度的全稱是漸進時間複雜度，表示演算法的執行時間與數據規模之間的增長關係。同理，空間複雜度全稱就是漸進空間複雜度（asymptotic space complexity），表示演算法的存儲空間與數據規模之間的增長關係，空間複雜度分析跟時間複雜度類似。

1 function run (n) {
2     let name = 'joel'
3     let step= 2
4     const arr = []
5 
6     for (let i = 0; i < n; i++) {
7       arr.push(i * step)
8    }
9 }

再第4行程式碼我們初始化一個數組，再第7行程式碼對這個數組進行push 操作，這個循環是依賴外部的n，所以這個空間複雜度為 O(n)，我們常見的空間複雜度就是 O(1)、O(n)、O(n2 )