算法學習指南

序 1
前言 3
第 1 章 解決問題 9
1．1 什么是算法？ 9
1．2 在一個任意的列表中查找最大值 12
1．3 對關鍵操作進行計數(shù) 14
1．4 可以預測算法性能的模型 14
1．5 在一個隨機列表中查找兩個最大值 19
1．6 錦標賽算法 22
1．7 時間復雜度和空間復雜度 28
1．8 總結 29
1．9 挑戰(zhàn)練習 30
第 2 章 分析算法 33
2．1 使用實驗模型預測性能 34
2．2 乘法可以更快 36
2．3 性能分類 38
2．4 漸進性分析 39
2．5 對所有操作進行計數(shù) 42
2．6 對所有字節(jié)進行計數(shù) 43
2．7 關上一扇門，打開另一扇門 44
2．8 二分數(shù)組搜索 45
2．9 幾乎和π 一樣簡單 46
2．10 一石二鳥 48
2．11 綜述 52
2．12 曲線擬合與上下界的比較 53
2．13 總結 54
2．14 挑戰(zhàn)練習 55
第3 章 更好的散列，更適意的人生 58
3．1 值與鍵相關聯(lián) 58
3．2 散列函數(shù)和散列碼 63
3．3 (key，value)對的可散列結構 64
3．4 使用線性探查法檢測和解決沖突 65
3．5 用鏈表實現(xiàn)分離鏈表 70
3．6 從鏈表中刪除一個數(shù)據(jù)項 73
3．7 評估 75
3．8 增長的散列表 78
3．9 分析動態(tài)散列表的性能 83
3．10 完美散列 84
3．11 對（key，value）對進行迭代 87
3．12 總結 88
3．13 挑戰(zhàn)練習 89
第4 章 堆起來！ 93
4．1 最大二叉堆 99
4．2 插入(value，priority)對 101
4．3 刪除具有最高優(yōu)先級的值 104
4．4 用數(shù)組表示二叉堆 106
4．5 實現(xiàn)上浮和下沉 107
4．6 總結 111
4．7 挑戰(zhàn)練習 112
第5 章 深入淺出論排序！ 115
5．1 交換排序 116
5．2 選擇排序 117
5．3 平方時間級排序算法的剖析 119
5．4 分析插入排序和選擇排序的性能 121
5．5 遞歸和分治法 122
5．6 歸并排序 127
5．7 快速排序 131
5．8 堆排序 134
5．9 O(NlogN)等級算法的性能比較 136
5．10 Tim 排序 137
5．11 總結 140
5．12 挑戰(zhàn)練習 140
第6 章 二叉樹：掌上世界的無限可能 142
6．1 基礎知識 142
6．2 二叉查找樹 147
6．3 在二叉查找樹中搜索值 152
6．4 從二叉查找樹刪除值 153
6．5 遍歷二叉查找樹 157
6．6 分析二叉查找樹的性能 159
6．7 平衡二叉樹 161
6．8 分析平衡二叉樹的性能 168
6．9 使用二叉樹作為(key，value)符號表 168
6．10 使用二叉樹作為優(yōu)先隊列 169
6．11 總結 172
6．12 挑戰(zhàn)練習 173
第7 章 圖：連得上的才是好的！ 176
7．1 圖高效地存儲了實用的信息 176
7．2 使用深度優(yōu)先搜索解決迷宮問題 181
7．3 廣度優(yōu)先搜索提供了一種不同的搜索算法 186
7．4 有向圖 193
7．5 具有邊權重的圖 200
7．6 迪杰斯特拉算法 202
7．7 全頂點對的最短路徑 212
7．8 弗洛伊德-沃歇爾算法 215
7．9 總結 219
7．10 挑戰(zhàn)練習 220
第8 章 綜述 ． 223
8．1 Python 的內(nèi)置數(shù)據(jù)類型 225
8．2 在Python 中實現(xiàn)堆棧 227
8．3 在Python 中實現(xiàn)隊列 228
8．4 堆和優(yōu)先隊列的實現(xiàn) 229
8．5 進一步的探索 229