目錄



第1章 引言 1

1.1 這是一本怎么樣的書 2

1.1.1 本書將主要涉及以下內容 3

1.1.2 本書還將簡單或部分涉及

以下內容 3

1.1.3 本書不會涉足以下領域 3

1.2 為什么要讀這本書 3

1.3 一些準備工作 5

1.4 本書主要內容 5

1.5 本章小結 7

1.6 如果您感興趣 7

1.7 練習題 7

1.8 參考資料 8

第2章 基礎知識 9

2.1 計算領域中一些核心理念 9

2.2 漸近記法 11

2.2.1 我看不懂這些希臘文 12

2.2.2 交通規則 14

2.2.3 讓我們拿漸近性問題

練練吧 16

2.2.4 三種重要情況 19

2.2.5 實證式算法評估 20

2.3 圖與樹的實現 24

2.3.1 鄰接列表及其類似結構 26

2.3.2 鄰接矩陣 29

2.3.3 樹的實現 32

2.3.4 多種表示法 35

2.4 請提防黑盒子 36

2.4.1 隱性平方級操作 37

2.4.2 浮點運算的麻煩 38

2.5 本章小結 41

2.6 如果您感興趣 42

2.7 練習題 42

2.8 參考資料 43

第3章 計數初步 46

3.1 求和式的含義 46

3.1.1 更多希臘字母 47

3.1.2 求和式的運用 47

3.2 兩種賽制的故事 48

3.2.1 握手問題 48

3.2.2 龜兔賽跑 50

3.3 子集與排列組合 54

3.4 遞歸與遞歸式 56

3.4.1 手動推導 57

3.4.2 幾個重要例子 59

3.4.3 猜測與檢驗 62

3.4.4 主定理：一刀切式的

解決方案 65

3.5 這一切究竟是什么呢 67

3.6 本章小結 69

3.7 如果您感興趣 69

3.8 練習題 70

3.9 參考資料 71

第4章 歸納、遞歸及歸簡 72

4.1 哦，這其實很簡單 73

4.2 一而再，再而三 74

4.3 魔鏡，魔鏡 77

4.4 基于歸納法（與遞歸法）的設計 82

4.4.1 尋找*大排列 82

4.4.2 明星問題 86

4.4.3 拓撲排序問題 88

4