淺談時間複雜度與空間複雜度

1月 17 2022 Algorithm

每次念這兩個詞都感覺很酷。

時間複雜度

簡單來說就是一個演算法平均需要多少「時間」來完成。

但時間並不是一個很好的指標，畢竟你家電腦跟 NASA 的超級電腦完全是不同等級的東西吧？所以時間上的落差一定很大，因此比較好的指標是用「執行次數」來解釋。

範例

假設要你在 1, 3, 4, 5, 9, 10 裡面找有沒有 9，最容易想到的演算法可能是：

演算法：從頭找到尾，看看有沒有。
輸出：有（第五個）

所以我們的演算法在 6 個數字時要看 6 次，換句話說就是有 n 個數字就要看 n 次。

這時候的時間複雜度就會是：O(n)

O(n) 是一個叫「Big O notation」的表示法：

big-o-complexity

把它想成是一種類似函數的東西就好，n 是你的輸入值，而 O(n) 的輸出結果代表「執行次數」：

  • O(1) 常數，不論 n 是多少都只需要 1 個步驟（最屌的演算法）
  • O(n) 當 n 是多少就要 n 個步驟（剛剛的範例）
  • O(n^2) n 的 2 次方，每當 n 增加 1，就需要 n^2 步驟（n=1 => 1, n=2 => 4, … , n=10 => 100）
  • O(2^n) 2 的 n 次方，每當 n 增加 1，就需要 2^n 步驟（n=1 => 2, n=2 => 4, … , n=10 => 1024）
  • O(n!) n 階層，每當 n 增加 1，就需要 n! 步驟（n=1 => 1, n=2 => 2, … , n=10 => 3628800）

實作

在知道時間複雜度後，我們可以來實作剛剛的演算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 時間複雜度 o(n) => n 有幾個就要看幾個數字 
function hasNumber(numbers, searchNumber) {
  let result = false
  // 看每一個數字，有就填入 true
  for (let number of numbers) {
    if (number === searchNumber) {
      result = true
    }
  }
  // 回傳結果
  return result
}
const numbers = [1, 3, 4, 5, 9, 10]
console.log(hasNumber(numbers, 10)) // true

現在如果要查詢的數字變多了呢？如果沿用剛剛的演算法，時間複雜度會變成：O(n*m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 時間複雜度 o(n*m) => n 有幾個就要看幾個數字，查 m 次就要做幾次查詢的動作
function hasNumber(numbers, searchNums) {
  let result = []
  // 查詢幾次
  for(let i=0; i<searchNums.length; i++) {
    // 看每一個數字
    for (let number of numbers) {
      // 找到就填入 true
      if (number === searchNums[i]) {
        result[i] = true
      }
    }
    // 找不到就填入 false
    if (!result[i]) {
      result[i] = false
    }
  }
  // 回傳結果
  return result
}
const numbers = [1, 3, 4, 5, 9, 10]
console.log(hasNumber(numbers, [2, 3, 5, 9])) // [ false, true, true, true ]

詳細的步驟可以參考下面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 查第一次：2
i 0
number: 1
searchNums: 2
number: 3
searchNums: 2
number: 4
searchNums: 2
number: 5
searchNums: 2
number: 9
searchNums: 2
number: 10
searchNums: 2

// 查第二次：1
i 1
number: 1
searchNums: 3
number: 3
searchNums: 3
number: 4
searchNums: 3
number: 5
searchNums: 3
number: 9
searchNums: 3
number: 10
searchNums: 3

// 查第三次：2
i 2
number: 1
searchNums: 5
number: 3
searchNums: 5
number: 4
searchNums: 5
number: 5
searchNums: 5
number: 9
searchNums: 5
number: 10
searchNums: 5

// 查第三次：3
i 3
number: 1
searchNums: 9
number: 3
searchNums: 9
number: 4
searchNums: 9
number: 5
searchNums: 9
number: 9
searchNums: 9
number: 10
searchNums: 9

空間複雜度

前面講時間，現在講空間，所謂空間複雜度是指：一個演算法平均需要多少「空間」來完成

在剛剛找數字的範例中，我們的演算法並沒有「儲存」任何資訊，所以空間複雜度就是 0。

然而，在前面實作部分中可以發現到當想查詢「多個數字」時，這套演算法的時間複雜度就會變成 O(n*m)，應該有更好的作法才對？畢竟沒有必要每次都從頭找到尾阿！

以空間換取時間

與其每次都從頭找到尾，不如建立一個「表格」，要查數字時只需要「一個步驟」：查表格

有個很經典的例子：費式數列

範例

在 1, 3, 4, 5, 9, 10 裡面找有沒有 2, 3, 5, 9 這些數字：

演算法：

  1. 先建立一個數字表

table-01

  1. 把有出現的數字記下來（1, 3, 4, 5, 9, 10）

table-02

  1. 要找數字就直接查表格

輸出：

2 => 沒有（查表 False）
3 => 有（查表 True）
5 => 有（查表 True）
9 => 有（查表 True）

這時後時間複雜度就從剛剛的 O(n*m) 變成 O(n+m)，但同時也利用了「空間」來儲存一些資訊，這就叫作「以空間換取時間」。

實作

一樣來實作一下這套演算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 時間複雜度 o(n+m)
// => 建立表格要先看 n 個數字
// => 查 m 次 = 查幾次表格
function hasNumber(numbers, searchNumbers) {
  let result = []
  // 所有的數字表格
  let table = {}
  // 建立 1~100 的表格
  for (let i=1; i<=100; i++) {
    table[i] = false
  }
  // 把出現的數字儲存起來
  for (let i=0; i<numbers.length; i++) {
    table[numbers[i]] = true
  }
  // 找數字，直接查表
  for (searchNumber of searchNumbers) {
    // 有出現在表格裡填入 true，沒有則填入 false
    if (table[searchNumber]) {
      result.push(true)
    } else {
      result.push(false)    
    }
  }
  return result
}
const numbers = [1, 3, 4, 5, 9, 10]
const searchNumbers = [2, 3, 5, 9]
console.log(hasNumber(numbers, searchNumbers)) // [ false, true, true, true ]

詳列步驟的話會是這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
1. 建立數字表格：
{
  '1': false,
  '2': false,
  '3': false,
  '4': false,
  '5': false,
  '6': false,
  '7': false,
  '8': false,
  '9': false,
  '10': false,
  ...
}

2. 把出現過的數字儲存起來：
{
  '1': true,
  '2': false,
  '3': true,
  '4': true,
  '5': true,
  '6': false,
  '7': false,
  '8': false,
  '9': true,
  '10': true,
  ...
}

3. 查表格
要找的數字：2，查表格 => false
要找的數字：3，查表格 => true
要找的數字：5，查表格 => true
要找的數字：9，查表格 => true

輸出結果：[ false, true, true, true ]

其實也有更快的作法，直接把「有出現的數字」記起來就好：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function hasNumber(numbers, searchNumbers) {
  let result = []
  // 儲存所有數字
  let table = {}
  // 建立表格（把有出現的數字存起來）
  for (number of numbers) {
    table[number] = true
  }
  // 找數字（直接查表）
  for (searchNumber of searchNumbers) {
    // 有出現在表格裡填入 true，沒有則填入 false
    if (table[searchNumber]) {
      result.push(true)
    } else {
      result.push(false)    
    }
  }
  return result
}
const numbers = [1, 3, 4, 5, 9, 10]
const searchNumbers = [2, 3, 5, 9]
console.log(hasNumber(numbers, searchNumbers)) // [ false, true, true, true ]

步驟跟剛剛差不多，只差在表格建立的內容而已：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1. 建立表格
{ '1': true,
  '3': true,
  '4': true,
  '5': true,
  '9': true,
  '10': true 
}

2. 查表格
searchNumber: 3
searchNumber: 5
searchNumber: 9

輸出結果：[ false, true, true, true ]

以上就是關於時間複雜度與空間複雜度的簡單解說，謝謝觀看。

泡沫排序法（Bubble-sort） 選擇排序法（Selection sort）
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×