歡迎來到演算法的世界！
歡迎踏上離散數學之旅的第一步！別被「演算法」(Algorithms) 這個名詞嚇到了。簡單來說，演算法就是一套用來解決問題的指令集——就像烘焙蛋糕的食譜，或是你綁鞋帶時遵循的步驟一樣。
在本章中，我們將學習如何清晰地表達這些指令，如何衡量演算法的「執行速度」，並探討一些經典的數據排序方法以及如何在網絡中找出最佳路徑。讓我們開始吧！
1. 什麼是演算法？
在開始編寫之前，我們需要了解一個「好的」演算法具備什麼條件。根據 OCR 課程大綱，每個演算法都必須具備以下特徵：
• 有限性 (Finite)： 它必須在有限步驟內結束。如果食譜叫你「永遠攪拌下去」，那絕對不是個好演算法！
• 確定性 (Deterministic)： 如果你使用相同的起始數據並遵循相同的步驟，結果必須永遠一致。
• 輸入/輸出 (Input/Output)： 它需要輸入初始數據，並在最後給出答案（輸出）。
必須記住的關鍵術語
貪婪演算法 (Greedy Algorithm)： 這類演算法在每一步都選擇當下看起來「最好」的選項，而不考慮長遠影響。想像你在吃自助餐，每次都拿盤子裡最大塊的披薩——這就是貪婪策略！
啟發式方法 (Heuristic)： 這是一種「經驗法則」或捷徑。它未必每次都能給出 100% 完美的答案，但通常「夠好」，而且比檢查所有可能性快得多。
遞迴 (Recursive)： 指演算法調用自身。想像俄羅斯套娃；為了到達最中心，你必須不斷打開較小的同款娃娃。
快速回顧：基本概念
輸入 (Input) → 演算法 (指令) → 輸出 (Output)
例子： 食材 → 食譜 → 蛋糕
2. 處理演算法：追蹤與解讀
最重要的技能之一就是「追蹤」(tracing) 演算法。這意味著你要像電腦一樣，透過追蹤表 (trace table) 一行一行地執行指令。
演算法可以透過流程圖 (flow diagrams)（使用框圖和箭頭）或虛擬碼 (pseudo-code)（使用類似電腦程式碼但語句通順的英文）來呈現。
你需要用到的數學工具
在虛擬碼中，你經常會看到這兩個函數：
1. \( \text{INT}(x) \)：意指「向下取整」，即捨去小數點後的部分。例如，\( \text{INT}(4.7) = 4 \) 且 \( \text{INT}(4.1) = 4 \)。
2. \( \text{ABS}(x) \)：這是「絕對值」。它只是將數字轉為正數。所以，\( \text{ABS}(-5) = 5 \) 且 \( \text{ABS}(5) = 5 \)。
別擔心，一開始可能會覺得有點複雜！ 追蹤的關鍵在於條理。請使用一個表格，為每個變數設立一欄，並在執行過程中隨時更新數值。
重點總結： 追蹤能幫你在不實際編寫程式的情況下，理解演算法到底在達成什麼目標。
3. 排序策略：數據的秩序
排序是離散數學中非常重要的一部分。我們專注於兩種主要方法：氣泡排序 (Bubble Sort) 和 穿梭排序 (Shuttle Sort)。兩者都從列表的最左端開始。
氣泡排序 (Bubble Sort)
想像最大的數字很「重」，會沉到底部（列表末端），而較小的數字則會像氣泡一樣「浮」到頂部。
1. 比較前兩個項目。如果第一個比較大，就交換它們。
2. 向右移一步，比較下一對。重複此過程直到列表末端。
3. 最後一個數字現在已在正確位置。對剩餘的數字重複整個流程。
穿梭排序 (Shuttle Sort)
把它想像成一旦找到一個數字，就把它「穿梭」回正確位置。
1. 比較第一個和第二個項目。必要時交換。
2. 接著看第三個項目。將它與第二個比較。如果需要左移，就進行交換，然後再與前一個比較。
3. 基本上，每檢查一個新項目，就持續將其向左交換，直到它遇到比自己小的數字為止。
常見錯誤： 在氣泡排序中，許多學生會忘記，即使列表看起來已經排序完成，演算法仍必須完成它的「輪次」(passes) 或達到特定的「停止條件」（例如在一輪中沒有發生任何交換）才能正式結束。
重點總結： 這兩種排序演算法都是「二次方」(quadratic) 的，意味著如果將項目數量翻倍，所需的時間大約會變成原來的四倍！
4. 裝箱問題：如何裝好裝滿？
我們該如何將物品裝入固定大小的箱子中？這些屬於啟發式 (heuristic)（捷徑）方法。它們通常分為「線上」(online)（物品隨到隨裝）或「離線」(offline)（開始前先看過所有物品）。
• 首次適應 (Next-Fit，線上)： 把物品放入當前的箱子。如果不夠放，就永遠關閉該箱子並開啟一個新的。
• 首次適應 (First-Fit，線上)： 嘗試將物品放入建立的第一個箱子。如果放不下，試試第二個，接著第三個，依此類推。只有當所有現有箱子都放不下時，才開啟一個新的箱子。
• 首次適應遞減 (First-Fit Decreasing，離線)： 先將物品按降序（從大到小）排列，然後使用 First-Fit 方法。這通常能得到更好的結果！
• 裝滿箱子 (Full Bin，啟發式)： 尋找能將箱子容量剛好填滿到 100% 的物品組合。
你知道嗎？ First-Fit Decreasing 是「離線」的，因為你必須事先知道所有物品才能進行排序。而 Next-Fit 是「線上」的，因為你可以像在輸送帶上一樣，來一個物品就裝一個箱子！
5. 演算法的「階數」(Big O 符號)
我們需要一種方法來衡量效率。我們使用階數 (Order) 符號，例如 \( O(n^2) \) 或 \( O(n^3) \)，其中 \( n \) 是問題的「規模」（例如列表中項目的數量）。
• 如果演算法是 \( O(n) \)，項目翻倍，時間只需 2 倍。
• 如果是 \( O(n^2) \)，項目翻倍，時間變成 4 倍 (\( 2^2 \))。
• 如果是 \( O(n^3) \)，項目翻倍，時間變成 8 倍 (\( 2^3 \))。
記憶小撇步： 當看到執行時間公式（如 \( T(n) = 3n^2 + 5n + 10 \)）時，階數取決於「主導項」（次數最高的那一項）。所以這就是 \( O(n^2) \)。
重點總結： 了解階數能讓你根據小規模的測試結果，預測龐大的電腦任務需要花費多少時間。
6. 網絡演算法：尋找最佳路徑
先決條件：請記住，網絡 (network) 就是一個邊上有「權重」(weights)（如距離或成本）的圖。
戴克斯特拉演算法 (Dijkstra’s Algorithm，最短路徑)
這用於找出起始點到網絡中其他每個點的最短路徑。它是一個貪婪演算法，因為它每次都選擇下一個「距離最近」且尚未訪問過的節點。
• 階數： 二次方，\( O(n^2) \)，其中 \( n \) 是頂點數量。
最小連接器 (生成樹，Spanning Trees)
目標是用邊的總權重最小化來連接網絡中的每個節點。想像要以最少的管線將房屋連接到主水管。
1. 克魯斯克爾演算法 (Kruskal’s Algorithm)： 隨時挑選圖中權重最小的邊，只要它不會形成「迴圈」(cycle)（封閉的環）。
2. 普林演算法 (Prim’s Algorithm)： 從一個節點開始。總是挑選一條邊，連接一個「已訪問」的節點與一個「未訪問」的節點，且權重最小。
快速回顧：Dijkstra vs. Prim/Kruskal
• 使用 Dijkstra 來找出從 A 到 B 的路徑。
• 使用 Prim 或 Kruskal 來以最低成本將所有節點連接起來。
重點總結： Prim 和 Kruskal 演算法都能找到最小生成樹 (MST)，但使用了不同的策略。兩者都是三次方階數 (cubic order)，即 \( O(n^3) \)。
演算法階數總表
• 排序 (Bubble/Shuttle)： \( O(n^2) \) (二次方)
• 最短路徑 (Dijkstra)： \( O(n^2) \) (二次方)
• 最小連接器 (Prim/Kruskal)： \( O(n^3) \) (三次方)
你已經完成了演算法章節！繼續練習你的追蹤表和排序輪次——持之以恆是掌握離散數學的關鍵。你一定行的！