歡迎來到算法的世界！
歡迎來到離散數學的第一章。別被「進階數學」（Further Maths）這個名字嚇到了——其實算法是你每天都在用的東西！無論是跟著食譜烤蛋糕、用 GPS 導航，還是根據天氣決定穿什麼，你都在使用算法。在這一章中，我們將學習如何清晰地寫出這些「數學食譜」，如何測試它們，以及如何找出其中執行速度最快的方法。
1. 什麼是算法？
簡單來說，算法（Algorithm）就是一套用於解決特定問題的逐步指令。要成為一個真正的算法，必須具備以下三個要素：
1. 輸入（Input）：你開始時的數據（例如一串數字列表）。
2. 輸出（Output）：你最終得到的結果（例如排序後的列表）。
3. 有限性（Finiteness）：它必須在有限步驟內結束！永遠不會停止的指令是沒有意義的。
策略的主要類型
在設計算法時，我們有時會採取不同的「思維模式」：
• 貪婪法（Greedy）：這種算法在每一步都做出當前看起來最好的選擇，希望藉此達到整體最佳結果。比喻：如果你要湊出 40p 的硬幣，貪婪算法會先選最大的那個（20p），然後再選一個（20p）。
• 啟發式算法（Heuristic）：這是所謂的「經驗法則」。它們可能無法每次都給出最完美、最優化的答案，但對於處理複雜的大問題時，它們速度快且「足夠好」。
• 遞歸（Recursive）：這是一種會「呼叫自己」的算法。它將一個大問題分解成若干個同類型的較小問題。比喻：要打掃整間屋子，先打掃一個房間，然後「呼叫」清理剩餘房間的指令。
快速回顧：檢查清單
• 它是否具有確定性（Deterministic）？（相同的輸入是否總能得到相同的輸出？）
• 它是否有終止條件（Stopping Condition）？（告訴「計數器」何時停止的規則。）
• 它是否有計數器（Counter）？（用來記錄某個步驟重複執行次數的方法。）
重點總結：算法是一組有限、可預測的指令，將輸入轉化為輸出。
2. 算法追蹤（Tracing）與操作
在考試中，你經常會被要求「追蹤」（trace）一個算法。這意味著你要像計算機一樣，精確地遵循每一條指令，即使你覺得自己已經找到了捷徑！
追蹤工具
算法可以用流程圖（Flow Diagrams）（使用方框和箭頭）或偽代碼（Pseudo-code）（用類似英語的數學語言寫成的指令）來表示。你需要掌握兩個特定的函數：
• INT(x)：這是「取整」函數。它會將任何數字向下捨入到最接近的整數。例如，\( INT(4.7) = 4 \)，而 \( INT(5.99) = 5 \)。
• ABS(x)：這是「絕對值」。它會忽略負號。例如，\( ABS(-3) = 3 \)，而 \( ABS(3) = 3 \)。
重點總結：追蹤需要使用追蹤表（Trace Table）。每當變數（如 \( x \) 或 \( y \)）的值發生變化時，都要新開一行進行記錄。
3. 算法的階數（效率）
並非所有算法都是一樣的。隨著問題的「規模」（記作 n）增加，有些算法所需的時間會比其他算法長得多。我們使用大 O 符號（Big O Notation）來衡量這一點。
理解 Big O
如果一個算法的運行時間公式是 \( T(n) = n^2 + 5n + 10 \)，我們稱其階數（Order）為 \( O(n^2) \)。為什麼呢？因為當 \( n \) 變得非常大（比如一百萬）時，\( n^2 \) 項遠大於其他項，使得 \( 5n \) 和 \( 10 \) 變得微不足道。我們將最高次冪稱為主導項（dominant term）。
階數的層級
從最快（最有效率）到最慢（效率最低）：
\( O(1) \) [常數階] \( \subset O(\log n) \) [對數階] \( \subset O(n) \) [線性階] \( \subset O(n \log n) \) \( \subset O(n^2) \) [二次階] \( \subset O(n^3) \) [立方階] \( \subset O(a^n) \) [指數階] \( \subset O(n!) \) [階乘階]
你知道嗎？一個指數級算法 \( O(2^n) \) 是如此緩慢，以至於如果 \( n=100 \)，在普通計算機上運行完成所需的時間將超過宇宙的年齡！
數學技巧：整數和
在分析排序算法進行了多少次比較時，你通常需要這個公式：
前 \( n \) 個整數之和為 \( \sum_{r=1}^n r = \frac{1}{2}n(n+1) \)。
由於這裡的最高次冪是 \( n^2 \)，許多簡單的排序算法都屬於二次階（Quadratic Order） \( O(n^2) \)。
重點總結：效率是指運行時間如何縮放（scales）。如果一個 \( O(n^2) \) 算法處理 10 個項目需要 4 秒，那麼將項目加倍到 20 個時，它會花費 \( 2^2 = 4 \) 倍的時間（即 16 秒）。
4. 排序算法
排序是計算中最常見的任務。你需要掌握三種主要方法：
A. 氣泡排序（Bubble Sort）
比較前兩個項目。如果順序不對，就交換它們。然後移動到下一對。在第一輪「遍歷」（pass）結束時，最大的項目會像氣泡一樣「浮」到最後面。
• 效率： \( O(n^2) \)。對於大型列表來說，它很簡單但速度較慢。
B. 穿梭排序（Shuttle Sort）
與氣泡排序類似，但當你進行一次交換後，你會立即檢查該項目後方的項目，看是否需要進一步向後移動。
• 效率：同樣是 \( O(n^2) \)，但在實際應用中，通常比氣泡排序的交換次數少。
C. 快速排序（Quick Sort，Stage 2）
選擇一個「樞軸」（pivot，通常是第一個項目）。將所有小於樞軸的項目放在其左側，大於樞軸的放在右側。然後對新創建的兩個列表重複此過程。
• 效率：通常非常快，但在最壞情況下是 \( O(n^2) \)。
重點總結：除非題目另有說明，否則排序時始終從左邊開始！
5. 裝箱算法（Bin Packing）
這涉及將不同大小的物品裝入固定容量的「箱子」中。就像試圖有效地整理行李箱一樣。
策略（啟發式）
• 下一個適合（Next-Fit）：將物品放入當前箱子，直到下一個物品放不下為止。關閉該箱子並移至一個新箱子。（你永遠不會回頭處理舊箱子）。
• 首次適合（First-Fit）：對於每個新物品，嘗試將其放入你最先開始使用的箱子中。只有當現有箱子都放不下時，才開始使用一個新箱子。
• 遞減首次適合（First-Fit Decreasing, FFD）：先將物品按降序排列，然後使用「首次適合」。這通常是處理「離線」問題最有效的方法。
• 滿箱（Full Bin）：「手動」搜索物品組合，使箱子剛好 100% 裝滿。
記憶小幫手：線上（Online）與離線（Offline）
• 線上（Online）：你像物品到達時一樣即時進行裝箱（Next-Fit, First-Fit）。
• 離線（Offline）：你可以先看到所有物品並將它們進行排序（FFD）。
重點總結：FFD 通常是最好的，但你必須記得先對列表進行排序，否則會失分！
6. 背包問題（The Knapsack Problem）
想像你是個小偷，帶著一個只能承重一定重量的背包。你想要選擇能獲得最大利潤的物品，且背包不會破裂。
這是一個經典的優化（optimisation）問題。你必須在物品的質量和價值之間取得平衡。
快速回顧總結：算法是工具。我們使用追蹤（Tracing）來檢查它們是否有效，使用大 O（Big O）來檢查它們的速度，並使用啟發式（Heuristics）來解決諸如裝箱和排序之類的棘手問題。