Algorithm 演算法

Algorithm 演算法
Categories:
Tags:

說明

好的程式碼通常是指好的「閱讀性／維護性（readable/maintainable）」和「可擴展性（scalable）」，而可擴展性又可以分成時間複雜度（速度）和空間複雜度（space complexity）。

其中時間複雜度就可以使用 Big O Notation 來衡量，也就是用來衡量當資料量持續增加時，程式執行的時間增加的比率為何。

時間複雜度 Time Complexity

我們需要一些指標來評量各種方式的好壞。在演算法中，常會使用 Big O Notation 和 Time Complexity 來衡量一個演算法（函式）的好壞。通常，會根據這個函式隨著輸入的資料量增加時，執行時間會拉長多少來作為衡量的標準之一。

速度排名 可接受度 複雜度 說明
1 優良 O(1) constant time 常數時間，沒有迴圈
2 優良 O(log(n)) logarithmic time 邏輯運算時間，通常會是搜尋使用的演算法，會排序後先對半分
3 優良 O(n) liner time，線性時間，一層迴圈
4 可接受 O(n*log(n)) n * logarithmic time，n 次邏輯運算時間，通常是排序的操作
5 差 O(n^2) 指數時間，2 層迴圈（迴圈內有迴圈）
6 差 O(n^3) 指數時間，3 層迴圈（迴圈內有迴圈）
7 差 O(2^N) recursive 遞迴
8 差 O(n!) 每個元素都在跑一次迴圈

時間複雜度比較 Common Data Structure Operations

Algorithm 演算法

資料結構時間複雜度

Algorithm 演算法

陣列排序演算法時間複雜度 Array Sorting Algorithms

Algorithm 演算法

時間複雜度範例

Constant Run Time (O(1))

執行時間不會隨著輸入資料量的增加而增加

以下面的函式為例，不論我們代入的資料量有多大，它都只是輸出陣列中第一和第二個元素的值，因此執行時間不會隨著輸入資料量的增加而增加。

let arr1 = [1, 2, 3, 4, 5];
let arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

/**
 * Constant Run Time：不會隨著輸入的資料量越大而使得執行時間變長
 * Big O Notation: "O(1)"
 **/
function log(arr) {
  console.log(arr[0]);
  console.log(arr[1]);
}
log(arr1); // 1, 2
log(arr2); // 1, 2

Linear Run Time (O(n))

當我們輸入的資料越多的時候，它就會需要等比例輸出越多的內容給我們，因此會需要消耗等比例越多的時間

/**
 * Linear Run Time: 隨著資料量的增加，執行時間會等比增加
 * Big O Notation: "O(n)"
 **/
function logAll(arr) {
  for (let item of arr) {
    console.log(item);
  }
}

logAll(arr1); // 1, 2, 3, 4, 5
logAll(arr2); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Exponential Run Time (O(n^2))

迴圈內有迴圈

隨著資料量的增加，執行時間會以指數成長。以下面的函式為例，當我們輸入的陣列包含 5 個元素的時候，它會輸出 25 (5^2) 筆資料；但是當我們數入的陣列包含 10 個元素的時候，它則會輸出 100 (10^2) 筆資料：

/**
 * Exponential Run Time:  隨著資料量的增加，執行時間會誇張的增長
 * Big O Notation: "O(n^2)"
 **/
function addAndLog(arr) {
  for (let item of arr) {
    for (let item2 of arr) {
      console.log('First', item + item2);
    }
  }
}
addAndLog(arr1); // 25 pairs logged out
addAndLog(arr2); // 100 pairs logged out

Logarithmic Run Time (O(log n))

n / 2

隨著資料量增加，執行時間雖然會增加，但增加率會趨緩。能夠對半（n/2）處理的通常都屬於 O(log n) 的演算法，因為假設 n 是 8，表示一共會跑 3 次，也就是 log 8 = 3 的意思。

每次都找到陣列中最中間的元素並保存起來：

/**
 * Logarithmic Run Time: 隨著資料量增加，執行時間雖然會增加，但增加率會趨緩
 * Big O Notation: "O (log n)"
 **/
function half(arr: number[]): number[] {
  const elements: number[] = [];

  let n = arr.length - 1;
  while (n > 0) {
    n = Math.floor(n / 2);
    elements.push(arr[n]);
  }
  return elements;
}

二元搜尋樹

/**
 * Logarithmic Run Time: 隨著資料量增加，執行時間雖然會增加，但增加率會趨緩
 * Big O Notation: "O (log n)"
 **/
function binarySearch(arr, key) {
  let low = 0;
  let high = arr.length - 1;
  let mid;
  let element;

  while (low <= high) {
    mid = Math.floor((low + high) / 2, 10);
    element = arr[mid];
    if (element < key) {
      low = mid + 1;
    } else if (element > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

console.log(binarySearch(arr1, 3));
console.log(binarySearch(arr2, 3));

sqrt n O(√n)

x*x < n

n 是 100 的話，只會跑 10 次，也就是 √100，所以可以知道是 √n

/**
 * Logarithmic Run Time: 隨著資料量增加，執行時間雖然會增加，但增加率會趨緩
 * Big O Notation: "O (√n)"
 **/
function isPrime(n: number): boolean {
  // 關鍵在這裡的 X * x
  for (let x = 2; x * x < n; x += 1) {
    if (n % x === 0) {
      return false;
    }
  }
  return true;
}

Space Complexity 空間複雜度

空間複雜度指的是程式佔用記憶體的空間，一樣可以透過 Big O 來表示。

時間複雜度和空間複雜度之間有時有 trade-off 存在，也就是為了提升時間複雜度（提升處理效率）必須犧牲空間複雜度；有時則需要為了空間複雜度（減少記體體的消耗）而犧牲時間複雜度。

空間複雜度範例

O(1)

// space complexity of foo: O(1)
function foo(n) {
  for (let i = 0; i < n.length; i++) {
    console.log('foo');
  }
}

O(n)

// space complexity of bar: O(n)
function bar(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr[i] = n;
  }
  return arr;
}

參考資料

Sort 排序

Sort 排序

Search 搜尋

Search 搜尋

Pointer 指標

Pointer 指標

數學運算

數學運算