Learn Coding 6: Algorithm

你不覺得一個功能要跑 1 分鐘、2 分鐘、甚至 3 分鐘以上很久嗎? 你也許會聽到人們說:「天哪! 呼叫別人寫給我的搜尋功能後，我苦苦等了五分鐘才得到結果!」、「為什麼同事交接過來的 code 光開起來就要花 1 分鐘!」。當你遇到這種程式，你要如何優化它? 你要如何讓程式在可以被接受的時間內跑完? 今天，我將在這篇文裡教你如何寫出讓「執行時間」或「使用的資源」符合預期的程式。在我給你實際的演算法實例之前，我需要先教你一些基礎知識，再帶你進行一個完整的演算法設計流程，否則你會沒有辦法用必要的工具來設計演算法。如果你正頭痛該怎麼設計解決方案、如果你想突破現況朝向大師前進，你必須理解我想教給你的三個關鍵課題。點開這篇文章，我將把你變成一個能讓程式表現符合預期的專家!

課題一: 演算法是什麼

當人們收到一個需求，例如要把陣列裡的元素從小排到大，他們可能會直接把手放到鍵盤上，開始敲敲打打寫出一段 code 來解決問題。問題是，要解決的問題如果很複雜、或程式必須在一定時間內跑完、又或者這問題得花很多資源、只能花一定的資源來解決，我就不太同意直接開始寫程式。千萬不要直接開始寫程式! 很多人都不相信，先設計好演算法並且估算它的表現到哪裡，再依照演算法把程式寫出來，會更有機會成功寫出一份性能符合預期的 program。我想要你先看看這個例子，如果我們要從兩位學生中找出比較高的那一位，我們可以先開一份空白的文字檔，然後寫下該如何找到比較高的學生:

1. 問第一位學生的身高，把他的身高記下來
2. 問第二位學生的身高，把他的身高也記下來
3. 比較他們的身高，找出比較高的那一位
4. 問到這位學生的名字
5. 把這個名字提供出來

這種用口語化的方式來設計、來描述一個問題該如何依序用有限的步驟來解決，就是演算法。好的演算法可以讓程式變得很簡單、很有效率，或只花預期內的資源就把問題解決；依照糟糕的演算法寫出來的 program，甚至可以跑好幾分鐘都跑不出來! 讓我給你一段照「找學生演算法」寫出來的程式:

std::string find_taller(student* student1, student* student2)
{
    int height1 = student1->get_height();
    int height2 = student2->get_height();
    student* taller_student = nullptr;

    if (height1 > height2)
    {
        taller_student = student1;
    }
    else
    {
        taller_student = student2;
    }

    std::string name = taller_student->get_name();

    return name;
}

我想要你先看這段 code 的第三行，這裡用 student->get_height() 取得第一位學生的身高。接著，在第二行取得第二位學生的身高。然後在第 7 到第 14 行比較兩位學生的身高，找出比較高的學生。接下來在第 16 行問到這位學生的名字。最後在第 18 行把這個名字給出去。在這個例子裡，演算法的描述一行一行轉換成對應的程式碼。這才是應該用來解決複雜問題的流程: 先設計好演算法再把程式寫出來。現在，你已經知道什麼是演算法。接下來你必須學會如何計算一個演算法的「複雜度」。

課題二: 複雜度

我已經寫好找學生的演算法了，但要如何評估它最糟的執行時間呢? 到底什麼是複雜度? 其實說穿了「複雜度」就是指程式跑一段演算法的「最糟狀況」到哪裡。寫好演算法之後你只知道解決問題的步驟，接著你需要計算程式跑這段演算法得花多少時間或多少資源。複雜度會專注在兩種指標: 最多會花多少時間的時間複雜度 (time complexity) 跟花多少資源的空間複雜度 (space complexity)。在計算複雜度的時候，工程師會用世界通用的 big-O 標記 O(n) (念作 big-O n) 來用小括弧裡面的方程式描述複雜度會怎麼隨著輸入量變化。例如 O(n) 可以看做是 Complexity = n 的多項式、O(2n + 1) 可以看做是 Complexity = 2n + 1 的多項式。複雜度的成長速度大略可以概括成常數、線性、log 跟次方這幾種，讓我解釋這四類複雜度給你知道：

1. O(1)：代表資料量增加不會影響複雜度
2. O(n)：代表複雜度會隨著資料量增加跟著以線性成長
3. O(n log(n))：代表複雜度一開始會隨著資料量增加跟著遽增，但隨著資料量持續增加，複雜度的成長會趨緩
4. O(n²)：複雜度會隨著資料量增加跟著以指數上升。上升的速度會由次方數決定

先計算出複雜度可以避免根據表現達不到目標的演算法來寫 code。複雜度主要關注在時間跟空間兩種需求，分別是 time complexity (時間複雜度) 跟 space complexity (空間複雜度)。讓我分別解給你聽:

1. 時間複雜度 (time complexity): 程式每次跑完花的時間可能都不一樣。時間複雜度是指程式跑完最多可能會花多少時間。我們通常會去算指令執行的數量來計算一個演算法的時間複雜度
2. 空間複雜度 (space complexity): 程式每次跑完使用的記憶體可能都不一樣。空間複雜度是指程式跑完最多可能會用多少 memory space。可以用每個變數分別被建立了幾次，分別乘上變數使用的記憶體大小，最後把它們全部加起來後得到一個演算法的空間複雜度

太好了! 現在你已經知道所有必要的專業知識。接著讓我給你一個經典的演算法，帶你走過幫問題設計演算法、計算複雜度，一直到最後把程式寫好的完整流程。

課題三: 演算法實例 - 泡沫排序 (Bubble Sort algorithm)

Instagram 如何把你最酷愛的 Reel 短片排給你? Facebook 如何把你最喜愛的 Watch 影片遞送給你? YouTube 如何把你最熱愛的影片一個接一個建議給你? 排序的概念到處都是，Google Excel 文件裡的排序功能就是最好的例子。我們今天要談的是一個叫「Bubble Sort」的排序演算法。我要你想像一下: 今天放學的時候，每個班級的小學生都在排隊準備回家。有位老師想把五位小學生從最高到最低排好。但問題是，這位老師該怎麼做呢? 首先，這位老師先走到頭兩位學生前面比較他們的身高。如果學生沒有由高排到低就幫兩位學生交換位置。接著老師會比較第二跟第三位、第三跟第四位……一直到最後兩位。如果中間有幫任何學生交換位置，老師就會走到最前面從頭再檢查一輪，直到有任何一輪結束後都沒有幫學生交換位置為止。簡單來說，這段演算法總共由這三個步驟組成:

1. 老師會不斷從隊伍裡的第一位學生開始兩兩比較學生的身高
2. 如果後面的學生比前面的還高，就幫兩位學生交換位置
3. 不斷循環做第 1. 跟第 2. 步，直到有一輪完全沒有幫學生交換位置為止

這段演算法已經描述了麼把學生由高排到低。接著讓我帶你一起算算這段演算法的時間複雜度。

int[] student_heights = { 149, 151, 152, 153, 156 };

我想要你先看過上面這個陣列，裡面儲存了每位學生的身高。依照寫出來的演算法，在第一輪的流程裡面總共會比較學生的身高 4 次，幫學生交換位置 4 次。如果我們用一個代數「n」來表示學生的數量，那麼在進行完第一輪流程之後總共比較了 n - 1 次 (4 次 = 5 - 1 次 = n - 1 次)、交換了 n - 1 次 (4 次 = 5 - 1 次 = n - 1 次)

== 第一輪 ==
檢查了 n - 1 次
交換了 n - 1 次
[151, 152, 153, 156, 149]

---

接著老師會回到隊伍的最前面，一樣再進行一輪演算法定義的流程。然而在第二輪流程裡面，第四位學生已經比第五位學生還要高，不需要被交換位置，所以當第二輪流程進行完之後，在過程中總共比較了 n - 1 次 (實際上是 4 次)，但只交換了 n - 2 次 (實際上是 3 次)。

== 第二輪 ==
檢查了 n - 1 次
交換了 n - 2 次
[152, 153, 156, 151, 149]

---

在開始第三輪的排序流程之前，我想要你感受一下: 在兩輪的排序過程之中，先是最矮的學生被不斷被往後排到隊伍的最後面，接著是第二矮的學生不斷被往後排到隊伍裡的倒數第二個位置。這個過程會讓越矮的學生一位一位往後排，就像「氣泡 (bubble)」一樣不斷往上冒出水面。這種不斷把最大或最小元素往陣列的某個方向交換過去的過程就是 bubble sort 演算法的特點。再來一輪吧! 這次做完比較跟交換的動作之後，總共做了 n - 1 次比較 (實際上是 4 次) 跟 n - 3 次交換 (實際上是 2 次)。

== 第三輪 ==
檢查了 n - 1 次
交換了 n - 3 次
[153, 156, 152, 151, 149]

---

依此類推，在第五輪的流程結束之後，總共在這次的流程裡做了 n - 1 次比較 (實際上是 4 次) 跟 n - 5 次交換 (實際上是 0 次)。

== 第五輪 ==
檢查了 n - 1 次
交換了 n - 5 次
[156, 153, 152, 151, 149]

---

最後我想要你看過總共五輪的排序歷史紀錄:

第幾輪	檢查次數	交換次數
第一輪	n - 1	n - 1
第二輪	n - 1	n - 2
第三輪	n - 1	n - 3
第四輪	n - 1	n - 4
第五輪	n - 1	n - 5
Total	5n - 5	5n - 15

首先以檢查動作來看，可以得到總共做了 n(n - 1) 次動作
接著以交換動作來看，可以得到總共做了 (n - 1) + (n - 2) + (n - 3) + … + (n - n) = n(n - 1) / 2 次動作
最後把檢查跟交換動作的次數都加起來之後，會得到總共做了 n(n - 1) + n(n - 1) / 2 = 3n(n - 1) / 2 = 3(n² - n) / 2 次動作
到這邊讓我們再稍微修改一下這個複雜度:

1. 因為 n 的數值如果非常大，常數 3 跟 2 對複雜度就幾乎沒有影響，所以都可以被忽略掉。把常數都去掉之後會得到簡化過的時間複雜度: n² - n
2. 如果 n 的數值不斷往上增加，n 跟 n² 比起來也可以被看成是可被忽略的運算元。把 n 去掉之後會得到簡化過的時間複雜度: n²

結論就是，我們得到 bubble sort 演算法的時間複雜度是 O(n²)

Mathematical Style Pseudocode

上面是用比較高階、比較口語的方式來描述排學生的邏輯。接著，我們用比較低階的 pseudo code 把演算法寫出來:

algorithm bubble-sort is
    input: Array A with capacity l
    output: Array s such that s is a sorted version of array A

    s <- [] empty array

    for i <- 0 to l - 2 do
        ith element in s <- ith element in A

    if l = 1
        return s

    has_swap_op <- true

    while has_swap_op = true
        has_swap_op <- false
        for i <- 0 to l - 1 do
            if ith element in s < (i+1)th element in s
                temp <- (i+1)th element in s
                (i+1)th element in s <- ith element in s
                ith element in s <- temp
                has_swap_op <- true
    
    return s

是不是已經很像程式碼了呢? 上面的演算法有個專有名詞叫做「Mathematical Style Pseudocode」。第一行 algorithm bubble-sort is 是在定義一個名字叫做「bubble-sort」的演算法。第二行 input: 是用來定義這個演算法要接收什麼參數。以這個演算法來看要接收一個陣列，陣列的長度是 l。第三行 output: 是用來描述這個演算法要輸出什麼結果。以這個演算法來說，要輸出一個排序過的陣列。在 output: 之後就是演算法的內容啦! 內容跟前面的描述很類似，只是比較詳細了些。內容裡面有使用 pseudo code 常用的一些符號，例如 <- 代表把右邊的數值指定到左邊的變數、= 代表的是比較左邊跟右邊兩個運算元的數值是不是相等、for ... to ... 代表的是要從某個數值開始一直重複做迴圈內定義的事情，直到某個終止數值為止。這邊有常見的 pseudo code 數學符號:

運算種類	符號
Assignment	<- 或是 :=
Comparison	=, ≠, <, >, ≤, ≥
Arithmetic	+, -, *, /, mod
Floor/ceiling	⌊ ⌋, ⌈ ⌉
Logical	and, or
Sums, products	Σ, Π

到這裡我們已經知道演算法的目的，也知道怎麼把解法用比較口語、比較簡單的方式寫出來。接下來，就是屬於你的挑戰時間啦! 把上面的 pseudo code 用程式碼寫出來吧!

Implementation

這裡是把設計好的 bubble sort 演算法用 C++ 程式語言寫出來:

#include <stdio.h>

void bubble_sort(int array[], int length) {    
    bool has_swapped = false;

    if (length == 1) {
        return;
    }

    do {
        has_swapped = false;

        for (int i = 0; i < length - 1; i++) {
            if (array[i] < array[i + 1]) {
                int temp = array[i + 1];
                array[i + 1] = array[i];
                array[i] = temp;
                has_swapped = true;
            }
        }
    } while (has_swapped);
}

int main(int argc, char* argv[]) {
    int student_heights[] = { 149, 151, 152, 153, 156 };
    int length = sizeof(student_heights) / sizeof(int);
    bubble_sort(student_heights, length);

    for (int i = 0; i < length; i++) {
        printf("%dth student's height is: %d\n", i + 1, student_heights[i]);
    }

    return 0;
}

從這份 C++ 程式碼我們可以發現，如果演算法設計的很好，寫出來的程式碼其實不會跟演算法差太多。
讓我們再來看一份 PHP 程式碼:

<?php
    $array = array(149, 151, 152, 153, 156);

    function bubbleSort($array) {
        $hasSwapped = false;
        $sortedArray = [];

        foreach ($array as $key => $value) {
            array_push($sortedArray, $value);
        }

        do {
            $hasSwapped = false;

            for ($i = 0; $i < count($sortedArray) - 1; $i++) {
                if ($sortedArray[$i] < $sortedArray[$i + 1]) {
                    $temp = $sortedArray[$i + 1];
                    $sortedArray[$i + 1] = $sortedArray[$i];
                    $sortedArray[$i] = $temp;
                    $hasSwapped = true;
                }
            }
        } while ($hasSwapped);

        return $sortedArray;
    }

    foreach ($array as $key => $value) {
        echo("<li>Student $key's height is: $value</li>");
    }

    $array = bubbleSort($array);

    foreach ($array as $key => $value) {
        echo("<li>Student $key's height is: $value</li>");
    }
?>

發現了嗎? 兩份程式碼的寫法幾乎差不多! 用這次的例子我們也可以知道演算法寫好之後，不一定只能用某種語言寫出來。我們可以用演算法來設計跟描述怎麼解決一個問題。等方法設計出來之後，有機會可以用任何一種程式語言實作他!
希望今天的內容對您有幫助，有任何建議或想發問的地方歡迎在下面留言，我們下次 Learn to Code 見!