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 指标

数学运算

数学运算