歡迎來到決策數學 1：演算法 (Algorithms)！
你好！如果你正在修讀決策數學 (Decision Mathematics)，演算法就是整個科目的基石。別擔心這個術語聽起來很複雜；演算法 (Algorithm) 其實就是一套超級精確的指令集。把它想像成解決特定問題的「終極食譜」吧！
在本章中，我們將學習如何：
- 了解什麼才算是優秀的演算法。
- 逐步追蹤 (Trace) 演算法（這是考試的核心技能！）。
- 比較不同的排序與搜尋方法（例如氣泡排序法 Bubble Sort 與快速排序法 Quick Sort）。
- 評估演算法的效率。
掌握這些概念，將能讓你充滿信心地應對未來所有 D1 的課題，從圖論 (Graphs) 到網絡 (Networks) 皆是如此！
第一節：演算法的定義與理解
什麼是演算法？
演算法是一組有限且定義明確的指令序列，旨在執行特定任務或解決特定類型的問題。它們是電腦和決策者執行工作的「操作指南」。
有效演算法的基本特徵
要成為一個數學上的演算法，它必須具備五個關鍵特徵：
- 輸入 (Input)： 必須接收零個或多個外部數據。（例如：一串需要排序的數字列表。）
- 輸出 (Output)： 必須產生至少一個結果。（例如：排序後的列表。）
- 明確性 (Definiteness)： 每項指令必須清晰且無歧義。（不能留有猜測空間！）
- 有限性 (Finiteness)： 無論輸入為何，演算法必須在有限的步驟後結束。（它不能無限循環下去。）
- 有效性 (Effectiveness)： 每個步驟必須是可行的，並且能在有限的時間內完成。
類比：想像你在烤蛋糕。如果食譜（演算法）沒有明確告訴你該用多少麵粉（明確性），或者要求你烤無限長的時間（有限性），那這就是一個糟糕的食譜！
追蹤 (Tracing) 與流程圖 (Flow Charts)
要理解一個演算法，尤其是在考試環境下，你必須具備追蹤 (Trace) 的能力。追蹤（或稱「乾跑」，dry run）是指按步驟執行指令，並記錄下每個階段的變量和決策。這通常會使用追蹤表 (Trace Table) 來完成。
流程圖中的關鍵符號
演算法通常會用流程圖來視覺化呈現：
- 橢圓形： 流程的開始或結束。
- 平行四邊形： 輸入或輸出（獲取數據或顯示結果）。
- 矩形： 處理或指令（動作，例如設定 \(x = 5\) 或計算總數）。
- 菱形： 決策或條件（一個有兩條路徑的問題，通常是「是/否」或「真/假」）。
重點小結： 演算法是一種精確、結構化且有限的問題解決方法。我們透過追蹤來證明它的正確性。
第二節：衡量演算法的性能（效率）
如果你有兩個都能解決相同問題的演算法，你該如何決定哪一個更好？你需要比較它們的效率 (Efficiency)。
效率衡量的是當輸入數據的規模 (\(n\)) 增加時，演算法所需的資源（通常是時間或記憶體）如何變化。
時間複雜度的定性分析
在 D1 中，你需要了解演算法所需的操作數量是如何隨著輸入項目數量 \(n\) 的增加而變化的。
效率（或稱為階數，Order）是由當 \(n\) 變得非常大時，主導運行時間的那一項所決定的。
我們將性能分為幾個基本類別（由好到壞）：
- 對數時間 (\(\log n\))： 所需時間增長非常緩慢。每一個步驟都能減半剩餘的工作量。（優秀！）
- 線性時間 (\(n\))： 所需時間與項目數量成正比。如果你將輸入加倍，所需時間也會加倍。（良好。）
- 二次時間 (\(n^2\))： 所需時間隨著輸入的增加而迅速增長（呈二次方增長）。如果你將輸入加倍，時間會增加為原來的四倍 (\(2^2 = 4\))。（較差，對於大型數據集來說非常糟糕。）
這為什麼重要？ 對於 10 個項目的列表，\(n^2\) 的演算法可能很快，但對於 100 萬個項目的列表，\(n\) 或 \(n \log n\) 的演算法將會遠勝於前者。
記憶小撇步：始終追求更低的指數或增長率。\(\log n\) 遠小於 \(n\)，而 \(n\) 又遠小於 \(n^2\)。
\(\log n\) (最快) < \(n\) (中等) < \(n^2\) (最慢)
重點小結： 效率是指當列表大小增加時，演算法變慢的程度。我們希望演算法能具備良好的擴展性。
第三節：排序演算法
排序演算法將列表中的項目按特定順序排列（升序或降序）。
1. 氣泡排序法 (Bubble Sort)
氣泡排序法是最容易理解的排序演算法，但也是最慢的演算法之一。它的運作方式是反覆遍歷列表，比較相鄰元素，若順序錯誤則交換它們。
氣泡排序的過程（升序排列）
- 第 1 輪 (Pass 1)： 從列表開頭開始，比較前兩個項目。如果第二個比第一個小，則交換它們。
- 向後移動一個位置，比較接下來的兩個項目（第二和第三個）。如有需要，進行交換。
- 重複上述過程直到列表末尾。最大的項目會像氣泡一樣「浮」到列表末尾的正確位置。
- 第 2 輪 (Pass 2)： 重複該過程，但比上一輪提早一個元素結束（因為最後一個項目已經歸位）。
- 重複此過程，直到某一次遍歷過程中沒有發生任何交換為止。
助記：想像汽水裡的氣泡。最重的物體（最大的數字）會沉到最底部（列表末尾）。
性能： 氣泡排序是一個 \(n^2\) 的演算法（二次方）。這使得它在處理大型數據集時效率極低。
常見錯誤： 學生經常忘記在後續的輪次中提早一個元素停止比較。請記得，每一輪過後，未排序部分的長度都要減一。
2. 快速排序法 (Quick Sort)
快速排序法通常是此階段課程中所教授的最快排序演算法。它採用「分治法」(divide and conquer) 的策略。
快速排序的過程
- 選擇樞紐 (Pivot)： 從列表中選擇一個元素，通常是第一個項目，作為樞紐 (pivot)。
- 分區 (Partitioning)： 重新排列其餘元素，使得所有小於樞紐的元素都放在它的左邊，而所有大於樞紐的元素都放在它的右邊。此時樞紐已處於其最終的正確位置。
- 遞迴 (Recursion)： 對樞紐左側的子列表和右側的子列表重複上述過程（遞迴），直到所有子列表的長度為 0 或 1（這意味著它們已經排好序）。
性能： 快速排序通常為 \(n \log n\)，這比氣泡排序快得多。然而，如果樞紐選擇得很差（例如每次都選到最大或最小值），其最差情況的性能會退化為 \(n^2\)。
你知道嗎？在實際計算機科學中，快速排序常被使用，因為儘管它有理論上的最差情況，但它的平均性能非常出色。
重點小結： 快速排序之所以快 (\(n \log n\))，是因為它將問題進行了拆分。氣泡排序之所以慢 (\(n^2\))，是因為它反覆檢查相鄰的配對。
第四節：搜尋演算法
搜尋演算法用於在列表中定位特定的目標項目。
1. 線性搜尋法 (Linear Search)
這是最直觀的搜尋方法。它只是從頭開始，逐一檢查列表中的每個項目，直到找到目標或列表檢查完畢為止。
要求： 無。列表不需要已排序。
過程：
- 從第一個元素開始。
- 將該元素與目標進行比較。
- 如果匹配，停止並報告成功。
- 如果不匹配，移動到下一個元素。
- 重複直到列表檢查完畢。
性能： 線性搜尋是一個 \(n\) 的演算法（線性）。在最壞的情況下（項目在最後或根本不在列表中），你必須檢查每個項目，使得時間與 \(n\) 成正比。
類比：為了找到某個特定品牌的麥片，在大型超市裡逛遍每一個貨架。
2. 二分搜尋法 (Binary Search)
二分搜尋法比線性搜尋快得多，但它有一個關鍵的前提條件。
關鍵要求：列表必須已排序。
二分搜尋的過程
- 尋找中間點： 找出列表的中間項目。
- 比較： 將中間項目與目標值進行比較。
- 決策：
- 如果中間項目就是目標，停止。成功！
- 如果目標小於中間項目，忽略列表的後半部分。
- 如果目標大於中間項目，忽略列表的前半部分。
- 重複： 將剩餘的部分視為新的列表並重複上述過程（找新的中間點、比較、排除一半）。
二分搜尋之所以極具效率，是因為它在每次比較後都會排除掉剩下數據的一半。
性能： 二分搜尋是一個 \(\log n\) 的演算法（對數）。這速度極快。如果你有一個 1,000 個項目的列表，你大約只需要 10 個步驟就能找到目標 (\(\log_2 1000 \approx 10\))。
常見錯誤： 試圖對未排序的列表使用二分搜尋。如果列表沒有排序，二分搜尋會徹底失敗。
排序演算法
- 氣泡排序： 簡單。比較相鄰配對。性能：\(n^2\) (慢)。
- 快速排序： 複雜。使用樞紐與遞迴。性能：\(n \log n\) (平均速度快)。
搜尋演算法
- 線性搜尋： 簡單。按順序檢查一切。性能：\(n\)。
- 二分搜尋： 高效。反覆將列表減半。必須先排序。性能：\(\log n\)。
結論與最後建議
你已經掌握了演算法的基礎知識！請記住，決策數學的核心就是尋找解決問題的最佳方法。效率就是關鍵！
理解這些概念的最佳方式是透過練習：
- 畫出氣泡排序追蹤表的步驟，直到這變成你的本能。
- 練習為快速排序選擇樞紐並對列表進行分區。
- 每當題目要求進行搜尋時，一定要確保先檢查「列表已排序」這一條件。
繼續努力，保持優異表現！