👋 歡迎來到演算法的世界！

各位未來的決策數學家，你們好！本章將帶領你進入「演算法 (Algorithms)」這個既刺激又實用的領域。別被這個名詞嚇到了；演算法其實就是「結構化計畫」或「指令集」的代名詞而已。

在決策數學 (D1) 中，我們運用演算法來高效率地解決複雜的現實問題——例如找出最快路徑、編排工作排程，或是整理海量數據。熟練這些概念，對於我們稍後要處理的所有網絡與最佳化問題至關重要。

第 1 節：定義演算法

到底什麼是演算法？

你可以把演算法想像成一份食譜。如果你想烤一個蛋糕（輸出結果），你需要特定的材料（輸入資料），以及一套清晰、有順序的步驟（演算法）來將這些材料轉化為成品。

在數學與計算領域中：

  • 演算法是一組有限、定義明確的指令序列，旨在執行特定任務或解決特定問題。

優秀演算法的特徵

任何指令集若要被視為一個合格的演算法，必須具備以下四個關鍵屬性：

  1. 有限性 (Finiteness)：演算法必須在有限的步驟後結束，不能無限執行下去。
  2. 清晰/精確 (Clarity/Precision)：每一個步驟都必須清晰、無歧義且精確定義。（不能出現像「烤到看起來不錯為止」這種模糊的指令。）
  3. 輸入 (Input)：演算法必須接收零個或多個指定的數量作為輸入數據。
  4. 輸出 (Output)：演算法必須產生一個或多個指定的結果作為輸出數據。

你知道嗎？「演算法 (Algorithm)」這個字源自於 9 世紀波斯數學家花拉子米 (Muḥammad ibn Mūsā al-Khwārizmī) 的名字。

重點回顧：演算法基礎

演算法就是一個逐步執行的程序，必須具備有限性、清晰性，並能處理輸入與產生輸出。

第 2 節：衡量效率

在決策數學中，演算法能運作還不夠，它還必須運作得快。效率是指演算法解決問題的速度，通常以相對於輸入規模的操作次數或比較次數來衡量。

時間複雜度與量級

我們通常使用量級 (Order of Magnitude)（或稱大 O 符號 Big O Notation，你只需要理解基本的分類）來衡量效率。這描述了隨著資料集的大小 \(n\) 增加時，執行時間如何增加。

情況 1：線性時間複雜度 — \(O(n)\)

如果演算法與輸入規模 \(n\) 呈線性關係，我們稱之為 \(O(n)\)。

  • 意義：如果你將輸入資料量加倍（例如從 10 項變為 20 項），執行時間大約也會加倍。
  • 範例：如果你有一份 \(n\) 個名字的清單，而你需要逐一檢查每個名字以找出特定的人，步驟數與 \(n\) 成正比。
情況 2：二次時間複雜度 — \(O(n^2)\)

如果演算法的執行時間與輸入規模的平方成正比，我們稱之為 \(O(n^2)\)。

  • 意義：如果你將輸入資料量加倍（從 10 項變為 20 項），執行時間會增加 \(2^2 = 4\) 倍。對於大型資料集而言，這種效率會變得非常慢。
  • 範例：如果你有一份 \(n\) 個項目的清單，並且對於每一項，你都必須將其與清單中其他所有項目進行比較。

類比：想像你在整理圖書館。
如果你使用 \(O(n)\) 的方法，你只需要看每一本書一次。
如果你使用 \(O(n^2)\) 的方法，對於每一本書，你都要重複將其與「所有其他書籍」的位置進行比對。

輸入規模 (\(n\)) \(O(n)\) 所需步驟 \(O(n^2)\) 所需步驟
10 10 步 100 步
100 100 步 10,000 步
1000 1,000 步 1,000,000 步

關鍵重點：處理大型資料集時，\(O(n)\) 效率的演算法遠比 \(O(n^2)\) 的演算法好得多。

第 3 節：排序演算法

排序演算法用於將清單中的項目（數字、名字等）按特定順序（升序或降序）排列。你必須學會執行並分析以下兩種方法。

1. 氣泡排序法 (Bubble Sort)

氣泡排序法是最簡單的排序演算法，但對於大型清單來說也是最慢的。它的運作方式是反覆遍歷清單，比較相鄰元素，如果順序錯誤就交換它們。當某一次完整的遍歷中無需任何交換時，程序就會停止。

氣泡排序法過程（升序）
  1. 從清單開頭開始，這是第 1 次遍歷 (Pass 1)。
  2. 比較第一個元素與第二個元素。如果順序錯誤，交換位置。
  3. 移動到下一對（第二個與第三個元素），重複比較與交換。
  4. 持續此過程直到清單末尾。最大的未排序項目將會像「氣泡」一樣浮動至清單末端的正確位置。
  5. 記錄該次遍歷中的總交換次數。
  6. 如果交換次數為零，則清單已排序完畢，演算法終止。
  7. 如果發生了交換，則開始第 2 次遍歷 (Pass 2)，重複步驟 2-5，但不需要檢查末端已排序的項目。

範例：排序清單 [4, 1, 3, 2]

  • 開始： [4, 1, 3, 2]
  • 第 1 次遍歷：
    • (4, 1) -> 交換 -> [1, 4, 3, 2]
    • (4, 3) -> 交換 -> [1, 3, 4, 2]
    • (4, 2) -> 交換 -> [1, 3, 2, 4] (4 已歸位)
    總交換次數：3。
  • 第 2 次遍歷：
    • (1, 3) -> 不交換 -> [1, 3, 2, 4]
    • (3, 2) -> 交換 -> [1, 2, 3, 4] (3 已歸位)
    總交換次數：1。
  • 第 3 次遍歷：
    • (1, 2) -> 不交換 -> [1, 2, 3, 4]
    總交換次數：0。停止。

效率說明：氣泡排序法在最壞與平均情況下通常為 \(O(n^2)\) 演算法，因為它經常需要嵌套迴圈（一個迴圈用於遍歷，另一個迴圈用於遍歷內的比較）。

2. 快速排序法 (Quick Sort)

快速排序法對於大型資料集的排序效率要高得多。它採用「分而治之 (Divide and Conquer)」策略。

快速排序法過程
  1. 選擇基準 (Pivot)：從清單中選擇一個元素作為基準 (pivot)。（在 D1 考試中，基準通常選擇中間項，或三個數的中位數）。
  2. 分割 (Partition)：重新排列清單，將所有小於基準的元素放在基準左側，大於基準的元素放在右側。
  3. 子排序 (Sub-sort)：對基準左側與右側的子清單遞迴套用快速排序演算法，直到每個子清單只剩下一個元素。
使用指標進行分割（D1 標準方法）

我們通常使用兩個指標，一個從左 (L) 開始，另一個從右 (R) 開始。

範例：排序 [5, 1, 8, 3, 9, 2] (基準 = 8，中間的元素)

  1. 設定：
    清單：[5, 1, 8, 3, 9, 2]
    L 從 5 開始，R 從 2 開始，基準 = 8。
  2. 尋找 L 與 R：
    • 向右移動 L 直到找到大於或等於基準的元素。（L 停在 8）。
    • 向左移動 R 直到找到小於或等於基準的元素。（R 停在 2）。
  3. 比較 L 與 R：
    • 如果 L 的位置在 R 的左側 (\(L < R\))，交換 L 與 R 指向的元素。
    • 如果 \(L \ge R\)，則遍歷結束，基準已放置在正確位置。
    在我們的範例中，以數值來看，L (位於 8) 在 R (位於 2) 的右側，但以位置來看，L 位於第 3 位，R 位於第 6 位。
    讓我們重新執行指標邏輯：L 需要 $\ge 8$，R 需要 $\le 8$。
    [5, 1, 8, 3, 9, 2]
    L 經過 5, 1，停在 8。
    R 經過 2, 9, 3，停在 2。
    因為 L 的位置 (3) 小於 R 的位置 (6)，我們進行交換：
    清單變為：[5, 1, 2, 3, 9, 8]。
  4. 重複：持續尋找 L 與 R 並進行交換，直到 \(L \ge R\)。
    *自我修正*：D1 中對快速排序的定義通常會簡化分割階段，著重於確認最終的基準位置正確。
快速排序法的效率說明

快速排序法在平均情況下通常為 \(O(n \log n)\)，是速度最快的排序演算法之一。在最壞的情況下（例如基準總是選擇到最大或最小值），效率會退化為 \(O(n^2)\)。這就是為什麼選擇一個好的基準非常重要。

常見錯誤提醒

進行氣泡排序法時，學生常會忘記檢查總交換次數。如果一次遍歷中有任何交換發生，你必須進行下一次遍歷。只有當一次遍歷中沒有發生任何交換時，才能停止。

第 4 節：搜尋演算法

搜尋演算法幫助我們在清單中找到特定的項目（目標）。

二分搜尋法 (Binary Search)

二分搜尋法是在清單中尋找項目極有效率的方法，但有一個關鍵前提：清單必須是已排序的。

二分搜尋法過程（對半原則）

該演算法透過不斷將搜尋區間對半劃分來運作。

  1. 尋找中間點：確定清單的起點、終點與中間元素。
  2. 比較：將目標項目與中間元素進行比較。
  3. 決策：
    • 如果目標等於中間元素，停止（成功！）。
    • 如果目標小於中間元素，捨棄後半部分（從中間元素之後的所有內容）。將新終點設定在目前中間元素的前一個位置。
    • 如果目標大於中間元素，捨棄前半部分。將新起點設定在目前中間元素的後一個位置。
  4. 重複：帶著新的、較小的清單區段回到步驟 1，直到找到目標或區段變空（表示項目不存在）。

範例：在已排序清單 [5, 10, 15, 20, 25, 30, 35] 中找到 25

  • 步驟 1：起點=5，終點=35，中間元素為 20。
  • 步驟 2：25 大於 20，捨棄 [5, 10, 15, 20]。
  • 步驟 3：新清單區段：[25, 30, 35]，新的中間元素為 30。
  • 步驟 4：25 小於 30，捨棄 [30, 35]。
  • 步驟 5：新清單區段：[25]，新的中間元素為 25。
  • 步驟 6：目標 (25) 等於中間元素 (25)。找到了！
二分搜尋法的效率說明

二分搜尋法效率極高，屬於 \(O(\log n)\)。由於每一步都會將搜尋範圍減半，即使對於極大的清單，所需的步驟也非常少。

類比：如果你要在 500 頁的字典中找一個字，你不會從第 1 頁開始翻。你會翻開大約中間的位置（第 250 頁）。根據字母順序，你可以立即捨棄一半的字典，這讓你能在極少的嘗試內找到目標字詞。

演算法重點總結

  • 定義：達成目標的一組有限、精確的步驟。
  • 效率：重點在於時間複雜度 \(O(n)\)（線性，好）與 \(O(n^2)\)（二次，慢）。
  • 氣泡排序法：\(O(n^2)\)，簡單，比較相鄰對，當某次遍歷無交換時停止。
  • 快速排序法：平均 \(O(n \log n)\)，使用基準 (pivot)與分割（分而治之）。
  • 二分搜尋法：必須使用已排序清單，\(O(\log n)\)，每一步驟快速排除掉一半的資料。