歡迎來到「演算法比較」！

你有沒有留意過，解決一個問題往往不只一種方法？例如：收拾房間、上學的路線，或者找出一對配對的襪子。有些方法非常快捷，有些方法雖然耗時較長，但步驟卻簡單得多。

在電腦科學中，我們也面對完全相同的挑戰。針對同一個計算問題，程式員可以設計出幾種不同的演算法（Algorithm）。但我們應該如何決定選用哪一個？在這一章中，我們將會運用邏輯推理來比較各個演算法，並找出哪一個演算法針對特定工作擁有最高的效用（Utility，即是否切合用途）。

如果一開始覺得有點抽象，千萬不要擔心！我們會用清晰的生活例子，一步一步拆解每一個概念。

1. 甚麼是「演算法」和「效用」？

在開始比較之前，我們先來複習兩個核心定義：

演算法（Algorithm）： 一組清晰明確、按部就班的指令步驟，旨在執行特定工作或解決計算問題。

效用（Utility）： 演算法應用於特定情境或數據集時的整體合適度、成效和實用價值。你可以將效用理解為回答這個問題：「這個演算法對於我特定的工作來說，有多切合用途？」

比較演算法的 5 大準則

當電腦科學家比較不同的演算法時，會根據以下五個關鍵準則進行評估：

1. 正確性（Correctness）： 對於所有有效的輸入數據，演算法能否可靠地產生正確的輸出？一個運算極快但給出錯誤答案的演算法，效用絕對是零！

2. 效率（時間 / 速度，Efficiency）： 演算法需要執行的步驟和比較次數，與輸入數據的大小（以 \(n\) 表示）有何關係？

3. 空間 / 記憶體效率（Space / Memory Efficiency）： 演算法運行期間，電腦需要多少額外的工作記憶體或儲存空間？

4. 簡易度與可讀性（Simplicity and Readability）： 程式員閱讀、理解、追蹤（Trace）和維護這些程式碼的難易程度如何？

5. 前置條件與限制（Preconditions and Constraints）： 演算法開始運行前，數據必須處於甚麼狀態？例如：列表是否必須先排列好次序？

重點提示： 演算法本身沒有絕對的「好」或「壞」。它的效用完全取決於具體情境、數據規模，以及數據本身是否已經排序。

2. 案例研究 1：搜尋演算法（Searching Algorithms）

電腦科學中一個經典的問題，是在一串項目清單中尋找特定的目標值（就像在學校點名簿中尋找某位學生的名字一樣）。

演算法 A：線性搜尋法（Linear Search）

運作原理： 線性搜尋法從列表的最開頭開始，逐一（按順序）檢查每個項目，直到找到目標項目或到達列表末尾為止。

生活比喻： 想像一下在一堆亂七八糟的衣服堆中尋找你最喜歡的襯衫。你必須把衣服一件一件拿起來看，直到找到為止。

前置條件： 無！它適用於未排序和已排序的列表。

最佳情況效用： 1 次比較（如果目標剛好是列表的第一個項目）。

最差情況效用： 對於大小為 \(n\) 的列表需要進行 \(n\) 次比較（如果目標在列表的最末尾，或者根本不在列表中）。

優點： 概念和編程都非常簡單；完全適用於未排序的數據。

缺點： 處理龐大數據集時效率低且速度慢。

演算法 B：二分搜尋法（Binary Search）

運作原理： 二分搜尋法採用分治法（Divide and conquer）策略。它首先檢查列表正中間的項目。如果中間項目剛好是目標，搜尋立即完成！如果目標比中間項目小，演算法就會捨棄列表後半部分的所有數據；如果目標較大，則捨棄前半部分。接著在剩下的一半數據中重複這個過程，直到找到目標為止。

生活比喻： 想像在實體字典中查字。你先翻到正中間。如果你要查的字以「T」開頭，而中間那頁是「M」，你就可以直接略過前半本字典，只在後半本中繼續尋找。

前置條件： 數據必須先按升序或降序排列好。

最佳情況效用： 1 次比較（如果目標剛好落在最初的中位數位置）。

最差情況效用： 比較的次數與 \(\log_2(n)\) 成正比，因為每檢查一次，搜尋範圍就會減半。

優點： 速度極快，在處理海量數據時尤為明顯（例如在 1,000,000 個項目中搜尋，最多只需約 20 次比較！）。

缺點： 如果列表未經排序，則完全無法使用。

比較效用：線性搜尋法 VS 二分搜尋法

哪一種搜尋演算法的效用更高？

• 對於小型列表或經常變動且未排序的數據，線性搜尋法的效用較高。為甚麼？因為單純為了執行二分搜尋而特意先將未排序的列表排序，所耗費的時間和資源往往得不償失。

• 對於龐大、固定不變或已經排序的數據集，二分搜尋法在速度和效用上都遠遠勝出。

重點提示： 線性搜尋法勝在靈活，適用於任何列表；但面對龐大且已排序的列表時，二分搜尋法的速度則快得多。

3. 案例研究 2：排序演算法（Sorting Algorithms）

另一個電腦科學的基礎問題是排序：將混亂的項目列表按數值大小或字母順序重新排列。

演算法 1：冒泡排序法（Bubble Sort）

運作原理： 它會走訪整個列表，比較相鄰（並排）的兩個項目，如果次序錯誤就將它們調換（Swap）。它會重複進行完整的走訪，直到在其中一輪走訪中完全沒有進行過任何調換，這代表列表已經排序完成。

效用： 易於追蹤和編寫程式碼；如果列表本身已經大致排好，運行效率會很高；但對於龐大且混亂的列表，速度非常緩慢且效率低下。

演算法 2：插入排序法（Insertion Sort）

運作原理： 它會逐步建立已排序的列表，每次處理一個項目。它取出下一個未排序的項目，並將其插入到前面已經排序好的序列中的正確位置。

生活比喻： 想想看你在手中整理撲克牌的方法。你每次摸一張新牌，然後把它插入手中已整理好牌堆的適當位置。

效用： 適用於小型列表以及部分已排序的列表；佔用極少的額外記憶體；但對於龐大且逆序排列的列表效率較低。

演算法 3：合併排序法（Merge Sort）

運作原理： 這是一種分治演算法，它會不斷將列表對半拆分，直到剩下單一元素（長度為 1 的子列表）。接著，它會將這些子列表按正確順序逐步合併，直到還原為一個完整排序好的列表。

效用： 在處理大型數據集時表現高度穩定且速度極快；然而，在合併過程中，它需要額外的工作記憶體來暫存這些拆分出來的子列表。

比較排序效用：速度 VS 記憶體空間

• 冒泡排序法與插入排序法： 當數據量較小、數據幾乎已排好序，或者記憶體空間非常有限時具有高效用（因為它們直接在原列表上「就地」排序）。

• 合併排序法： 在處理大型數據集時具有高效用，特別是當快速、穩定的排序速度是首要考慮，且電腦擁有足夠的工作記憶體時。

重點提示： 排序演算法涉及權衡取捨（Trade-offs）。像合併排序法這種高效的分治演算法在大型數據集上運行迅速，但需要額外的記憶體來儲存拆分的子列表。

4. 常見陷阱與誤解

比較演算法時，請特別留意以下常見盲點：

陷阱 1：誤以為「某一個演算法永遠是最好的」
正解： 沒有任何單一演算法能完美適用於所有情況。例如二分搜尋法在大型列表上比線性搜尋法快得多，但如果數據無法預先排序，它就完全派不上用場！

陷阱 2：忘記二分搜尋法的前置條件
正解： 永遠要先檢查列表是否已經排序。你無法在未排序的列表上進行二分搜尋。

陷阱 3：以為「程式碼行數越少 ＝ 演算法越快」
正解： 程式碼的行數並不決定執行速度。一個包含執行 \(n\) 次迴圈的簡短演算法，耗時可能遠遠長於一段較長但設計更精妙的演算法。

陷阱 4：混淆「比較」（Comparisons）與「調換」（Swaps）
正解： 在冒泡排序法等演算法中，每當演算法檢視兩個項目時都會進行一次比較，但只有在它們順序錯誤時才會執行調換。

陷阱 5：以為線性搜尋法每次都必須檢查所有項目
正解： 線性搜尋法只要一找到目標項目就會立即停止（這就是為甚麼它的最佳情況只需 1 次比較！）。只有在最差情況下，它才需要檢查全部 \(n\) 個項目。

5. 快速複習清單

在學習下一部分之前，請確保自己能夠回答以下核心問題：

• 你能用自己的話定義演算法和效用嗎？

• 你能說出比較演算法的 5 大準則嗎（正確性、速度、記憶體、簡易度、前置條件）？

• 在甚麼情況下，線性搜尋法的效用會高於二分搜尋法？

• 執行二分搜尋法之前，必須具備甚麼基本前置條件？

• 如果記憶體空間非常有限，為甚麼程式員可能會選擇冒泡排序法或插入排序法，而不是合併排序法？