Steven Skiena：the Algorithm Design Manual@2008 (第2版)

本文件概述了《演算法設計手冊》的序言以及前九章的主要論點與概念。這本手冊旨在幫助程式設計師設計正確、高效且可實作的演算法，以解決實際世界中的問題。本書強調了演算法設計所需的核心知識：演算法設計技術（如資料結構、動態規劃、搜尋和啟發法）和資源（已知問題、實作和文獻）。手冊特別強調了「問題目錄」、「戰爭故事」和「電子資源（網站）」。

一、演算法的基礎 (Introduction to Algorithm Design)

• 演算法與問題的定義： 演算法是用於完成特定任務的程序。一個演算法問題由其必須處理的輸入實例集合和在這些實例上運行後所需的輸出屬性來定義。一個演算法則是能將任何可能的輸入實例轉換為所需輸出的程序。排序問題就是一個典型的例子，輸入是一個鍵序列，輸出是該序列的有序排列。
• 正確性、效率與實作難度： 一個好的演算法應該是正確的、高效的且易於實作。然而，這些目標可能無法同時達成。在工業界，只要程式能提供足夠好的答案且不拖慢應用程式的速度，即使存在更好的演算法，也往往是可以接受的。
• 啟發法與正確性： 啟發法是一種依據經驗法則或直覺來尋找解決方案的方法，通常速度較快，但不保證總是能找到最佳或正確的解。書中以「機器人巡遊最佳化」問題的最近鄰居啟發法和最近對啟發法為例，展示了看似合理的啟發法在特定輸入實例上如何產生非常差的結果，證明了「這很明顯」絕不足以作為正確性的證明。演算法的正確性必須被小心地論證，通常需要證明。
• 表達演算法的方式： 演算法可以透過英文描述、偽代碼或實際程式語言來表達。英文最自然但最不精確，程式語言最精確但較難表達。偽代碼提供了兩者之間的平衡，但應以清晰地揭示演算法核心思想為目標。
• 問題和屬性： 證明演算法的正確性需要清晰精確的問題定義，包括允許的輸入實例集合和所需的輸出屬性。模糊的問題定義或複合的目標會使證明變得困難或不可能。一個重要的演算法設計技術是縮小允許的實例範圍，直到找到正確且高效的演算法。
• 證明不正確性： 證明一個演算法不正確的最佳方法是提供一個反例——一個演算法產生錯誤結果的實例。好的反例應具備可驗證性（能計算演算法的輸出並展示更好的解）和簡潔性（只保留必要細節）。尋找反例的技巧包括思考小規模實例、窮盡可能性、針對啟發法的弱點、考慮平手以及尋找極端實例。
• 歸納法與遞歸： 數學歸納法是證明遞歸或增量演算法正確性的常用方法。這與遞歸程式設計的概念密切相關，兩者都涉及基本情況和遞歸步驟。然而，歸納證明可能潛藏細微的錯誤，尤其是在處理邊界情況或當插入一個新項可能導致整個最優解發生大規模變化時。
• 建模問題： 將現實世界的應用問題抽象化，以精確描述、已被良好理解的標準問題來表達，這是應用演算法設計技術的關鍵。常見的抽象結構包括：排列、子集、樹、圖、點、多邊形、字串。學習以這些結構來描述問題，能幫助我們找到現有的演算法或解決方案。戰爭故事「通靈建模」強調了在解決問題之前，確保問題建模正確的重要性。
• 遞歸對象： 學習遞歸思考是理解大事物是由更小但相同類型的事物構成的。排列、子集、樹、圖、點集、多邊形和字串都可以視為遞歸對象，這種分解思想是許多演算法的基礎。

二、演算法分析 (Algorithm Analysis)

• RAM 計算模型： 演算法分析通常在隨機存取機器（RAM）模型下進行，假設每個簡單操作（加、乘、比較等）和記憶體存取都耗時一個單位時間。這是一個簡化的模型，忽略了現實世界中操作和記憶體訪問的複雜差異，但它足以捕捉演算法的本質行為，實現與具體機器無關的分析。
• 最好、最壞與平均情況複雜度： 演算法的運行時間會因輸入實例的不同而異。最好情況複雜度是給定輸入大小下的最快運行時間，最壞情況複雜度是最慢運行時間，平均情況複雜度是所有實例運行時間的平均。最壞情況複雜度在實踐中最為有用，因為它提供了性能的上界保證。
• 大 O 符號： 為了簡化複雜的運行時間函數，我們使用大 O 符號（Big Oh Notation）。
  • O(g(n)) 表示 f(n) 的漸近上界（f(n) ≤ c ⋅ g(n) 對足夠大的 n 成立）。
  • Ω(g(n)) 表示 f(n) 的漸近下界（f(n) ≥ c ⋅ g(n) 對足夠大的 n 成立）。
  • Θ(g(n)) 表示 f(n) 的漸近緊界（f(n) 同時滿足 O 和 Ω）。
    大 O 符號忽略了常數因子和低階項，讓我們能專注於函數的增長率。這對於比較不同漸近複雜度的演算法至關重要，因為漸近行為決定了演算法在大規模問題上的可行性（例如，O(n log n) 遠優於 O(n²)）。
• 增長率與支配關係： 演算法分析中常見的增長率按支配關係排序大致為：常數 < 對數 < 線性 < 超線性 (n log n) < 平方 < 立方 < 指數 < 階乘。支配關係是指增長更快的函數最終會超越增長較慢的函數。對數（log n）增長非常慢，通常出現在重複二分問題大小的演算法中（如二分查找）。
• 大 O 符號的運算： 函數相加時，結果由支配項決定；函數相乘時，結果是兩個函數的積。
• 分析效率： 透過檢查演算法的巢狀循環結構，可以粗略估計其運行時間。最壞情況運行時間通常由最深層巢狀循環的迭代次數的乘積決定。對於更複雜的結構，可以使用求和公式來精確計算操作次數。戰爭故事「金字塔之謎」生動地展示了演算法改進帶來的性能提升遠超硬體速度提升，以及細緻分析的重要性。

三、資料結構 (Data Structures)

• 資料結構的重要性： 選擇合適的資料結構可以極大地提高程式性能，甚至能將低效演算法轉變為高效演算法。就像器官移植，更換一個關鍵組件就能解決問題。
• 連續分配與連結結構： 資料結構可以基於陣列進行連續分配（如陣列、雜湊表）或基於指標進行連結（如連結串列、樹、圖的鄰接表）。
  • 陣列： 優點包括常數時間隨機存取（如果知道索引）、空間效率高和記憶體局部性好。缺點是大小固定。動態陣列通過在空間不足時倍增大小，實現了均攤意義上的常數時間插入。
  • 連結串列： 優點包括大小彈性、插入刪除相對簡單（如果不需要保持順序）、移動大記錄時只需移動指標。缺點是需要額外空間存儲指標、隨機存取效率低、記憶體局部性差。
  • 遞歸結構： 連結串列和陣列都可以被視為遞歸對象，這啟發了許多遞歸演算法的設計。
• 堆疊與佇列： 這兩種是基於插入順序進行存取的基本容器。堆疊是後進先出（LIFO），佇列是先進先出（FIFO）。它們可以使用陣列或連結串列實現。
• 字典： 字典抽象資料類型允許根據鍵值存取資料。基本操作包括搜尋、插入、刪除。一些字典還支持尋找最小值/最大值、前驅/後繼等操作。不同的資料結構實現字典操作的效率不同（如排序陣列在搜尋上優於未排序陣列，但在插入刪除上則反之）。選擇字典實現需要平衡所有所需操作的性能。
• 二元搜尋樹： 結合了排序和連結的思想，通過樹結構實現對數時間的搜尋、插入和刪除（在樹平衡的情況下）。每個節點的左子樹鍵小於節點鍵，右子樹鍵大於節點鍵。雖然插入順序可能導致樹不平衡（最壞情況下高度為線性），但隨機插入的樹平均高度是對數的。自平衡二元搜尋樹（如紅黑樹、伸展樹）保證樹的高度始終為對數，使得所有字典操作在最壞情況下都是對數時間。
• 優先佇列： 優先佇列根據鍵值存取資料，支持插入、尋找最小/最大元素、刪除最小/最大元素。常見實現包括二元堆積（通常使用陣列實現）或自平衡二元搜尋樹。優先佇列在許多演算法中扮演關鍵角色，如 Prim 演算法和事件模擬。戰爭故事「剖分三角形網格」強調了優先佇列在改進幾何演算法性能中的作用。
• 雜湊表與字串： 雜湊表提供了一種非常實用的字典實現方式，利用雜湊函數將鍵映射到陣列索引，實現均攤常數時間的插入、刪除和搜尋。解決衝突的方法有鏈式法和開放定址法。雜湊表不僅用於字典，還可用於高效的字串匹配（Rabin-Karp 演算法）和重複偵測。戰爭故事「串起來」展示了為了解決生物序列處理中的性能瓶頸，從二元搜尋樹到雜湊表再到後綴樹的資料結構演變過程。
• 專門資料結構： 除了基本類型外，還有許多專門資料結構用於處理特定類型的對象，如字串資料結構（後綴樹/陣列）、幾何資料結構（kd 樹、R 樹）、圖資料結構（鄰接矩陣、鄰接表）、集合資料結構（位元向量、並查集）。

四、排序與搜尋 (Sorting and Searching)

• 排序的應用： 排序是許多其他演算法的基礎構件。將資料排序後，許多問題變得更容易解決，例如搜尋、尋找最接近對、元素唯一性、頻率分佈、選擇（找到第 k 小元素）和構建凸包。
• 排序的實用考量： 選擇排序演算法時需要考慮數據量、是否存在重複鍵（穩定性）、數據的特性（分佈、鍵長度）以及是否需要外部排序。通常應優先使用標準庫提供的排序函數，並透過比較函數來指定排序準則。
• 堆積排序： 堆積排序是利用優先佇列資料結構實現的選擇排序。通過使用（二元）堆積來高效地尋找和刪除最小元素，將選擇排序從 O(n²) 提升到 O(n log n)。二元堆積是一種高效實現優先佇列的資料結構。堆積可以在 O(n) 時間內構建（通過從下往上冒泡），但插入和刪除元素則需要 O(log n)。
• 歸併排序： 歸併排序是分治法的經典應用。它將陣列分成兩半，遞歸排序，然後在線性時間內將兩個排序好的子陣列合併。這導致 O(n log n) 的運行時間。歸併排序特別適用於連結串列。
• 快速排序： 快速排序也是分治法，通過隨機選擇一個樞軸元素將陣列分割為小於樞軸和不小於樞軸的兩部分。樞軸元素被放置在最終 sorted 位置。遞歸地排序兩部分。雖然最壞情況下（樞軸選擇最差）是 O(n²)，但隨機化樞軸選擇使得平均期望時間為 O(n log n)，在實踐中通常非常快，因為其內層循環操作簡單。隨機化演算法利用隨機性來保證良好的平均性能，使其對任何輸入都表現良好。
• 分佈排序： 分佈排序或桶排序利用將元素分配到桶中，然後分別排序每個桶的思想。這在資料分佈均勻時表現良好，但對於不均勻分佈則可能性能很差。
• 排序的下界： 在比較模型下，任何排序演算法的最壞情況運行時間都不能快於 Ω(n log n)。
• 二元搜尋及其相關演算法： 二元搜尋在排序陣列中尋找鍵，每次比較都能將搜尋範圍減半，實現 O(log n) 的搜尋時間。它是分治法的典型應用，也是很多變體搜尋演算法的基礎，如計數 occurrences、單邊二元搜尋等。
• 分治法： 分治法是將大問題分解為更小的同類型子問題，遞歸求解，然後將子問題的解合併以得到原問題的解。這種技術的效率通常用遞歸關係來分析，許多形式的遞歸關係可以使用主定理來解決。

五、圖遍歷與加權圖演算法 (Graph Traversal and Weighted Graph Algorithms)

• 圖的定義與種類： 圖由頂點集和邊集構成，是建模關係的強大工具。圖有多種「種類」，如無向/有向、加權/無權、簡單/非簡單、稀疏/稠密、循環/非循環、嵌入/拓撲、隱式/顯式、標籤/無標籤。理解這些特性有助於選擇合適的資料結構和演算法。朋友關係圖是稀疏、無向、加權、嵌入、隱式和有標籤圖的典型例子。
• 圖的資料結構： 圖的常見表示方法是鄰接矩陣和鄰接表。鄰接矩陣在測試兩點間是否存在邊時很快捷，但在表示稀疏圖時空間效率低。鄰接表更適合表示稀疏圖，儘管測試邊的存在需要遍歷。對於大多數實際應用，鄰接表是更好的選擇。
• 圖的遍歷： 遍歷圖是系統地訪問圖中所有邊和頂點的過程，是許多基本圖演算法的基礎。遍歷過程中，頂點通常經歷未發現、已發現、已處理三個狀態。
  • 廣度優先搜尋 (BFS)： 使用佇列來探索頂點，以距離起始點越來越遠的順序訪問。BFS 找到的是無權圖中的最短路徑，可用於尋找連通分量、判斷二分圖。
  • 深度優先搜尋 (DFS)： 使用堆疊（或遞歸）來探索頂點，沿著一條路徑深入，直到無法再深入才回溯。DFS 對邊進行分類（樹邊、後向邊、前向邊、交叉邊），記錄頂點的進入和退出時間，這些屬性在許多演算法中至關重要，如尋找循環、關節點、橋，以及有向圖中的拓撲排序和強連通分量。戰爭故事「摩爾定律的受害者」和「獲得圖形」強調了在處理大規模圖時選擇正確的圖資料結構的重要性。
• 加權圖演算法： 邊帶有權重的圖問題需要更複雜的演算法。
  • 最小生成樹 (MST)： 尋找連通所有頂點的邊集權重最小的樹。Prim 演算法和 Kruskal 演算法是兩種經典的貪心演算法，都可以在 O(m log m) 或 O(n²) 或 O(m + n log n) 時間內找到 MST，取決於資料結構的實現。並查集是 Kruskal 演算法中用於高效管理連通分量的重要資料結構。MST 在網絡設計和聚類中常見。
  • 最短路徑： 尋找兩點間權重最小的路徑。Dijkstra 演算法使用類似 Prim 演算法的貪心策略，找到從單一起始點到所有其他頂點的最短路徑，適用於非負權重圖。Floyd-Warshall 演算法使用動態規劃解決所有頂點對之間的最短路徑問題，適用於非負循環圖和帶負權重的圖（但不含負循環）。戰爭故事「撥號尋文」展示了將模式識別問題建模為最短路徑問題的應用。
  • 網絡流： 在有向圖中，邊帶有容量限制，網絡流問題尋找從源點到匯點的最大流量。最大流量等於最小割（分割源點與匯點所需的最小邊容量）。網絡流可以解決多種圖問題，最著名的是二分圖匹配問題。戰爭故事「只有它不是無線電」展示了網絡流在電話代碼重建中的應用。

六、難解問題與近似演算法 (Intractable Problems and Approximation Algorithms)

• 難解問題的定義： 並非所有問題都有已知的高效（多項式時間）演算法。難解問題是那些可能沒有多項式時間演算法的問題。證明一個問題是難解的，通常是通過歸約，展示如果該問題可以被高效解決，那麼一個已知難解的問題也可以被高效解決，從而導致矛盾。
• 歸約： 歸約是一種將問題 A 的實例轉換為問題 B 的實例的方法，使得問題 A 的解可以通過問題 B 的解得到。如果轉換本身是高效的（多項式時間），那麼高效解決 B 就意味著高效解決 A。反過來，如果 A 是已知難解的，那麼 B 也必然是難解的。
• 決策問題： 為了簡化歸約，通常將問題轉換為只能回答「是」或「否」的決策問題（例如，TSP 決策問題：是否存在權重 ≤ k 的巡遊？）。許多優化問題都可以這樣轉換。
• NP-完全性理論： NP-完全性是計算複雜性中最基本的概念之一。
  • P 類： 可以在多項式時間內解決的決策問題類。
  • NP 類： 解可以在多項式時間內驗證的決策問題類。所有 P 類問題都在 NP 類中。
  • NP-難： 至少與任何 NP 類問題一樣難的問題。
  • NP-完全： 既是 NP-難，又在 NP 類中的問題。
    並行計算可以幫助解決許多圖論問題，但並非所有問題都能有效並行化。有些問題被證明是 P-完全的，難以有效並行。
• 難度證明： 3-Satisfiability (3-SAT) 是公認的 NP-完全問題的「母」問題。許多其他 NP-完全問題都可以通過一系列歸約鏈證明其難度，例如 3-SAT 歸約到頂點覆蓋，頂點覆蓋歸約到獨立集和團。證明問題難度是一種技巧，通常從一個已知的 NP-完全問題開始，通過構造性歸約將其轉化為目標問題。戰爭故事「在時鐘前硬拼」和「然後我失敗了」分享了證明問題難度的經驗。
• 應對 NP-完全問題： 證明一個問題是 NP-完全的並不意味著無法解決它。而是需要採取不同的策略：
  • 平均情況下高效的演算法： 如帶有剪枝的回溯法。
  • 啟發法： 尋找好的但非最佳解，如模擬退火、貪心法。
  • 近似演算法： 尋找帶有性能保證的解，即保證解的品質與最佳解在一個可控的因子（近似比）內。一些問題有很好的近似演算法（如頂點覆蓋、歐幾里得 TSP、最大無環子圖、集合覆蓋），但也有一些問題難以近似（如團、集合覆蓋）。戰爭故事「斯基納的防禦」和「退火陣列」展示了啟發法和近似演算法在實際問題中的應用。

這些概念構成了本書的基礎，指導讀者理解演算法的本質、分析其效率、選擇合適的工具（資料結構和演算法範式）以及應對計算上困難的問題。