Jing's 技術筆記

演算法與時間複雜度

Algorithm
2019/09/15 Share

什麼是演算法(Algorithm)

在數學（算學）和電腦科學之中，為任何良定義的具體計算步驟的一個序列，常用於計算、資料處理和自動推理。精確而言，演算法是一個表示爲有限長列表的有效方法。演算法應包含清晰定義的指令用於計算函式。維基百科

「演算法」是用以執行計算或完成作業的程序，可以想像成手機裡的電話簿，想找出一筆特定的聯絡資料，可以從第一筆資料開始一筆一筆查找，也可以利用查詢功能查找，其中的過程就可以稱為是演算法。

演算法的簡單定義式：輸入 + 演算法 = 輸出

Input -> Algorithm -> Output

ex: 3 * 3 = 9

對演算法有基礎的了解後又該如何評斷出一個演算法的好壞：時間複雜度 (Time Complexity)。

時間複雜度(Time Complexity)

時間複雜度是用來評斷演算法執行快慢的指標，通常用大 O 符號（Big O notation）來記錄時間複雜度的快慢。

要評判一個演算法的好壞，最基本的兩個指標:

  • 需要消耗的時間(時間複雜度)
  • 佔用記憶體空間(空間複雜度)

時間複雜度的計算是以步驟、次數為單位，不是以時間單位計算，並以最壞的狀況做計算。

由一開始電話簿的例子可以知道，查找一筆聯絡資訊的方式：

1.從第一筆開始一筆一筆查找

2.利用查詢功能查找

資料量 方法一 (一筆一筆找) 方法二 (查詢功能)
1 1 分鐘 30 秒
10 10 分鐘 30 秒
n n 分鐘 30 秒

方法1: 隨著資料量增加，需要的時間就等比增加，時間複雜度是 Big O(n)

方法2: 不管資料量如何增加，都不被影響，時間複雜度是 Big O(1)

由此，我們能知道：

Big O 是用來描述一個演算法在輸入 n 個東西時，總執行時間與 n 的關係。

常見的時間複雜度比較

通常，我們會希望一個演算法至少能比 O(n²) 還要快，如果能到 O(n) 甚至是 O(log n) 、 O(1) 的話是最理想的情況。

這張圖會看到當 n 到達一定數量， O(n²) 所花時間比 O(n) 多千倍甚至萬倍。所以寫出一個好的演算法是很重要的！

O(1) 陣列讀取

代表不管你輸入多少個東西，程式都會在同一個時間跑完。最簡單的例子就是讀取一個陣列中特定索引值的元素。

1
2
let color = ['red', 'yellow', 'blue']
console.log(color[2]) // blue

陣列讀取時，因為我們已經知道索引值，不管放入的 n 等於多少，程式都可以在 「一個步驟」 就到達 n 所對應到的索引位置並取出該元素，像這樣的案例，我們就會說陣列讀取演算法的時間複雜度為 O(1)。

一個一個查找，執行步驟會跟著輸入 n 等比例增加，當有 n 個東西時，最壞的情況需要找 n 次，時間複雜度為 O(n)。

1
2
3
4
5
6
7
8
let color = ['red', 'yellow', 'blue']
for(let i = 0 ; i < color.length ; i++) {
  if(fruits[i] == 'blue') {
    return i
  } else {
    return -1
  }
}

十分高效的算法，代表當輸入的數量是 n 時，執行的步驟數會是 log n。

log n = x 的意思是 n = 2^x
log 4: 當 n = 4，程式會在 2 個步驟完成（4 = 2²）
log 16: 當 n = 16 時，程式會在 4 個步驟完成（16 = 2⁴）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let input = [5, 10, 15, 20, 25, 30, 35]
let target = 25
function binarySearch(array, target) {
  let left = 0
  let right = array.length - 1
  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (array[mid] > target){
      right = mid - 1
    } else if( array[mid] < target){
      left = mid + 1
    } else {
      return mid
    }
  }
  return -1;
}
binarySearch(input, target) // 4

二分搜尋法在每進行一個步驟時，就可以排除掉一半的可能性。每次都能減少一半，因此二分搜尋法最糟最糟也只需要以 2 為底的 log n 個步驟就能完成。

二分搜尋法有很多種不同的條件、例子，上面的範例，只是要求在一連串數列裡面回答有沒有找到，有的話在第幾個位置，但其實原理都很類似，一樣是用二分搜尋去排除最多的數字，但是在一些條件判斷上會有些微差異，如果條件沒寫好的話，很容易會變成無窮迴圈。

O(n²) 選擇排序(Selection Sort)

效能較差的演算法。像是選擇排序，大致上來說，包了兩層 for 迴圈的都是 n² 。
選擇排序只需要重複執行兩個步驟：

1.從數列中找出最小值

2.將最小值與數列最左邊的數交換，結束排序。回到 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let input = [5, 4, 1, 3, 2]
function selectionSort(arr) {
  let len = arr.length // 陣列長度有幾個，就要找幾輪
  let minIndex
  for (let i = 0 ; i < len ; i++) { // i 以前的元素都排序好了
    let min = arr[i] // 預設第一個是最小的
    minIndex = i
    for (let j = i ; j < len ; j++) { // 找未排序的最小值
      if (arr[j] < min) {
        min = arr[j]
        minIndex = j
      }
    }
    [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]] // 交換兩個數
  }
  return arr
}
selectionSort(input) // [1, 2, 3, 4, 5]

第一個回合要從 5 個數字中找到最小值，需要 5 個步驟。第二個回合則是從 4 個數字中找，需要 4 個步驟，如果總共要排序的數字有 n 個，則第一個回合需要 n 個步驟，第二回合需要 n-1 個，一直到最後一個回合需要 1 個步驟為止。
可以得知需要經過：

(n + (n - 1) + (n - 2) + … + 1)

= n * (n + 1) / 2

個步驟。

時間複雜度就是 O(n²)，最好、最壞、平均都是一樣的，因為無論原本的陣列長怎樣，都要經過這麼多輪比較。 為什麼會是 O(n²) 後面會提到

O(2^n) 費波那契數列(Fibonacci numbers)

代表著執行步驟會是 2 的 n 次方。這樣的執行效率非常的慢，因此，這樣的時間複雜度是大部分工程師在設計演算法時想要避免的，最常見的例子是以遞迴計算費波那契數列。
規則：

第 0 項 = 0
第 1 項 = 1
第 n 項 = 第 n-1 項 + 第 n-2 項
ex : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

1
2
3
4
// 遞迴不斷呼叫自己
let fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n
fib(2) // 1
fib(10) // 55

執行時間的計算方式

該如何測量執行時間隨輸入內容而變化的程度？最實際的方式是，編程並在電腦上運作，計算真正耗費的時間。不過就算是相同的演算法，也會因為使用的電腦不同，影響執行時間，這點會造成不便。

因此，使用「步驟次數」來表示執行時間。「1個步驟」是執行的基本單位，用「運作結束之前，共執行幾次基本單位」來測量執行時間。

用上面選擇排序的例子來看執行時間，選擇排序的演算法如下：

1.從數列中找出最小值

2.將最小值與數列最左邊的數交換，結束排序。回到 (1)

假設數列中有 n 個數，確認完 n 個數後，(1)「找出最小值」的過程即結束。將「確認 1 個數」的操作視為基本單位，耗費的時間是 Tc。，因此，(1) 是經過n * Tc的時間後結束。

接著，將「交換 2 個數」也視為基本單位，設定為耗費 Ts 的時間。如此一來，(2) 的過程並不隨 n 變化，只進行 1 次數的交換，經過 Ts 的時間後結束。

反覆進行 (1) 和 (2) n 次，加上每回合要確認的數會減少 1 個，總計的執行時間如下:

(n Tc + Ts)+((n - 1) x Tc + Ts)+((n - 2) x Tc + Ts) + … + (2 Tc + Ts) + (1 * Tc + Ts)

= 1/2Tcn(n + 1) + Tsn

= 1/2Tcn² + (1/2Tc + Ts)n

上面已求出執行時間，接著來看如何稍微簡化結果。 Tc 和 Ts 是基本單位，與輸入無關。會隨輸入而變動的是數列長度，假設 n 極大的情況下，當 n 越大，上列數式中的 n² 就會變得非常大，其他部分相對變小。因此，最容易受影響的是 n ，所以可刪除其他部分，將式子變成：

1/2Tcn² + (1/2Tc + Ts)n = O(n²)

可以得知，選擇排序的執行時間，大致會依輸入的數列長度 n 的平方成比例變化，同樣地，比方說某個演算法的運作量分別如下：

5Tx * n³ + 20Tyn² + 3Tzn

此時，用 O(n³) 表示。

5n log n + 2Tyn

此時，用 O(n log n) 表示。

O 這個符號表示「忽略重要項目之外的部分」的意思。 O(n²) 是表示「執行時間在最糟的情況時，能控制在 n² 的常數倍以內」。透過這種表示方式，可以直覺地理解演算法的執行時間，舉例來說，當選擇排序的執行時間是 O(n²) ，快速排序的執行時間是 O(n log n)馬上就能知道快速排序的執行時間較短。此外，隨著輸入的 n 的大小，執行時間會有多大的變化也能一目瞭然。

重點整理

  • 演算法的簡單定義：輸入 + 演算法 = 輸出
  • 時間複雜度：衡量演算法執行好壞的工具
  • Big O：用來描述演算法在輸入 n 個東西時，總執行時間與 n 的關係
  • n 是以最壞情況下做紀錄
  • 在 n 非常大時，好的演算法設計可以省下非常多時間
  • 演算法的速度不是以秒計算，而是以步驟次數
  • 實務上，我們只會紀錄最高次方的那一項，並忽略重要項目之外的係數
CATALOG
  1. 1. 什麼是演算法(Algorithm)
  2. 2. 時間複雜度(Time Complexity)
    1. 2.1. 常見的時間複雜度比較
      1. 2.1.1. O(1) 陣列讀取
      2. 2.1.2. O(n) 簡易搜尋(Linear Search)
      3. 2.1.3. O(log n) 二分搜尋(Binary Search)
      4. 2.1.4. O(n²) 選擇排序(Selection Sort)
      5. 2.1.5. O(2^n) 費波那契數列(Fibonacci numbers)
    2. 2.2. 執行時間的計算方式
  3. 3. 重點整理
Total : 11
2020
2019
2018
JavaScript ES6 Hexo CSS Git Algorithm
JavaScript JS30筆記 CSS Git Algorithm