歡迎來到演算法分類！

你好！在本章中，我們將探討計算機科學家是如何對不同的演算法進行「評分」與分組的。你可以把演算法想像成食譜：有些食譜製作迅速但過程混亂，而有些則費時但能做出完美的成品。看完這份筆記後，你將能夠判斷兩種解決問題的方法，並根據效率決定哪一個才是「贏家」。

如果起初覺得有點複雜，別擔心！ 我們基本上只是在學習如何比較工具，找出最適合特定工作的那個。

1. 什麼是「好」的演算法？

在分類之前，我們需要知道我們在尋找什麼。根據課程大綱，我們從以下三個主要方面來評估一個電腦系統（及其演算法）：

  • 正確性 (Correctness)： 它是否真的解決了問題並給出正確答案？
  • 效率 (Efficiency)： 它的執行速度有多快（時間效率），以及它佔用多少記憶體（空間效率）？
  • 可維護性 (Maintainability)： 程式碼是否容易讓其他人閱讀並在日後進行修正？

效率的取捨 (The Efficiency Trade-off)

在計算機科學中，我們經常需要在速度與記憶體之間做出選擇。這就像搬家一樣：你可以開一輛小型車來回跑 20 趟（記憶體使用量低，但耗時長），或者僱用一輛大型卡車一次搞定（佔用很多「空間」，但速度極快）。

快速複習：評估準則

記住 CEM：
C - Correctness (正確性：它能運作嗎？)
E - Efficiency (效率：它夠快/夠精簡嗎？)
M - Maintainability (可維護性：我讀得懂嗎？)

2. 搜尋演算法分類

搜尋是指在列表中尋找特定項目。我們主要關注兩種類型：線性搜尋 (Linear Search) 和 二元搜尋 (Binary Search)。

線性搜尋 (Linear Search)

這是最「簡單」的搜尋方式。你從列表的第一個項目開始，逐一檢查每一個項目，直到找到你要找的目標，或者查完整個列表。

  • 效率： 通常較低。如果你的目標在一百萬個項目的列表末端，你就必須執行一百萬次搜尋！
  • 條件： 適用於任何列表（無論是否有序）。

二元搜尋 (Binary Search)

這是一種更聰明的「分治法」(Divide and Conquer) 演算法。它會先跳到列表的中間，判斷目標是在上半部還是下半部，然後捨棄不需要的那一半。重複這個步驟，直到找到目標為止。

  • 效率： 非常高。隨著列表長度增加，它的尋找速度遠快於線性搜尋。
  • 條件： 列表必須先經過排序 (ordered)。

類比：想像你在字典裡找一個詞。線性搜尋就像是從 'A' 開始閱讀每一個字。而二元搜尋則是把書翻到中間，看看你的目標詞是在那一頁之前還是之後，然後根據判斷繼續翻閱。

常見的錯誤陷阱

切記： 你不能在雜亂、未排序的列表中使用 二元搜尋。如果列表沒有排序，你就只能使用 線性搜尋。

重點總結： 對於小型或未排序的列表，請使用 線性搜尋。對於大型、已排序的列表，請使用 二元搜尋 以獲得更好的時間效率。

3. 排序演算法分類

排序是指將混亂的列表按順序排列（例如按字母順序或由小到大）。我們來看 氣泡排序 (Bubble Sort) 和 合併排序 (Merge Sort)。

氣泡排序 (Bubble Sort)

這個演算法會以「回合」方式掃描列表。它會比較相鄰的兩個項目，如果順序錯誤就交換它們。最大的項目會像氣泡一樣「浮」到列表的末端。

  • 時間效率： 對於大型列表來說，通常效率極低且緩慢。
  • 記憶體效率： 非常優異，因為它是「原地」(in-place) 排序，不需要額外的儲存空間。
  • 你知道嗎？ 高效版本的 氣泡排序 如果在整輪掃描中沒有進行任何交換，可以提早結束——這代表列表已經排序完成了！

合併排序 (Merge Sort)

這是一個較複雜的演算法。它會將列表拆分成極小的片段（單個項目），然後再按正確順序將它們合併起來。

  • 時間效率： 處理大量數據時，速度比氣泡排序快得多。
  • 記憶體效率： 較氣泡排序低，因為它在處理過程中需要額外的記憶體來存放那些被「拆開」的片段。

逐步比較

要決定使用哪種排序法，請參考以下因素：

  1. 有多少數據？ 如果是巨量列表，合併排序在速度上完勝。
  2. 你有多少記憶體？ 如果記憶體空間非常有限（例如在微型晶片上），氣泡排序可能較為合適。
  3. 列表是否已經部分排序？ 如果列表幾乎已經排好，氣泡排序會相當快；而合併排序則無論資料狀態如何，所需時間大致相同。
記憶小撇步：排序總結

「Bubble 是 Basic（基本且慢），Merge 是 Mighty（強大且快）！」

重點總結： 氣泡排序容易撰寫但速度慢。合併排序適合處理大數據但會佔用較多記憶體。

4. 複習總結表

使用下表快速比較我們所介紹的演算法：

演算法 類型 主要優點 主要缺點
線性搜尋 搜尋 適用於未排序的數據。 在大型列表中速度緩慢。
二元搜尋 搜尋 速度極快。 數據必須先排序。
氣泡排序 排序 佔用極少記憶體。 在大型列表中非常緩慢。
合併排序 排序 處理大型列表速度極快。 使用較多記憶體。

最終小貼士： 當考試要求你比較演算法時，請務必提到時間效率（速度）以及數據的初始狀態（是否已排序？是否為大型列表？）。