Efficiency of algorithms

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

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

在本節中，我們將學習如何衡量一個算法是否比另一個「更好」，並專注於兩個核心概念：時間和記憶體的使用。

1. 什麼是算法效率？

當我們談論算法的效率 (Efficiency of an Algorithm) 時，我們是在描述算法使用資源來解決問題的能力。我們最關心的主要資源是時間和記憶體。

一個高效的算法，是指能用最少的運算時間及/或最少的記憶體空間，達到預期結果的算法。

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

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

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

重點總結： 效率的核心在於將時間 (Time) 和空間 (Space/Memory) 的使用量降至最低。

2. 衡量效率的兩個維度（時間與空間）

在評估算法時，我們根據兩個主要標準來衡量其效能：

A. 時間複雜度 (Time Complexity)（需要多久？）

時間複雜度衡量的是算法完成任務所需的時間。關鍵在於，我們通常不會用「秒」來衡量，因為執行時間會隨電腦運算速度（硬體）的不同而改變。

相反，我們通過計算算法相對於輸入數據量所執行的基本運算或步驟 (steps) 數量來衡量時間複雜度。

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

為什麼我們使用「步驟」而不是「秒」：

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

B. 空間複雜度 (Space Complexity)（需要多少記憶體？）

空間複雜度衡量的是算法運行並完成任務所需的暫存記憶體（RAM/儲存空間）。

當算法運行時，它通常需要建立暫存變數、列表或數據副本，這會佔用記憶體。

類比： 想像為遠足（算法）打包背包（記憶體）。

• 簡單的路線只需要地圖和水瓶（空間複雜度低）。
• 複雜的多日旅程則需要大量的額外補給、存放裝備的空間和額外的食物（空間複雜度高）。

一個高效的算法會嘗試將其所需的額外儲存空間降至最低。

C. 時間與空間的取捨 (Trade-off)

在許多情況下，時間效率和空間效率之間存在著取捨 (Trade-off)：

• 有時，如果你允許算法使用更多的記憶體（空間複雜度變差），你可以讓它運行得快得多（時間複雜度變好）。
• 相反，你可能設計出一個幾乎不需要額外記憶體的算法，但它可能需要很長時間才能完成任務。

程式設計師必須根據所解決的特定任務，決定哪種資源更為重要。

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

即使兩個算法解決同一個問題，它們的效率也可能因多種因素而大相徑庭。理解這些因素有助於我們預測效能。

A. 輸入數據的大小 (Input Size)

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

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

例子： 在電話簿（輸入）中尋找特定姓名（數據）。

• 在 10 頁的簿子裡找名字非常容易且快速（輸入大小小）。
• 在包含數百萬個名字的龐大資料庫中找同樣的名字則需耗費更長時間（輸入大小大）。

一個好的算法不僅在輸入較小時運行快速，即使在輸入大小變得極大時，也能妥善管理其執行步驟。

B. 算法設計的品質

不同的方法會導致不同的效率。考慮兩種簡單的搜尋方法：

1. 順序搜尋 (Sequential Search)（效率低）： 逐個檢查每一項。如果列表有 N 個項目，在最壞的情況下，你可能需要 N 個步驟。

2. 二分搜尋 (Binary Search)（效率高）： 這只有在列表已排序時才有效，但它讓你能夠重複將列表減半。在 100 個項目的列表中找到一個項目可能只需要 7 或 8 個步驟。

在可能的情況下，選擇二分搜尋而不是順序搜尋，是瞬間顯著提升效率的捷徑，因為其底層設計更優越。

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

雖然我們傾向於基於步驟來衡量效率（以忽略硬體影響），但在現實環境中，實際耗時（以秒為單位）會受到以下影響：

• 處理器速度 (CPU)： 更快的電腦能更快執行每個步驟。
• 記憶體可用性 (RAM)： 如果電腦沒有足夠的 RAM，運行速度會大幅下降。
• 程式語言： 一些語言（如 C++）會被編譯成非常快速的機器碼，而其他語言（如 Python）運行時通常稍慢，這會影響絕對速度。
• 編譯器/直譯器效率： 負責翻譯你程式碼的軟體有時能進行優化，使其運行得更快。

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

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

A. 處理大量數據

現代應用程式需要處理海量資料集——數百萬甚至數十億條資訊（想想 Google 搜尋、Netflix 推薦系統或銀行交易）。

如果一個低效的算法對 1,000 個項目排序需要 1 秒，那麼對 100,000 個項目排序可能需要 1,000 秒（超過 16 分鐘）。這種等待時間在產業界是無法接受的。

B. 資源管理與成本

• 節省電力： 更高效的算法需要較少的運算能力，因此耗電量更少。這對行動裝置（電池壽命）和大型數據中心（成本與環境影響）至關重要。
• 更好的用戶體驗： 用戶期望得到即時結果。如果網頁搜尋需要 10 秒，用戶就會離開。高效率能確保快速的載入時間和反應速度。

你知道嗎？ 像 Amazon 和 Google 這樣的公司，僅僅通過對其算法進行微小的優化就能節省數百萬美元，因為這些微小的改進在他們龐大的基礎架構中每天被重複數十億次！

5. 關鍵概念回顧

我們使用兩個主要標準來衡量效率：

時間複雜度 (T)

衡量算法執行的步驟數量如何隨著輸入大小的增加而增長。

空間複雜度 (S)

衡量算法在執行過程中所需的額外記憶體量。

影響效能的最大因素是輸入大小。

最後的鼓勵： 理解效率能幫助你像真正的計算機科學家一樣思考。你不僅是在解決問題，更是在以最優質的方式解決問題！