這週是 六角鼠年鐵人賽 第十週（是不是有銅角獎啦？！），說明如何評估演算法的好壞。

演算法的好壞

一個問題不一定只有一種演算法能解決。那我們怎麼評估演算法的好壞呢？

最直覺的方式，就是測量程式的執行時間、程式的記憶體使用量。

但是，即便是相同的演算法，也會因為以下變數而有所不同：

• 不同電腦的處理速度
• 實作的程式語言
• 輸入的大小
• 不同情況的資料

所以需要用一個「不受環境、數據狀況，比較客觀的方式」去分析一個演算法。

所以我們會用 複雜度 來分析演算法：

• 時間複雜度（Time complexity）
  指演算法所耗費的時間。
• 空間複雜度（Space Complexity）
  指演算法所需要消耗的儲存記憶體資源。

時間複雜度與空間複雜度是相互影響的，當追求一個較好的時間複雜度時，可能會使空間複雜度的性能變差。舉例來說，Google Chrome 相較於其他瀏覽器，運行速度較快，但它的缺點就是占用很多記憶體。

根據調查顯示，用戶對於執行效率有極高的要求，對於網頁開啟的忍耐極限是 6 秒甚至更短。在這個大背景下，一個好的演算法，更專注於討論時間複雜度。另外，現在的儲存空間很便宜，而且當 資料量變大 時，空間複雜度的差異通常不大，但 時間複雜度則會有極大的差異。

不同情況下的分析

每當輸入資料的情況不同時，演算法呈現的效果也不同，舉例來說，在圖書館找一本書，並一本一本找：

• 最佳情況：第一本就是要找的書
• 最糟情況：最後一本才是要找的書
• 平均情況：中途就找到要找的書

上述三種情況都可以被用來分析演算法。但最佳情況對演算法沒有多大幫助，通常我們只考慮最糟情況，也就是演算法複雜度的上限值。

輸入大小與執行時間的關係

我們舉一個非常簡單的例子。

以 求等差數列的和 來說，假設要求出 1 + 2 + 3 + … + n 的和，有兩種作法：

1. 一個一個加
2. 套用公式計算

用 for 迴圈一個一個的加：

1
2
3
4
5
6
7

function sum(n) {
  let sum = 0;
  for(let i = 0; i <= n; i++) {
    sum += i;
  }
  return sum;
}

等差數列的和公式，我們小時候應該都有學過：

一個等差數列的和，等於其首項與末項的和，乘以項數除以 2。

1
2
3

function sum(n) {
  return (1 + n) * n / 2;
}

兩種作法的時間差異：

1. 如果 $1$ 累加到 $n$ 迴圈需要跑 $n$ 次
2. 不論 $n$ 多大，都只需要執行 $1$ 次。

假設執行一次只需要 0.01毫秒，當 $n$ 不大時，一個一個加與套用公式計算的時間差異並不大，但隨著 $n$ 越來越大，你會發現使用一個一個加的時間會變得非常可觀。

由此可知，當輸入量非常大時，不同演算法執行上效率差異會非常大。

演算法效率：執行所需時間與資料量 $n$ 的關係。

演算法執行時間的計算方式

執行時間 = 執行次數 * 每次執行所需的時間

但是 每次執行所需的時間 會根據機器和語言的的差異而有所不同，因此演算法只考慮執行的次數。

將演算法中基本操作的執行次數作為演算法時間複雜度的度量，即時間複雜度不是演算法程式的運行時間，而是其中基本操作的總次數。

舉例來說：

1
2
3
4
5
6
7

function sum(n) {
  let sum = 0;
  for(let i = 0; i < n; i++) {
    sum += i;
  }
  return sum;
}

假設每行的執行時間都一樣，記做 $t$。

• line2：需要 $1$ 個 $t$ 的時間
• line3：需要 $n$ 個 $t$ 的時間
• line4：也是 $n$ 個 $t$ 的時間
• line6：需要 $1$ 個 $t$ 的時間
• 那麼執行時間就是 $(2n + 2) * t$
• 執行次數為 $2n + 2$

再考量下面這個例子：

1
2
3
4
5
6
7
8
9

function sum(n) {
  let sum = 0;
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      sum += i * j;
    }
  }
  return sum;
}

• line2：需要 $1$ 個 $t$ 的時間
• line3：需要 $n$ 個 $t$ 的時間
• line4：也是 $n^2$ 個 $t$ 的時間
• line5：也是 $n^2$ 個 $t$ 的時間
• line8：需要 $1$ 個 $t$ 的時間
• 執行次數為 $2n^2 + n + 2$

複雜度分析工具

我們在之前已經提過，演算法通常只考慮最糟情況，也就是演算法複雜度的上限值。

因此我們會用 Big O Notation 來表示演算法的複雜度。

Big O Notation（$O$），念作 Big Oh 😮，是用於描述函數漸近行為的數學符號，更確切地說，它是用另一個函數來描述一個函數數量級的漸近上界，用 $O(f(n))$ 表示。

假設輸入 $n$，而演算法的執行時間為一個函數 $f(n)$，以下五個演算法分別為：

1. $1$
2. $10$
3. $2n + 1$
4. $2n^2$
5. $\log_2n$

當 $1$ 與 $10$ 比較時，並不會說 $1$ 比 $10$ 有效率，因為當 $n$ 趨近無限大時，$1$ 與 $10$ 兩者差異不大，舉例來說：假如你身上有一千億，當你要花 1元跟 10元時，你會認為 10元的比較貴嗎？不會都是小錢。

分析演算法是看當資料量「最多」會達到怎麼樣的趨勢，也就是 $n$ 趨近無限大時，並不會在意細節，只看函數的最高次方，會忽略係數、其他次方項與常數。

用 Big O 表示上述函數之複雜度分析：

1. $O(1)$
2. $O(1)$
3. $O(n)$
4. $O(n^2)$
5. $O(\log n)$

由此可知，當我們在計算演算法的時間時，只需要大概的算一下迴圈數，大致上判斷一下丟進去的資料量會讓程式執行幾次即可，不需要像之前一樣計算的那麼仔細。

常見時間複雜度

圖片來源：8 time complexities that every programmer should know

根據上圖，若同樣處理 $n$ 筆資料，那麼各個時間複雜度成本如下：

$O(1)<O(\log n)<O(n)<O(n \log n)<O(n^2)<O(2^n)<O(n!)$

成本越高，表示效率越差。

常見的時間複雜度：

輸入 10、100、1000 資料量需花費的時間比較：

當複雜度到達或超過 $O(2^n)$ 時，只要 $n$ 稍大一點，基本上程式就會跑到天荒地老都跑不出來，因此最好避免過高的複雜度。

空間複雜度

上邊説了那麼一大堆的時間複雜度，相比空間複雜度就是指演算法執行時所花費的記憶體空間的趨勢。

其計算方式與時間複雜度相似，也使用 Big-O 來表示其複雜度。

1. 計算演算法使用記憶體量

計算演算法所需的記憶體量，只需要計算使用的變數量。

舉例來說：

1
2
3
4
5
6
7

function sum(n) {
  let sum = 0;
  for(let i = 0; i < n; i++) {
    sum += i;
  }
  return sum;
}

不管程式的執行步驟數是多少，我們的變數始終只有 sum 與 i，也就是變數量只有 2。因此空間複雜度為 $O(1)$。

再考量下面這個例子：

1
2
3
4
5
6
7

function show(n) {
  let arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
}

迴圈每次執行一次 push 方法，就會申請一個空間存儲變量，很明顯的，記憶體的佔用量會隨著輸入量而線性成長，故這個演算法的空間複雜度為 $O(n)$。

2. 常見的空間複雜度

常見的空間複雜度只有 $O(1)$、$O(n)$、$O(n^2)$，其他的話很少會用到。

總結

評估演算法的好壞，就是要分析演算法的複雜度，而時間複雜度與空間複雜度式相互影響的，但時間複雜度比空間複雜度重要。