(clrs)：introduction To Algorithms@2009 (第3版)

本文字旨在介紹電腦演算法的核心概念、重要性以及本書《演算法概論》第三版涵蓋的主要內容與架構。演算法是計算科學的基礎，它是一組明確的計算步驟，旨在將輸入轉換為輸出，用以解決特定的計算問題。排序問題是演算法研究中的經典範例，例如將一串數字按非遞減順序排列。

研究演算法的價值不僅僅在於找到一個能解決問題的方法，更重要的是找到一個有效率的方法。即便電腦硬體速度不斷提升、記憶體成本持續下降，計算時間與空間資源依然是有限的。不同的演算法在處理相同問題時，其效率差異可能遠大於硬體速度或軟體優化的差異。例如，針對排序問題，插入排序在最壞情況下需要 ‚(n²) 的時間，而合併排序只需要 ‚(n lg n) 的時間，其中 n 是輸入規模。對於大型輸入，例如排序千萬個數字，合併排序即使在較慢的電腦上，其執行時間也可能比在快得多的電腦上執行插入排序快上許多倍。這凸顯了選擇高效演算法的重要性。因此，演算法應被視為與硬體、圖形使用者介面、物件導向系統、網路等並列的技術。許多應用程式的核心功能，如路徑規劃、資料檢索、資料壓縮、資源分配、密碼學等，都嚴重依賴於精巧的演算法。

本書涵蓋了演算法設計與分析的各種重要技術。其中一些核心設計範式包括：
1. 分治法 (Divide-and-Conquer)：將問題分解為若干與原問題類似但規模較小的子問題，遞歸地解決這些子問題，然後將子問題的解合併以得到原問題的解。合併排序就是一個典型的分治演算法。
2. 動態規劃 (Dynamic Programming)：應用於最佳化問題，當問題的子問題重疊時特別有效。動態規劃透過解決每個子問題一次並儲存其解，避免重複計算，從而將指數級時間的樸素解法轉換為多項式時間演算法。
3. 貪婪演算法 (Greedy Algorithms)：也常用於最佳化問題，每一步都選擇當前看起來最好的局部最佳解，希望藉此達到全域最佳解。貪婪演算法通常比動態規劃更簡單快速，但並非所有問題都適用。

同時，分析演算法的技術也至關重要，以便評估演算法的效率和資源需求。重要的分析技術包括：
1. 執行時間分析 (Running Time Analysis)：衡量演算法執行所需的時間，通常表達為輸入規模的函數。
2. 漸進式分析 (Asymptotic Analysis)：使用漸進符號（如 O, ‚, , o, !）來描述演算法執行時間的成長率，忽略常數因子和低階項，專注於演算法在處理大型輸入時的行為。
3. 遞歸式分析 (Recurrence Analysis)：用於描述遞歸演算法的執行時間，透過遞歸關係式來表達問題規模與子問題規模之間的關係，並使用特定的方法（如代換法、遞歸樹法、主定理）來求解。
4. 機率分析 (Probabilistic Analysis) 和 隨機演算法 (Randomized Algorithms)：當演算法的行為取決於輸入分布或演算法自身的隨機選擇時，使用機率論來分析演算法的平均效能或預期效能。
5. 攤銷分析 (Amortized Analysis)：分析一系列演算法操作的平均成本，即使個別操作可能耗時較長，攤銷分析能證明在一個操作序列中，平均而言每個操作的成本較低。

除了演算法設計和分析技術，本書還深入探討了各種資料結構 (Data Structures)，這些結構用於組織和儲存數據，以便有效地存取和修改。不同的資料結構適用於不同的用途，了解它們的優勢和限制至關重要。基礎資料結構如陣列、鏈結串列、堆疊、佇列和雜湊表是後續許多複雜演算法和資料結構的基礎。進階資料結構如二元搜尋樹、紅黑樹、B 樹、費氏堆積、van Emde Boas 樹和不相交集資料結構等，則提供了處理更複雜問題或在特定情境下實現更高效率的方法。例如，紅黑樹保證了對數時間的搜尋、插入和刪除操作；B 樹專為磁碟儲存設計，能有效減少磁碟存取次數；而費氏堆積和 van Emde Boas 樹在理論上提供了更快的特定操作的攤銷或最壞情況時間界限。

本書也涵蓋了圖形演算法，這是演算法領域一個非常重要的分支。許多實際問題可以建模為圖論問題，例如尋找兩點之間的最短路徑、確定網路中的最大流量、或構建連接所有頂點的最小成本網路。圖形演算法涉及圖的表示、圖的搜尋（廣度優先搜尋和深度優先搜尋）、拓撲排序、強連通分量、最小生成樹、單源最短路徑和所有對最短路徑等。

最後，本書還探討了計算的局限性，特別是 NP 完全問題。對於這類問題，目前沒有已知多項式時間的解決方案，它們被認為是難解的。了解問題的 NP 完全性可以幫助我們避免徒勞地尋找精確的多項式時間演算法，轉而尋求近似演算法 (Approximation Algorithms)，這類演算法能夠在多項式時間內找到接近最優解的方案，這在許多實際應用中已經足夠好。

總之，本書提供了一個關於電腦演算法的全面介紹，從基礎概念到進階技術和資料結構，並探討了計算的極限。本書採用清晰的偽碼描述演算法，並提供嚴謹的數學分析，旨在讓讀者深入理解演算法的設計原理和效能特性。第三版在內容和表達上進行了多方面的更新和改進，並增加了新的主題，以期更貼近當代計算科學的發展和應用需求。