Python 算法設計與分析

王碩

*深軟件工程師、北京理工大學客座講師，從事計算機教育多年，擅長Python、Java、C語言、
數據結構和算法等，接觸數千學生，對算法有獨到見解。
平行致力於企業級軟件開發和計算機教育工作，
具有索尼中國研究院、四大國有銀行軟件開發中心工作經歷。

目錄：
第 1章 算法初步1
1.1　什麼是算法　1
1.1.1　算法的定義　1
1.1.2　算法與程序的區別　1
1.2　時間複雜度　2
1.2.1　運行時間和程序複雜程度的關係　2
1.2.2　時間複雜度是漸進的　2
1.2.3　簡單程序的時間複雜度分析　3
1.2.4　時間複雜度的意義　6
1.3　空間複雜度　8
1.4　算法的應用　8
1.5　Python算法的優勢　9
1.6　小結　9
1.7　習題　10

第 2章　排序算法　12
2.1　初級排序算法　12
2.1.1　插入排序　12
2.1.2　選擇排序　14
2.1.3　冒泡排序　17
2.2　*級排序算法　19
2.2.1　歸併排序　19
2.2.2　快速排序　21
2.2.3　希爾排序　24
2.2.4　堆排序　26
2.2.5　桶排序　30
2.3　小結　32
2.4　習題　32

第3章　查找　34
3.1　順序查找　34
3.2　二分查找　35
3.3　樹　41
3.4　二叉樹　43
3.4.1　二叉樹的性質　43
3.4.2　滿二叉樹　44
3.4.3　完全二叉樹　44
3.4.4　創建二叉樹　45
3.4.5　遍歷二叉樹　46
3.5　二叉搜索樹　47
3.5.1　二叉搜索樹基礎　47
3.5.2　二叉搜索樹的操作　47
3.6　平衡二叉樹　56
3.6.1　二叉搜索樹的效率　56
3.6.2　AVL樹　56
3.7　小結　62
3.8　習題　62

第4章　雙指針問題　65
4.1　單鍊錶　65
4.1.1　建立單鍊錶　65
4.1.2　遍歷單鍊錶　66
4.1.3　插入單鍊錶　66
4.1.4　刪除單鍊錶第n個數　68
4.2　雙指針的應用　69
4.2.1　數組合併問題　69
4.2.2　刪除單鍊錶倒數第n個數　71
4.3　小結　72
4.4　習題　72

第5章　哈希算法　73
5.1　哈希算法的原理　73
5.2　哈希函數　74
5.2.1　除法哈希算法　74
5.2.2　乘法哈希算法　75
5.2.3　平方取中法　75
5.2.4　隨機數哈希算法　75
5.3　解決衝突　76
5.3.1　開放定址法　76
5.3.2　拉鍊址法　77
5.4　哈希算法的應用　78
5.4.1　兩個數的和問題　78
5.4.2　團體賽問題　79
5.4.3　猜數字遊戲　81
5.5　小結　83
5.6　習題　83

第6章　深度優先搜索算法　85
6.1　搜索　85
6.2　圖上的深度優先搜索　85
6.2.1　無向圖　85
6.2.2　圖的術語　86
6.2.3　圖上的搜索　88
6.2.4　經典例題講解（*大的油田）　89
6.3　二叉樹上的深度優先搜索　91
6.3.1　二叉樹相關術語　91
6.3.2　二叉樹上的搜索　92
6.3.3　經典例題講解（員工派對）　92
6.3.4　經典例題講解（城市危機）　97
6.4　小結　105
6.5　習題　106

第7章　廣度優先搜索算法　107
7.1　依舊是圖的搜索　107
7.2　隊列中的存儲方式　108
7.3　經典例題講解　111
7.3.1　艱難旅行　111
7.3.2　混亂地鐵　114
7.3.3　溫室大棚　116
7.4　小結　120
7.5　習題　120

第8章　回溯算法　121
8.1　回溯算法原理　121
8.2　回溯算法的應用　124
8.2.1　N皇后　124
8.2.2　數獨　128
8.2.3　排列組合　132
8.2.4　兩個擴展問題　137
8.3　小結　139
8.4　習題　139

第9章　動態規劃　141
9.1　動態規劃介紹　141
9.2　礦工問題　141
9.2.1　問題描述　141
9.2.2　問題分析　142
9.2.3　參考實現　145
9.3　爬樓梯問題　146
9.3.1　問題描述　146
9.3.2　問題分析　147
9.3.3　參考實現　149
9.4　背包問題　149
9.4.1　問題描述　149
9.4.2　問題分析　150
9.4.3　問題實例　151
9.4.4　參考實現　153
9.5　*長遞增子序列問題　154
9.5.1　問題描述　154
9.5.2　改進算法　155
9.5.3　參考實現　156
9.6　小結　157
9.7　習題　157

第 10章　貪心算法　158
10.1　貪心算法介紹　158
10.2　硬幣找零問題　159
10.2.1　問題描述　159
10.2.2　問題實例　159
10.2.3　參考實現　160
10.3　活動安排問題　160
10.3.1　問題描述　160
10.3.2　參考實現　161
10.4　哈夫曼編碼　162
10.4.1　問題描述　163
10.4.2　哈夫曼樹　163
10.4.3　貪心選擇性質　165
10.4.4　*優子結構性質　166
10.4.5　參考實現　166
10.5　小結　167
10.6　習題　168

第 11章　分治算法　169
11.1　分治算法原理　169
11.2　分治算法應用　170
11.2.1　二分查找　170
11.2.2　二維數組的查找　171
11.2.3　快速凸包算法　173
11.2.4　快速傅氏變換　178
11.3　小結　183
11.4　習題　183

第 12章　並查集　184
12.1　並查集介紹　184
12.1.1　並查集的構造方法　184
12.1.2　並查集的應用　184
12.1.3　並查集3種基本操作的Python實現　186
12.2　朋友圈　187
12.2.1　問題描述　187
12.2.2　問題分析　187
12.2.3　代碼　188
12.3　圖的子元素　190
12.3.1　問題描述　190
12.3.2　問題分析　190
12.3.3　代碼　192
12.4　小結　193
12.5　習題　193

第 13章　*短路徑算法　194
13.1　戴克斯特拉算法　194
13.1.1　算法介紹　194
13.1.2　算法證明　199
13.1.3　算法代碼　200
13.2　貝爾曼-福特算法　202
13.2.1　算法介紹　203
13.2.2　算法證明　205
13.2.3　算法代碼　206
13.3　弗洛伊德算法　208
13.3.1　算法介紹　208
13.3.2　算法代碼　212
13.4　A*搜索算法　215
13.4.1　算法介紹　215
13.4.2　算法證明　219
13.4.3　算法代碼　220
13.5　習題　222

第 14章　數論算法　223
14.1　歐幾里得算法　223
14.1.1　算法分析與證明　223
14.1.2　算法代碼　224
14.1.3　算法應用　224
14.2　中國餘數定理　228
14.2.1　算法介紹　228
14.2.2　算法證明　229
14.2.3　算法代碼　229
14.3　素性檢驗算法　230
14.3.1　費馬素性檢驗　230
14.3.2　米勒-拉賓素性檢驗　231
14.3.3　算法代碼　233
14.4　小結　234
14.5　習題　234