歡迎來到演算法的世界！
在本章中，我們將深入探索現代科技的「心臟」。從 Netflix 如何推薦影集，到物流貨車如何規劃最快路徑，演算法 (Algorithms) 無處不在。在進階數學中，我們學習演算法不僅是為了找到問題的解法，更重要的是了解如何以「高效」的方式去解決。別擔心，如果這聽起來有點像「計算機科學」，請放心——我們會把它拆解成簡單且合乎邏輯的步驟！
1. 什麼是演算法？
演算法的本質就是一套指令。試著把它想像成烘焙蛋糕的食譜：如果你嚴格按照步驟操作，每次都應該會得到同樣的結果。
演算法的核心特徵：
- 有限性 (Finiteness)： 必須有明確的起點（初始狀態）和終點。它不能無限循環！
- 輸入 (Input)： 開始時給予的資料。
- 輸出 (Output)： 演算法產生的結果或解決方案。
- 變數 (Variables)： 就像暫時性的「儲存盒」，用來存放演算法運作過程中會改變的數字或標籤。
演算法的呈現方式：
你通常會透過以下三種格式看到演算法：
- 文字描述 (Written English)： 用通俗語言寫成的逐步指令。
- 流程圖 (Flowcharts)： 利用方框和箭頭組成的視覺化地圖。
- 虛擬碼 (Pseudocode)： 介於人類語言與電腦程式碼之間的格式（例如："Let \(i = i + 1\)" 意思是用 \(i\) 的當前值加 1 後的結果來取代 \(i\)）。
快速複習： 演算法必須是有限的（必須有終止）且決定性的（遵循步驟會得出明確的結果）。
2. 演算法複雜度 (Algorithmic Complexity)
並非所有演算法都是平等的。有些很快，而有些在問題「規模」變大時會變得非常慢。這就是我們所說的複雜度 (Complexity)。
「大 O」符號 (Big O Notation)
我們使用階數符號 (Order Notation) 來描述演算法所需時間如何隨輸入規模 (\(n\)) 增加而增長。在本課程中，你需要特別了解二次複雜度 (Quadratic Complexity)，寫作 \(O(n^2)\)。
例子： 如果你有 10 個項目，排序需要 100 秒，而 20 個項目則需要 400 秒，這代表時間隨著項目增加的倍數呈現平方增長（\(2^2 = 4\) 倍）。這就是 \(O(n^2)\) 的特性。
避免常見錯誤： 不要把「問題的規模 (size of the problem)」與「數字的大小 (value of the numbers)」搞混。如果你正在排序一個列表，\(n\) 指的是列表中有多少個數字，而不是數字本身有多大。
3. 排序演算法：快速排序法 (Quick Sort)
排序是演算法中最常見的任務。快速排序法 (Quick Sort) 是一種強大的方法，它利用一個樞紐 (pivot) 將列表分成更小的部分。
如何執行快速排序（遞增）：
- 選擇一個樞紐 (pivot)（通常是列表中的第一個或中間項目）。
- 將其他所有項目與樞紐進行比較。
- 將小於樞紐的項目移至左側子列表，大於樞紐的項目移至右側子列表。
- 現在，樞紐已處於其最終正確位置。
- 對新的子列表重複上述過程，直到每個項目都成為過一次樞紐。
重要重點：
- 比較 (Comparisons)： 每當你詢問「這個數字是否大於樞紐？」時，這就算作一次比較。
- 交換 (Swaps)： 每當你移動一個項目時，這就算作一次交換。
- 最差情況 (Worst Case)： 快速排序法的最差情況複雜度為 \(O(n^2)\)。
關鍵要點： 一旦一個數字被選為樞紐並形成了子列表，該樞紐在接下來的演算法過程中將永遠固定在那裡，不會再移動！
4. 打包演算法 (Bin Packing)
想像你有幾個重量不同的物品，想要將它們放進有重量限制的箱子中。這是一個經典的「最佳化」問題。
啟發式演算法 (Heuristic Algorithms)
啟發式演算法是一種「經驗法則」。這種方法能快速找到一個「不錯」的解決方案，但不保證能找到「最完美」(optimal) 的方案。當計算完美方案需要耗費電腦多年時間時，我們就會使用這種方法！
你需要知道的三種策略：
- 首次適應法 (First Fit, FF)： 按給定順序取出每個項目，將其放入第一個有足夠空間的箱子中。
- 遞減首次適應法 (First Fit Decreasing, FFD)： 首先將項目按遞減順序（從大到小）排列，然後使用首次適應法。這通常會高效得多！
- 填滿箱子法 (Full Bin)： 尋找能將箱子剛好裝滿的物品組合。先處理這些組合，然後再打包剩下的物品。
類比： 首次適應法就像你在超市挑選貨品時，直接把物品裝進購物袋。而遞減首次適應法就像先把你所有的採購物品放在櫃檯上，在裝入巧克力棒等小東西之前，先放進巨大的麥片盒。
你知道嗎？ 首次適應法與遞減首次適應法的最差情況複雜度都是 \(O(n^2)\)。
5. 演算法的證明與修正
我們如何知道一個演算法對所有可能的輸入都有效呢？我們使用數學證明。
窮舉證明法 (Proof by Exhaustion)
如果可能的輸入數量很小，你可以簡單地測試每一種情況。如果全部測試都成功，則證明該演算法對於這組數據是正確的。
反例證明法 (Disproof by Counter-example)
要證明一個演算法不正確，你只需要找到一個它失敗的特定例子。例如，如果某個打包演算法聲稱總是使用最少數量的箱子，但你發現有一組列表它用了三個箱子而不是兩個，那麼你就已經證明該演算法是錯誤的！
關鍵要點： 如果題目要求你「修正 (repair)」一個演算法，請尋找邏輯錯誤發生的步驟——通常是一個「大於」符號應該改為「大於或等於」，或者是一個索引值從 1 開始而不是從 0 開始。
總結：核心要點
- 演算法 (Algorithms) 是有限且邏輯清晰的指令集合。
- 複雜度 \(O(n^2)\) 意味著如果輸入量倍增，所需時間大約會增加為四倍。
- 快速排序法 (Quick Sort) 使用樞紐來組織列表；它很高效，但在最差情況下為 \(O(n^2)\)。
- 打包演算法 (Bin Packing) 使用啟發式方法（FF 或 FFD）來尋找「不錯」而非「完美」的解決方案。
- 證明： 使用窮舉法證明小規模情況；使用反例證明一般規則是錯誤的。