A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills（資料結構與演算法常識指南）

引用

Wengrow, J. (2020). A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills (2nd ed.). The Pragmatic Bookshelf.

章節概要

第2版共506頁、二十章，每章以「Wrapping Up」（小結）和一組練習結束，書末附錄給出所有章節練習的解答。序言介紹本書的讀者物件、本版新增內容、閱讀方法、程式碼示例和線上資源；出版社提供原始碼下載。程式碼示例使用JavaScript、Python和Ruby。據出版社介紹，第2版為每一章都加了練習，並新增了關於遞迴、動態規劃、在日常程式碼中使用大O記號以及堆和字典樹的章節。

第1–3章：為什麼資料結構很重要；為什麼演算法很重要；O Yes! 大O記號

本書的方法在第1章中確立（該章有免費節選）：一個操作的速度不是用時間來衡量，而是用它所需的步數來衡量。這一章計算陣列讀取、查詢、插入和刪除各需多少步，然後把陣列與集合比較——在集合中，「不允許重複」這一條規則就改變了插入的代價。第2章介紹有序陣列，比較二分查詢與線性查詢；第3章把數步數的方法提煉為大O記號，包括對數和O(log N)。

第4–6章：用大O加快程式碼；藉助與不借助大O的程式碼最佳化；針對樂觀情形的最佳化

這三章藉助簡單排序演算法深化分析。氣泡排序（有免費節選）展示了一個平方級演算法，以及如何用線性解法取代平方級解法；選擇排序說明為什麼大O忽略常數，但同一類別中的兩個演算法仍可能有差別；插入排序引入最好、最壞和平均情況。

第7章：日常程式碼中的大O

這是新增的一章，也有節選，把分析應用於簡短的實用函式：偶數的平均值、拼詞、陣列抽樣、服裝標籤、迴文檢查、獲取全部商品以及密碼破解等。開頭說明，確定當前程式碼的大O是最佳化的第一步。

第8–9章：用雜湊表實現極速查詢；用堆疊和佇列寫出優雅的程式碼

雜湊表透過雜湊函式、衝突以及高效雜湊表的條件來講解，並展示了它在組織資料和加快程式碼兩方面的用途。堆疊和佇列被作為受約束的資料結構和抽象資料型別來介紹。

第10–13章：用遞迴遞迴地遞迴；學會用遞迴來寫；動態規劃；追求速度的遞迴演算法

遞迴部分從如何閱讀遞迴程式碼和基準情形講起，經過遞迴問題的類別與自頂向下的思維方式（爬樓梯問題、生成變位詞），再到透過記憶化和自底向上兩種方式實現的動態規劃。第13章把遞迴用於劃分、快速排序及其最壞情況、快速選擇，並指出排序可以成為解決其他問題的關鍵。

第14–17章：基於節點的資料結構；用二叉搜尋樹加速一切；用堆分清輕重緩急；試試字典樹

講連結串列和雙向連結串列（包括用它們實現的佇列），帶插入、刪除和遍歷的二叉搜尋樹，作為優先佇列的堆（包括用陣列儲存堆以及「最後一個節點」問題），以及用於實現自動補全的字典樹（trie）。

第18章：用圖連線一切

講有向圖、物件導向的實現、深度優先搜尋和廣度優先搜尋及其效率、加權圖和迪傑斯特拉演算法。

第19–20章：應對空間限制；程式碼最佳化技巧

第19章把大O推廣到記憶體，討論時間與空間的權衡以及遞迴隱藏的空間開銷。第20章彙總了實用的最佳化策略：從當前的大O出發，設想可能達到的最佳大O，尋找「神奇查詢」（magical lookups），識別模式，使用貪心演算法，以及更換資料結構。

核心概念

第1–7章：衡量效率

• 步數而非秒數：操作的速度就是它所需的步數，與硬體無關。
• 大O記號：在忽略常數的前提下，描述步數如何隨N個數據元素增長。
• 最好、最壞與平均情況：同一演算法在不同輸入下表現不同的原因。
• 二分查詢：每一步把有序陣列折半，這就是O(log N)的來源。

第8–13章：查詢、約束與遞迴

• 雜湊表：藉助雜湊函式按鍵查詢，並透過處理衝突保持查詢速度。
• 抽象資料型別：由所允許的操作來定義的堆疊和佇列。
• 遞迴與基準情形：用問題自身更小的例項來求解問題。
• 記憶化與自底向上的動態規劃：消除對重疊子問題的重複遞迴呼叫。

第14–18章：基於節點的結構

• 連結串列：由連結相連的節點，讀取和插入的代價與陣列不同。
• 二叉搜尋樹與堆：為快速查詢而有序的樹，或為快速取得最高優先順序元素而有序的樹。
• 圖搜尋與迪傑斯特拉演算法：深度優先和廣度優先遍歷，以及加權圖中的最短路徑。

第19–20章：空間與最佳化

• 空間複雜度：應用於記憶體的大O，包括遞迴使用的呼叫堆疊。
• 最佳化技巧：尋找更快演算法的有意識的策略。

評析

優點

• 單一而具體的效率觀念。 免費的第1章展示了這種方法：在任何記號出現之前，所有關於速度的說法都歸結為在小例子上數步數，因此讀者是從經驗而不是從定義出發建立大O的概念。
• 分析普通程式碼。 第7章分析真實程式碼庫中常見的簡短函式，第20章把分析轉化為一套最佳化習慣，從而把理論與在職程式設計師實際編寫的程式碼聯絡起來。
• 練習附完整解答。 每章都以練習結束，附錄給出全部二十章的解答，便於自學。
• 多語言示例。 JavaScript、Python和Ruby的示例讓在職的Web開發者容易上手；出版社沒有列出程式設計以外的先修要求。

局限

• 分析不夠形式化。 大O是透過數步數引入的；目錄中看不到形式化定義、正確性證明或遞推式求解，準備學習理論課程的學生需要一本更嚴謹的教材。
• 內容有所取捨。 歸併排序、平衡搜尋樹、最小生成樹等標準演算法沒有出現在節標題中；本書涵蓋了核心結構，但不覆蓋大學課程的全部內容。
• 只有動態型別語言的示例。 程式碼使用JavaScript、Python和Ruby；課程使用Java或C++的學生需要自己改寫實現。

在課程中的定位

在本課程中，本書與Bhargava的 Grokking Algorithms 同為平易的入門讀物。兩者都適合會程式設計但沒有電腦科學背景的讀者：Wengrow在數步數和分析日常程式碼上花的篇幅更多，並配有帶解答的練習；Bhargava更多依靠插圖，還涉及貪心演算法和近似演算法等主題。先讀哪一本都可以；想對同樣的核心思想獲得第二種講解的讀者，兩本都讀也很合理。

讀完本書後，課程轉向完整的教科書。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 則是要到很久以後才讀的專門著作。

如何使用本書

本書面向希望為日常工作理解資料結構與演算法的程式設計師，包括自學和培訓班出身的開發者，以及正在修讀第一門資料結構課程的學生。讀者只需掌握任意一種語言的基本程式設計和中學算術；對數在第3章中有講解。

實用閱讀計畫：

• 核心（按順序）： 第1–9章。本書的分析是逐步累積的，第7章對真實程式碼的分析值得認真完成。
• 遞迴部分： 把第10–13章作為一個整體來讀；講動態規劃的第12章依賴於前兩章。
• 資料結構： 第14–18章。時間不夠時，初讀可以跳過堆和字典樹（第16–17章），但圖（第18章）不應跳過。
• 綜合： 第19–20章為全書收尾，適合在技術面試或課程考試前複習。

先做每章的練習再看解答；用自己最常用的語言把可下載的程式碼敲一遍並執行，對同一任務的慢版本和快版本計時，親眼看看步數的差別。如果正在修讀大學課程，可以在讀完本書每個部分後再讀一本正式教材的對應章節，當形式化的講解難以理解時，再回到本書的解釋。