Python數據結構與算法分析 (第2版)
本書是使用Python闡述數據結構與算法的经典教材。涵蓋了Python基礎複習、算法分析（大O記法）、基本數據結構（棧、隊列、列表）、遞歸、搜索與排序、樹及圖算法。通過實戰代碼清單，幫助讀者理解如何透過Python高效地實現各種抽象數據類型。
課程總覽
📚 內容概要
本書是使用 Python 阐述資料結構與演算法的經典教材。涵蓋了 Python 基礎複習、演算法分析（大 O 記法）、基本資料結構（堆疊、佇列、列表）、遞迴、搜尋與排序、樹及圖演算法。透過實戰程式碼清單，幫助讀者理解如何透過 Python 高效地實現各種抽象資料類型。
唯有徹底掌握資料結構與演算法，才能真正精通 Python。
作者： 布拉德利·米勒（美國路德學院計算機科學榮譽教授）、戴維·拉努姆（IBM Watson 認知軟體工程師）
致謝： 感謝同事史蒂夫·哈伯德為第一版提供的大量反饋以及為新版提供的新素材，同時感謝各地同行寄信指出錯誤並提供意見。感謝迪科拉市 Java John's 咖啡館的瑪麗、鮑勃等服務生，允許我們在休假期間成為店內的「常駐作者」。此外，感謝 Franklin, Beedle & Associates 出版公司各位員工（特別是吉姆·萊西和湯姆·薩姆納）愉快的合作。最後，特別感謝我們兩人的妻子珍·米勒與布倫達·拉努姆，她們的愛與支持使本書終於成形。
🎯 學習目標
- 理解電腦科學、演算法與程式設計之間的關係，並掌握抽象資料類型 (ADT) 與資訊隱藏的概念。
- 熟練運用 Python 的內建集合資料類型（列表、元組、集合、字典）及控制結構（迴圈、分支、例外處理）。
- 掌握 Python 面向物件程式設計的核心：包括類別的定義、建構方法、運算子重載（如分數加法）、歐幾里得演算法應用，以及深淺相等的差異。
- 演算法多方案對比：能夠解釋異序詞檢測的四種方案（計數、排序、暴力、計數）及其對應的時間複雜度。
- Python 容器效能量化：掌握 Python 列表 (List) 與字典 (Dict) 核心操作的大 O 效率，並能區分
pop()與pop(i)的效能差異。 - 性能驗證能力：能夠利用
timeit模組設計實驗，驗證理論複雜度與實際執行時間的一致性。 - 理解並能區分線性資料結構（堆疊、佇列、雙端佇列、列表）的邏輯特性。
- 能夠使用 Python 的基礎集合（如列表）實作自訂的堆疊、佇列與雙端佇列。
- 掌握堆疊在表示式處理（中序轉後序、後序求值）與佇列在系統模擬（印表機模擬）中的應用。
- 掌握遞迴核心三原則：能夠準確識別並撰寫包含基本情況、狀態演變與自呼叫的遞迴函數。
課程 共 8 课时 · 预计 24.0h
課程
Lesson
This lesson introduces the core principles of computer science, focusing on problem-solving through algorithms, procedural abstraction, and Python’s object-oriented nature. Students will learn to manage complexity by leveraging Python’s dynamic variable references, efficient built-in data structures, and robust error-handling techniques to build reliable, scalable software.
本课程深入探讨了算法分析的核心工具——大O记法，通过异序词检测案例展示了从暴力法到计数法的性能优化过程。学习重点在于理解不同操作（如列表索引与pop操作）的复杂度差异，并掌握如何通过空间换时间及选择合适的数据结构来提升程序效率。
This lesson introduces linear data structures and the concept of Abstract Data Types (ADTs), focusing on the stack as a fundamental LIFO (Last-In, First-Out) structure. Students will learn to implement stacks in Python and apply them to complex tasks, including converting infix expressions to postfix notation and evaluating those expressions efficiently.
本课程深入探讨了递归算法的核心原理，重点讲解了递归三原则（基准情况、状态改变、自我调用）以及递归与系统调用栈之间的内在联系。通过进制转换、汉诺塔及动态规划等案例，学生将学习如何将复杂问题拆解为自相似的子问题，并掌握从递归思维向高效动态规划算法的进阶转换。
This lesson explores fundamental search and retrieval algorithms, progressing from $O(n)$ sequential search to the $O(\log n)$ efficiency of binary search and the $O(1)$ potential of hash tables. Students learn to optimize data access through divide-and-conquer strategies, sophisticated hash function design, and collision-handling techniques to build efficient, dictionary-like data structures.
This lesson explores the hierarchical and recursive nature of tree data structures, covering fundamental terminology, implementation methods like nested lists and object-oriented references, and the construction of expression trees. It also introduces essential tree traversal algorithms—preorder, inorder, and postorder—and explains how these recursive patterns are applied to tasks like file system analysis and AVL tree balancing.
This lesson introduces graph theory as a powerful tool for modeling real-world problems by abstracting entities as vertices and relationships as edges. Students will learn to implement graphs using adjacency lists, compare storage efficiency, and master the Breadth-First Search (BFS) algorithm to solve pathfinding and state-space challenges.
This lesson explores the memory efficiency of Python's ArrayList, explaining how amortized analysis ensures $O(1)$ performance for append operations through strategic over-allocation. It also covers the mathematical foundations of RSA encryption, demonstrating how modular exponentiation and divide-and-conquer algorithms optimize complex calculations for secure data processing.