高效算法：聰明地工作，而非努力地工作

歡迎！這一章非常重要，因為它讓我們從「寫出能運作的程式」，進階到「寫出優質的程式」。你可以這樣想：任何人都能開車從倫敦到曼徹斯特，但一位高效的司機知道最快的路線，能避開交通擠塞，並節省時間。

在本節中，我們將學習在解決同一個問題時，如何衡量一個算法是否比另一個「更好」或更有效率。


1. 什麼是算法效率？

當我們談論算法的效率 (Efficiency of an Algorithm) 時，我們是在描述算法使用運算步驟來解決問題的有效程度。

一個高效的算法，是指能用盡可能最少的步驟或運算，達到預期結果的算法。

類比： 想像你需要在一座巨大的圖書館中找到特定的一本書。

  • 低效率的方法： 從第一個書架開始，檢查每一本書，直到找到為止。
  • 高效的方法： 查看圖書館目錄，找到準確的區域和書架編號，然後直接前往。

高效的方法使用的步驟更少，節省了大量時間！

重點總結： 在考試中，算法效率側重於時間效率 (Time Efficiency)（將執行步驟的數量降至最低）。


2. 衡量時間效率

時間效率衡量的是算法的執行時間如何隨著輸入數據量的增加而增長。

關鍵在於，我們不會用秒來衡量時間效率，因為所花費的時鐘時間會隨電腦硬體速度（CPU）的不同而改變。

相反，我們通過計算算法相對於輸入數據量所執行的基本運算或步驟 (steps) 數量（例如比較、計算或賦值）來衡量時間效率。

例子：如果一個算法需要比較兩個數字 100 次才能將一個小列表排序，那麼它執行了 100 個步驟。如果列表大小增加了 10 倍，它可能需要 1,000 個步驟。

為什麼我們計算「步驟」而不是「秒」：

  • 如果算法 A 在超級電腦上運行需 5 秒，而算法 B 在基礎的學校手提電腦上運行需 10 秒，這樣的比較並不公平。
  • 通過計算步驟（比較、加法、賦值），我們得到了一種與硬體無關的度量標準。我們僅僅是在評估算法本身的品質與邏輯。

3. 影響算法效率的關鍵因素

可以使用多於一個算法來解決完全相同的問題，但它們的效率可能大相徑庭。

A. 輸入數據的大小 (The Size of the Input Data)

這通常是決定效率最重要的因素。

定義： 輸入大小 (Input Size) 是指算法必須處理的數據量（例如：列表中的項目數量、資料庫中的記錄數量）。

例子： 在聯絡人清單中尋找特定姓名。

  • 在包含 10 個項目的列表中找名字非常快速，且只需要極少步驟（輸入大小小）。
  • 在包含數百萬個項目的資料庫中找名字則需要多得多的步驟（輸入大小大）。

一個好的算法即使在輸入大小變得極大時，也能妥善管理其步驟。

B. 算法設計的品質

不同的算法方法會導致不同數量的步驟。考慮在列表中尋找項目的兩種搜尋方法：

1. 線性（順序）搜尋 (Linear (Sequential) Search)： 逐個檢查每一項。如果列表有 \(N\) 個項目，在最壞的情況下，它需要 \(N\) 個比較步驟。

2. 二分搜尋 (Binary Search)： 這需要列表已排序，但它在每次比較時都會將剩餘項目減半。在 100 個項目的列表中找到一個項目最多只需 7 個步驟。

對於已排序的列表，選擇二分搜尋而不是線性搜尋，是瞬間顯著提升效率的捷徑，因為其算法設計需要的運算少得多。

C. 外部因素（硬體與軟體）

雖然我們嚴格通過計算步驟來衡量算法效率，但在現實環境的執行中，實際耗時（以秒為單位）也會受到以下影響：

  • 處理器速度 (CPU)： 更快的電腦能更快執行每個步驟。
  • 記憶體可用性 (RAM)： RAM 不足可能會在執行期間導致延遲。
  • 程式語言： 編譯型語言執行機器碼的速度通常比直譯型語言更快。

💡 避免常見錯誤

不要將電腦的速度與算法的效率混為一談！無論是在超級電腦還是基礎筆電上運行，高效的算法執行的步驟永遠比低效算法少。


4. 為什麼選擇高效算法很重要？

你可能會問：「我的程式碼能瞬間完成 10 個數字的排序，為什麼還要費心去優化它？」答案是規模！

A. 處理大量數據

現代應用程式需要處理海量數據集——數百萬甚至數十億條資訊（例如搜尋引擎、社交媒體動態或銀行系統）。

如果一個低效的算法處理 1,000 個項目需要 1 秒，那麼處理 100,000 個項目可能需要 1,000 秒（超過 16 分鐘）。選擇更高效的算法能保持處理過程快速且實用。

B. 資源管理與反應速度
  • 節省能源： 執行較少指令的算法消耗較少的處理器功耗和電力，從而延長行動裝置的電池壽命並減少數據中心的能源消耗。
  • 更好的用戶體驗： 用戶期望得到反應靈敏的程式。高算法效率能確保快速的反應時間，並防止應用程式凍結。

5. 關鍵概念速覽

  • 多於一個算法可以解決同一個問題。
  • 時間效率是通過比較執行步驟/運算的數量來評估的，而不是以秒為單位的原始時鐘時間。
  • 所需步驟的數量在很大程度上由輸入大小和算法設計決定（例如：二分搜尋與線性搜尋）。