Python數據結構與算法分析 (第2版)

📚 內容概要

本書是使用 Python 阐述資料結構與演算法的經典教材。涵蓋了 Python 基礎複習、演算法分析（大 O 記法）、基本資料結構（堆疊、佇列、列表）、遞迴、搜尋與排序、樹及圖演算法。透過實戰程式碼清單，幫助讀者理解如何透過 Python 高效地實現各種抽象資料類型。

唯有徹底掌握資料結構與演算法，才能真正精通 Python。

作者： 布拉德利·米勒（美國路德學院計算機科學榮譽教授）、戴維·拉努姆（IBM Watson 認知軟體工程師）

致謝： 感謝同事史蒂夫·哈伯德為第一版提供的大量反饋以及為新版提供的新素材，同時感謝各地同行寄信指出錯誤並提供意見。感謝迪科拉市 Java John's 咖啡館的瑪麗、鮑勃等服務生，允許我們在休假期間成為店內的「常駐作者」。此外，感謝 Franklin, Beedle & Associates 出版公司各位員工（特別是吉姆·萊西和湯姆·薩姆納）愉快的合作。最後，特別感謝我們兩人的妻子珍·米勒與布倫達·拉努姆，她們的愛與支持使本書終於成形。

🎯 學習目標

1. 理解電腦科學、演算法與程式設計之間的關係，並掌握抽象資料類型 (ADT) 與資訊隱藏的概念。
2. 熟練運用 Python 的內建集合資料類型（列表、元組、集合、字典）及控制結構（迴圈、分支、例外處理）。
3. 掌握 Python 面向物件程式設計的核心：包括類別的定義、建構方法、運算子重載（如分數加法）、歐幾里得演算法應用，以及深淺相等的差異。
4. 演算法多方案對比：能夠解釋異序詞檢測的四種方案（計數、排序、暴力、計數）及其對應的時間複雜度。
5. Python 容器效能量化：掌握 Python 列表 (List) 與字典 (Dict) 核心操作的大 O 效率，並能區分 pop() 與 pop(i) 的效能差異。
6. 性能驗證能力：能夠利用 timeit 模組設計實驗，驗證理論複雜度與實際執行時間的一致性。
7. 理解並能區分線性資料結構（堆疊、佇列、雙端佇列、列表）的邏輯特性。
8. 能夠使用 Python 的基礎集合（如列表）實作自訂的堆疊、佇列與雙端佇列。
9. 掌握堆疊在表示式處理（中序轉後序、後序求值）與佇列在系統模擬（印表機模擬）中的應用。
10. 掌握遞迴核心三原則：能夠準確識別並撰寫包含基本情況、狀態演變與自呼叫的遞迴函數。

🔹 第一課：Python 程式設計基礎與面向物件抽象

概述： 本課程模塊旨在引導學習者從電腦科學的基本理論過渡到 Python 程式設計實務。課程首先界定電腦科學、演算法與抽象資料類型 (ADT) 的核心定義，隨後深入講解 Python 的內建集合、控制結構與例外處理。最終透過建立 Fraction 類與「邏輯閘」繼承層次結構，展示面向物件程式設計 (OOP) 在過程抽象與資料抽象中的強大應用。

學習成果：

• 理解電腦科學、演算法與程式設計的關係，並掌握抽象資料類型 (ADT) 與資訊隱藏的概念。
• 熟練運用 Python 的內建集合資料類型（列表、元組、集合、字典）及控制結構（迴圈、分支、例外處理）。
• 掌握 Python 面向物件程式設計的核心：包括類別的定義、建構方法、運算子重載（如分數加法）、歐幾里得演算法應用，以及深淺相等的差異。

🔹 第二課：演算法分析與 Python 容器效能

概述： 本課程深入探討如何透過大 O 記法評估演算法效率，並以「異序詞檢測」為例，展示從 O(n!) 到 O(n) 不同複雜度的演進。同時，課程定量分析 Python 核心資料結構（列表與字典）的常用操作效能，旨在幫助開發者在實際程式設計中做出最佳的容器選擇與演算法設計。

學習成果：

• 演算法多方案對比：能夠解釋異序詞檢測的四種方案（計數、排序、暴力、計數）及其對應的時間複雜度。
• Python 容器效能量化：掌握 Python 列表 (List) 與字典 (Dict) 核心操作的大 O 效率，並能區分 pop() 與 pop(i) 的效能差異。
• 性能驗證能力：能夠利用 timeit 模組設計實驗，驗證理論複雜度與實際執行時間的一致性。

🔹 第三課：基本線性結構：堆疊、佇列與鏈結串列

概述： 本課程深入探討四種基礎線性資料結構：堆疊 (Stack)、佇列 (Queue)、雙端佇列 (Deque) 和列表 (List)。線性結構的核心在於項目之間保持相對順序，其主要差別在於新增與移除項目的方式。透過使用 Python 實作這些抽象資料類型 (ADT)，學習者將掌握如何利用 LIFO（後進先出）、FIFO（先進先出）等原則解決實際演算法問題，如表示式轉換、系統模擬及鏈結串列記憶體管理。

學習成果：

• 理解並能區分線性資料結構（堆疊、佇列、雙端佇列、列表）的邏輯特徵。
• 能夠使用 Python 的基礎集合（如列表）實作自訂的堆疊、佇列與雙端佇列。
• 掌握堆疊在表示式處理（中序轉後序、後序求值）與佇列在系統模擬（印表機模擬）中的應用。

🔹 第四課：遞迴演算法原理與動態規劃入門

概述： 本課程深入探討遞迴演算法的核心原理，從基礎的遞迴三原則出發，透過數值轉換、分形幾何、經典解謎（漢諾塔與迷宮）等範例，揭示遞迴呼叫的底層機制——棧幀。最後，課程引入動態規劃 (Dynamic Programming) 的概念，展示如何透過記憶化技術解決遞迴中的重複計算問題，從而實現演算法效率的質變。

學習成果：

• 掌握遞迴核心三原則：能夠準確識別並撰寫包含基本情況、狀態演變與自呼叫的遞迴函數。
• 透析底層執行機制：理解 Python 呼叫棧 (Stack Frame) 如何在遞迴過程中管理區域變數與回傳路徑。
• 具備複雜問題建模能力：能夠利用遞迴與回溯思維解決漢諾塔、迷宮尋路等非線性問題。

🔹 第五課：搜尋技術、雜湊與排序演算法

概述： 本課程模塊聚焦於電腦科學中核心的資料處理技術：搜尋、雜湊 (Hashing) 與排序。內容涵蓋從基礎的順序搜尋到高效的二分搜尋，深入探討雜湊表 (Hash Tables) 的構造原理、衝突解決方法及映射 (Map) 抽象資料類型的實作。同時詳細剖析冒泡排序、希爾排序與合併排序的演算法邏輯與效能表現。

學習成果：

• 理解並能比較順序搜尋與二分搜尋的適用場景及時間複雜度（O(n) 對 O(\log n)）。
• 掌握雜湊函數的設計（摺疊法、平方取中法）及衝突處理機制（線性探測、平方探測、連結法）。
• 能夠手動模擬並編程實作冒泡排序、希爾排序與合併排序，理解分治策略在排序中的應用。

🔹 第六課：樹狀結構：二元堆、搜尋樹與平衡樹 (AVL)

概述： 本課程深入探討電腦科學中最核心的資料結構——樹。我們將從基礎術語與二元樹的實作入手，逐步進階至二元樹的高階應用，包括表示式解析樹及其遍歷方法。隨後，我們將學習兩種高效的變體：用於優先權佇列的二元堆以及用於高效搜尋的二元搜尋樹 (BST)。最後，我們將研究 AVL 樹，透過旋轉操作維持平衡因子，解決 BST 在最壞情況下的效能退化問題。

學習成果：

• 能夠準確定義樹的核心術語（根、邊、路徑、高度等）並描述二元樹的遞迴性質。
• 掌握使用 Python 實作二元堆、二元搜尋樹及 AVL 樹的核心演算法（如插入、刪除、旋轉、再平衡）。
• 能夠執行並解釋三種樹的走訪演算法，並利用解析樹處理數學表示式。

🔹 第七課：圖論演算法：搜尋、最短路徑與最小生成樹

概述： 本課程深入探討圖論的基本理論及其在 Python 中的高效實作。內容涵蓋圖的抽象資料類型（鄰接矩陣與鄰接表）、基礎搜尋演算法（BFS 與 DFS）及其經典應用場景。最終進階至加權圖中的最短路徑 (Dijkstra) 與最小生成樹 (Prim) 演算法。

學習成果：

• 理解並能比較圖的兩種主要表示法（鄰接矩陣與鄰接表）的效能與適用場景。
• 掌握寬度優先搜尋 (BFS) 與深度優先搜尋 (DFS) 的演算法原理，並能解決路徑搜尋與周遊問題。
• 能夠應用圖演算法解決複雜邏輯依賴（拓撲排序）及網路連通性（強連通元件、最小生成樹）問題。

🔹 第八課：專題複習：RSA 加密、跳表與八元樹量化

概述： 本課程深入探討電腦科學中從基礎資料結構到複雜演算法的應用遷移。內容涵蓋 Python 列表 (ArrayList) 的底層實作與均攤分析、支援 RSA 加密的數論遞迴演算法、提升字典搜尋效率的跳表建構，以及利用八元樹進行數位影像顏色量化的原理。

學習成果：

• 理解 ArrayList 的記憶體佈局及均攤分析 (Amortized Analysis) 的數學推導。
• 掌握 RSA 加密的核心數學原理，包括同餘定理、冪剩餘及擴展歐幾里得演算法。
• 能夠描述跳表的層級結構、機率性建構過程及其 O(\log n) 的搜尋效率。