Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People（演算法圖解）

引用

Bhargava, A. Y. (2024). Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People (2nd ed.). Manning Publications.

章節概要

第2版共320頁、十三章，有Daniel Zingaro撰寫的推薦序、作者序言，以及一節「關於本書」，說明如何使用本書、誰應該讀和全書的組織結構。據出版社介紹，書中有400多幅插圖，每章都有練習和程式碼示例，程式碼已更新為Python 3，新增了關於樹（二叉搜尋樹、平衡樹、B樹）和NP完全問題的內容，以及關於資料結構在現代CPU上效能的討論。每章開頭列出讀者將學到的內容，章末有小結（Recap）。

第1章：演算法簡介

全書的基礎：以二分查詢作為第一個演算法，執行時間與大O表示法，執行時間的不同增長速度，大O作為最壞情況的度量，並初步介紹旅行推銷員問題，作為執行時間極慢的一個例子。

第2章：選擇排序

從記憶體的工作原理講起，比較陣列和連結串列在讀取、在中間插入和刪除方面的表現，然後介紹選擇排序。本章說明它以第1章的大O表示法和對數為前提。

第3章：遞迴

講基線條件和遞迴條件、堆疊與呼叫堆疊，以及遞迴時呼叫堆疊的行為。作者建議讀者親自執行程式碼，並至少用紙筆逐步跟蹤一個遞迴函式；本章還引入了虛擬碼。

第4章：快速排序

把分而治之作為一種通用的解題策略，然後以快速排序作為它的第一個主要例子，再談大O表示法，比較歸併排序與快速排序，並對照平均情況與最壞情況。

第5章：雜湊表

講雜湊函式和雜湊表的常見用途（查詢、防止重複、用作快取），然後講決定效能的內部機制：衝突、效能和負載因子。

第6章：廣度優先搜尋

把圖作為對網路建模的方式加以介紹，用廣度優先搜尋尋找步數最少的最短路徑，講佇列、有向圖與無向圖以及拓撲排序。

第7–8章：樹；平衡樹

這是本版新增的內容。第7章藉助檔案目錄定義有根樹和二叉樹，引入深度優先搜尋並與廣度優先搜尋對比，還介紹了基於樹的壓縮演算法——霍夫曼編碼。第8章介紹二叉搜尋樹及平衡的重要性、AVL樹與旋轉、伸展樹，以及B樹及其優點。

第9章：戴克斯特拉演算法

講邊帶有行程時間時的加權圖和最短路徑，透過「換鋼琴」的例子展開，並討論戴克斯特拉演算法失效的負權邊以及演算法的實現。

第10章：貪婪演算法

講貪婪策略（教室排程問題）、背包問題和集合覆蓋問題、近似演算法，以及如何識別沒有已知快速精確解的NP困難問題。

第11章：動態規劃

重新討論背包問題，展示動態規劃如何在網格中由子問題逐步構造出解，列出關於網格如何變化的一組問題，並透過例項說明如何為新問題設計動態規劃解法。

第12章：K最近鄰演算法

機器學習的初步：用K最近鄰進行分類、構建推薦系統、特徵提取、迴歸，以及這種方法的用途和局限。

第13章：接下來如何做

簡要介紹本書沒有涉及的十種演算法，包括線性迴歸、倒排索引、傅立葉變換、並行演算法和MapReduce，並給出進一步閱讀的建議。

核心概念

第1–4章：執行時間、排序與遞迴

• 大O表示法：演算法執行時間如何隨輸入規模增長，按最壞情況給出。
• 二分查詢：反覆把有序列表折半，複雜度為O(log n)而不是O(n)。
• 陣列與連結串列：讀取快與插入、刪除快之間的對比，與記憶體的工作原理相關。
• 遞迴與呼叫堆疊：基線條件、遞迴條件以及待完成呼叫組成的堆疊。
• 分而治之：把問題化為更小的例項，如快速排序。

第5–9章：雜湊表、圖與樹

• 雜湊表：平均為常數時間的查詢，衝突和負載因子決定其效能。
• 廣度優先搜尋：用佇列求無權圖中的最短路徑。
• 深度優先搜尋與霍夫曼編碼：樹的遍歷以及基於樹的壓縮演算法。
• 平衡樹：AVL樹、伸展樹和B樹，在資料變化時仍能保持快速查詢。
• 戴克斯特拉演算法：邊權非負的圖中的最短路徑。

第10–13章：難題及更遠處

• 貪婪演算法與近似：透過區域性最優選擇，快速得到NP困難問題的較好答案。
• 動態規劃：先解子問題，再逐步構建整個問題的解。
• K最近鄰：根據特徵相似度進行分類和迴歸。

評析

優點

• 以圖示和例項為中心。 出版社稱書中有400多幅插圖，公開的各章開頭展示了這種風格：每個概念都先從一個具體場景出發（遞迴是閣樓裡上了鎖的手提箱，雜湊表是雜貨店，廣度優先搜尋是穿越舊金山的公車路線），然後才給出演算法。
• 篇幅短而覆蓋廣。 320頁就從二分查詢講到NP困難問題、近似演算法、動態規劃和K最近鄰，最後一章還指向更多主題。
• 第2版有所更新。 關於樹和平衡樹的新章節填補了第1版的空白，程式碼使用Python 3，原始碼釋出在GitHub上。
• 鼓勵主動閱讀。 例如遞迴一章要求讀者執行程式碼並手工跟蹤遞迴函式，出版社也說明每章都有練習。

局限

• 重直觀而非證明。 出版社「不需要高深數學」的定位意味著正確性和執行時間是透過例子來解釋，而不是推匯出來的；修讀大學課程的學生仍需要一本有證明的教材。
• 每個主題都講得簡短。 在插圖很多的320頁中容納十三章，每種演算法的篇幅有限；第13章明確只是概覽十個主題。
• 只用Python。 全部程式碼都是Python，使用其他語言的讀者需要自己改寫。

在課程中的定位

本書是本課程中最直觀的入門讀物，與Wengrow的 A Common-Sense Guide to Data Structures and Algorithms 互為搭配。Wengrow在數步數和分析日常程式碼上花的篇幅更多，併為每道練習提供解答；Bhargava的分析較輕，但覆蓋更多演算法內容，包括平衡樹、戴克斯特拉演算法、NP困難問題和K最近鄰。覺得其中一本講解難懂的讀者，可以換另一本看。

讀完這兩本之後，Goodrich、Tamassia和Goldwasser的 Data Structures and Algorithms in Java 以及Pat Morin免費提供的 Open Data Structures 會給出帶有實現和證明的完整大學課程內容。Peter Brass的 Advanced Data Structures 和Chris Okasaki的 Purely Functional Data Structures 是很久以後才讀的專門著作。貪婪演算法和動態規劃兩章也可以作為演算法課程的輕鬆預習。

如何使用本書

本書適合會一點程式設計（任何語言均可）、想直觀入門演算法的讀者：自學的程式設計師、在第一門資料結構課程之前或期間的學生，以及準備技術面試的人。有Python經驗會有幫助，但示例都很短。

實用閱讀計畫：

• 核心： 按順序讀第1–6章。每章都建立在前一章之上：大O、陣列與連結串列、遞迴、分而治之、雜湊表，然後是圖。
• 樹與圖： 第7–9章。第8章的平衡樹初讀時可以略讀，但第9章完成了第6章開始的最短路徑話題。
• 解題策略： 第10–11章最好一起讀，因為第11章重新討論了第10章的背包問題。
• 選讀： 對機器學習感興趣的讀者讀第12章；第13章可作為閱讀清單。

執行GitHub倉庫中的Python程式碼並改變輸入，像書中建議的那樣手工跟蹤遞迴函式和圖搜尋。進入下一章之前先完成本章練習。如果是為課程而讀，可在每個部分之後閱讀一本正式教材的相應章節，補上本書省略的證明和分析。