演算法設計手冊

引用

Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.

章節概要

全書分兩部分，共22章，後接參考文獻和索引；正文頁碼排到約第718頁，全書共793頁。第一部分「實用演算法設計」（第1–13章）講授設計和分析演算法的方法。第二部分「演算法漫遊指南」（第14–22章），出版社稱之為供翻閱的目錄，收錄實務中經常出現的75個問題，並附有實作和文獻的線索。Skiena 本人的網頁把本書描述為重設計而非重分析。

第1–2章：演算法設計導論；演算法分析

開頭兩章分別介紹演算法設計（第1章）和演算法分析（第2章），後者約四十頁。出版社把本書的風格描述為「不堆砌定理與證明」（no theorem-proof），即直觀而非形式化的口吻，分析也是用這種口吻來講的。

第3–4章：資料結構；排序

資料結構和排序在第一部分裡各有專門的章節，所以本書並不是簡單地假定讀者已經掌握它們；不過，目錄沒有顯示這兩章對先修知識的預期有多高。

第5–6章：分治法；雜湊與隨機演算法

兩章講技巧。出版社列出本版在分治法、雜湊和隨機演算法方面的新增或擴充內容，與這些章節的主題相符。

第7–8章：圖的遍歷；加權圖演算法

兩章合計約八十五頁，從遍歷講到加權問題。圖在第二部分裡再次出現，分別在多項式時間問題和NP難問題兩章中，因此正文頁碼中大約四分之一與圖有關。

第9–10章：組合搜尋；動態規劃

第9章講組合搜尋；第10章講動態規劃，約四十七頁，是第一部分最長的一章。

第11–13章：NP完全性；應對困難問題；如何設計演算法

第一部分以一組關於難解性的章節收尾：先講NP完全性意味著什麼，再講遇到這類困難問題時的對策。出版社把近似演算法列為新增或擴充的內容之一，但沒有說明由哪一章承載。這一部分的最後一章題為「如何設計演算法」，只有六頁。

第14章：演算法問題目錄

通向第二部分的兩頁入口；第二部分以「漫遊指南」的形式從第435頁開始。出版社稱，這份目錄會為每個問題把讀者引向解決問題的正確道路。

第15–19章：資料結構；數值問題；組合問題；圖問題（多項式時間）；圖問題（NP難）

按問題種類組織的目錄條目。第15章回到資料結構，只是現在放在目錄之中；第18章和第19章把圖問題分成多項式時間可解的和NP難的兩類。

第20–22章：計算幾何；集合與字串問題；演算法資源

目錄以幾何問題（目錄各章中最長，約五十六頁）、集合與字串問題，以及很短的最後一章「演算法資源」結束。出版社稱本書提供指向 C、C++ 和 Java 實作的連結。

核心概念

第一部分：實用演算法設計（第1–13章）

• 演算法分析：判斷設計的效率，被當作實用工具來對待。
• 分治、雜湊、隨機化：各有專章的設計技巧。
• 圖的遍歷與加權圖：圖這部分的核心。
• 動態規劃與組合搜尋：處理最佳化問題和窮舉類問題的方法。
• NP完全性：用來識別那些很可能沒有高效精確演算法的問題的術語。

第二部分：演算法漫遊指南（第14–22章）

• 問題目錄：按問題類別組織條目，讀者可以由問題而不是由演算法入手查詢。
• 問題類別：資料結構、數值、組合、圖（多項式時間與NP難）、幾何、集合與字串，目錄各章即按此劃分。

評析

優點

• 圍繞「識別問題」來組織。 目錄部分讓讀者可以從問題的形態出發，這與多數演算法教材逐個技巧推進的順序不同。Skiena 的網站上還列有演算法資源庫（Algorithm Repository）和程式。
• 易於讀懂。 出版社強調「不堆砌定理與證明」的風格、突出顯示的「帶走的教訓」（take-home lessons），以及來自實際應用的「戰爭故事」（war stories）。
• 練習材料豐富。 習題中有求職面試題，新版增加了一百多道題，其中包括來自 LeetCode 和 HackerRank 的題目。作者的網站連結了題解維基、講義和講課影片。
• 正面應對困難問題。 NP完全性、應對困難問題的策略，以及單獨一章NP難圖問題，讓學生看到在預期沒有高效演算法時該怎麼辦。

侷限

• 有意把證明壓到最少。 想認真跟蹤正確性和執行時間證明的讀者，需要配一本更形式化的教材。
• 程式碼用C語言。 出版社說，許多演算法以C程式碼給出，所以使用其他語言的讀者要自己翻譯，或者藉助實作連結。
• 一半是參考內容。 出版社稱第二部分供翻閱和查考；從頭讀到尾，它只是一份目錄，而不是一串循序漸進的課程。

在課程中的定位

在本課程之中，Skiena 的書介於較平易的入門書和嚴謹的教材之間。Cormen 的 Algorithms Unlocked 是數學要求不高的簡短入門書，Roughgarden 的 Algorithms Illuminated 是帶免費影片講座的、口語化的四部分講解；兩者都可以先讀。Cormen 等人的 Introduction to Algorithms 是以嚴謹講解和虛擬碼著稱的綜合教材，需要證明時是自然的配套讀物。

對於第11–12章和第19章的困難問題部分，專門的書可以走得更遠：Vazirani 的 Approximation Algorithms 與 Williamson 和 Shmoys 的 The Design of Approximation Algorithms 對近似演算法講得深入得多，Mitzenmacher 和 Upfal 的 Probability and Computing 則是進入隨機演算法的進階途徑。

如何使用本書

本書適合已經會程式設計、接觸過基本資料結構的學生，也適合準備技術面試的從業者，後者是出版社提到的用途之一。想判斷自己面對的是哪一類問題的人，也能從中受益。

一個實用的讀法：

• 核心（第一部分）： 內容熟悉的話，第1–4章快速過一遍；第5–10章按順序讀，它們是主要的技巧庫；第11–12章讀難解性；第13章作為這一部分收尾的簡短設計章節。
• 參考（第二部分）： 讀完入口一章後，在遇到具體問題時查目錄，順著它給出的實作和進一步文獻的線索走，而不是一章接一章地讀。
• 練習： 做習題，包括面試風格的題目，並用作者網站上的題解維基和講課影片核對。
• 搭配： 手邊放一本像 Introduction to Algorithms 這樣嚴謹的教材，用於查證明；再用自己的語言實作幾個演算法，與書中的C程式碼對照。