歡迎來到演算法的世界！
歡迎踏上離散數學之旅的第一步！別被「演算法」(Algorithms) 這個名詞嚇到了。簡單來說，演算法就是一套用來解決問題的指令集——就像烘焙蛋糕的食譜，或是你綁鞋帶時遵循的步驟一樣。
在本章中，我們將學習如何清晰地表達這些指令，如何衡量演算法的「執行速度」，並探討一些經典的數據排序方法以及如何在網絡中找出最佳路徑。讓我們開始吧！
1. 什麼是演算法？
在開始編寫之前，我們需要了解一個「好的」演算法具備什麼條件。根據 OCR 課程大綱，每個演算法都必須具備以下特徵：
• 有限性 (Finite)： 它必須在有限步驟內結束。如果食譜叫你「永遠攪拌下去」，那絕對不是個好演算法！
• 確定性 (Deterministic)： 如果你使用相同的起始數據並遵循相同的步驟，結果必須永遠一致。
• 輸入/輸出 (Input/Output)： 它需要輸入初始數據 (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) 和 快速排序 (Quick Sort)。預設情況下，氣泡排序和穿梭排序均從列表的最左端開始。
氣泡排序 (Bubble Sort)
想像最大的數字很「重」，會沉到底部（列表末端），而較小的數字則會像氣泡一樣「浮」到頂部。
1. 比較前兩個項目。如果第一個比較大，就交換它們。
2. 向右移一步，比較下一對。重複此過程直到列表末端。
3. 最後一個數字現在已在正確位置。對剩餘的數字重複整個流程。
穿梭排序 (Shuttle Sort)
把它想像成一旦找到一個數字，就把它「穿梭」回正確位置。
1. 比較第一個和第二個項目。必要時交換。
2. 接著看第三個項目。將它與第二個比較。如果需要左移，就進行交換，然後再與第一個比較。
3. 之後的每個項目，都持續將其向左交換，直到它遇到比自己小的數值為止。
快速排序 (Quick Sort)
快速排序利用樞紐 (pivot) 來對列表進行分治 (divide and conquer)。
1. 選擇一個樞紐（在 OCR 中，除非另有說明，否則預設選擇子列表中的第一個數值）。
2. 將剩餘項目劃分為兩個子列表：小於樞紐的項目，以及大於或等於樞紐的項目，並保持它們原有的相對順序。
3. 將樞紐放置在兩個子列表之間（此時該樞紐的位置已固定）。
4. 對每個子列表遞迴套用此演算法，直到所有項目都被選為樞紐為止。
常見錯誤： 在氣泡排序中，許多學生會忘記，即使列表看起來已經排序完成，演算法仍必須完成它的輪次 (passes) 或達到正式的停止條件（在一整輪中沒有發生任何交換）才能正式結束。
重點總結： 氣泡排序和穿梭排序都是二次方的，即 \( O(n^2) \)。快速排序平均為 \( O(n \log n) \)，但最壞情況下的階數為 \( O(n^2) \)。
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) 就是一個邊上有「權重」（數字，如距離或成本）的圖。
戴克斯特拉演算法 (Dijkstra’s Algorithm，最短路徑)
這用於找出起始節點到其他節點之間的最短路徑。它是一個貪婪演算法，因為它每次都選擇下一個距離最近且尚未訪問過的節點。
• 階數： 二次方，\( O(n^2) \)，其中 \( n \) 是頂點數量。
最小連接器 (生成樹，Spanning Trees)
目標是用最小的邊總權重連接網絡中的每個節點，且不形成迴圈。
1. 克魯斯克爾演算法 (Kruskal’s Algorithm)： 將所有邊按權重升序排列。隨時挑選圖中可用的最短邊，只要它不會形成迴圈 (cycle)（封閉的環）。
2. 普林演算法 (Prim’s Algorithm，圖形或矩陣形式)： 從一個起始頂點開始。總是挑選連接任何當前已訪問頂點與未訪問頂點的最短邊。在距離矩陣／表格形式中，劃掉所選頂點的列 (row)，並在活動的行 (columns) 中圈出最小值。
快速回顧：Dijkstra vs. Prim/Kruskal
• 使用 Dijkstra 來找出從起始頂點到其他頂點的路徑。
• 使用 Prim 或 Kruskal 來以最低成本將所有頂點連接起來。
重點總結： Prim 和 Kruskal 演算法都能找到最小生成樹 (MST)。以頂點數量為基準，兩者的階數都是三次方 (cubic order)，即 \( O(n^3) \)。
演算法階數總表
• 排序 (Bubble/Shuttle)： \( O(n^2) \) (二次方)
• 排序 (Quick Sort)： 平均 \( O(n \log n) \)，最壞情況 \( O(n^2) \)
• 最短路徑 (Dijkstra)： \( O(n^2) \) (二次方)
• 最小連接器 (Prim/Kruskal)： \( O(n^3) \) (三次方)
你已經完成了演算法章節！繼續練習你的追蹤表和排序輪次——持之以恆是掌握離散數學的關鍵。你一定行的！