Python算法設計與分析

來自 孔夫子網 的圖片

《Python算法設計與分析》，王碩，董文馨，張舒行，張潔，李秉倫 著，出版社： 人民郵電出版社。

人民郵電出版社是全國優秀出版社、全國百佳圖書出版單位。人民郵電出版社出版領域涵蓋科技出版、教育出版、大眾出版，涉及信息技術、通信、工業技術、科普、經濟管理、攝影、藝術、運動與休閒、心理學、少兒、大中專教材等10餘個出版門類，年出版圖書近萬種。

目錄

內容簡介

本書主要內容包括： 算法基礎 、 排序算法 、 查找算法 、 雙指針 、 哈希算法 、 深度優先搜索 、 廣度優先搜索 、 回溯算法 、 動態規劃 、 貪心算法 、 分治算法 、 並查集 、 最短路徑 、 數論算法 等。

作者介紹

王碩，軟件工程師、北京理工大學客座講師，從事計算機教育多年，擅長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