《算法設計與分析(Python)》是2018年1月清華大學出版社出版的圖書，作者是程振波、李曲、王春平。
基本介紹
- 中文名：算法設計與分析(Python)
- 作者：程振波、李曲、王春平
- ISBN：9787302477488
- 定價：39元
- 出版社：清華大學出版社
- 出版時間：2018年1月
內容簡介,圖書目錄,
內容簡介
本書介紹了算法設計與分析的基本技巧，主要包括遞歸、分治、動態規劃、貪心和隨機等算法，以及利用這些算法求解計算問題的時間複雜度分析等內容。通過諸多有趣的實例，向讀者介紹了算法設計的思想，以便讀者能形成算法思維的固定模式去解決問題。在介紹每一類算法範式以及分析算法複雜度時，都力求建立直觀的思維過程，而摒棄過深的數學證明。書中所有算法均採用 Python語言描述，讀者能從中學習到許多算法實現的技巧，從而提高編寫程式的能力。
本書可作為高等學校計算機專業大一、大二或者學習過程式設計的非計算機專業學生的算法設計與分析教材。
圖書目錄
第 1章引言 1
1 1算法的定義 1
1 1 1算法的屬性 2
1 1 2效率的定義 3
1 2算法設計與分析舉例5
1 2 1尋找局部高點 -1D 5
1 2 2圖書管理 8
1 3小結 10 課後習題 11
第 2章漸進分析與 Python計算模型 13
2 1引言 13
2 2計算模型 13
2 3算法的漸進分析 14
2 4 Python計算模型 17
2 4 1控制流語句 17
2 4 2數據結構 19
2 5算法分析實例 21
2 5 1求最大值 22
2 5 2二分搜尋 22
2 5 3子集和問題 23
2 6小結 24 課後習題 25
第 3章問題求解與代碼最佳化27
3 1引言 27
3 2文檔比較 27
3 2 1問題提出 27
3 2 2算法設計 28
3 2 3算法最佳化 31
3 3拼寫矯正 33
3 3 1問題提出 33
3 3 2算法設計 33
3 4穩定匹配問題 36
3 4 1問題提出 36
3 4 2算法設計 38
3 5小結 40 課後習題 41
第 4章遞歸算法與遞歸函式42
4 1引言 42
4 2遞歸的組成結構 42
4 2 1如何籌集巨款 42
4 2 2上線與下線 44
4 3遞歸算法的執行 45
4 3 1跟蹤函式的執行 47
4 4利用遞歸算法求解問題 51
4 4 1回文判斷 51
4 4 2全排列 53
4 4 3漢諾塔問題 54
4 4 4雪花曲線 57
4 5遞歸函式的求解 58
4 5 1替換法 59
4 5 2主分析法 60
4 6小結 62 課後習題 63
第 5章排序與樹結構64
5 1引言 64
5 2遞歸與排序 65
5 2 1選擇排序 65
5 2 2插入排序 67
5 2 3合併排序 69
5 3二叉搜尋樹 72
5 3 1 BST的實現74
5 3 2插入新結點 75
5 3 3 BST上查找77
5 3 4二叉樹修剪 78
IX
5 4堆 81
5 4 1堆化操作 81
5 4 2構造堆 83
5 4 3堆排序 85
5 4 4合併 k個有序序列 86
5 5小結 87 課後習題 88
第 6章分治算法 90
6 1引言 90
6 2股票的買賣 91
6 2 1問題描述 91
6 2 2算法設計 91
6 3統計逆序 94
6 3 1問題描述 94
6 3 2算法設計 94
6 4空間最小距離點對 97
6 4 1問題描述 97
6 4 2算法設計 98
6 5尋找第 k小的數 103
6 5 1問題描述 103
6 5 2算法設計 103
6 6大整數乘法107
6 6 1問題描述 107
6 6 2算法設計 108
6 7小結109 課後習題 109
第 7章圖搜尋算法111
7 1引言111
7 2圖搜尋的套用 112
7 3圖的表示 113
7 4寬度優先搜尋 114
7 4 1寬度優先搜尋算法114
7 4 2 BFS算法分析 117
7 4 3 BFS算法套用舉例 117
7 5深度優先搜尋 121
7 5 1深度優先搜尋算法121
7 5 2 DFS算法分析 124
7 5 3 DFS套用舉例 124
7 6小結126 課後習題 126
第 8章貪心算法 128
8 1引言128
8 2硬幣找零 128
8 2 1問題描述 128
8 2 2問題求解 129
8 2 3最優解證明130
8 3間隔任務規劃 130
8 3 1問題描述 130
8 3 2問題求解 131
8 3 3最優解證明133
8 4單源最矩路徑問題134
8 4 1 Dijkstra問題 135
8 4 2算法的正確性 136
8 4 3算法的性能最佳化 137
8 5最小生成樹139
8 5 1 Prim算法 140
8 5 2算法實現 142
8 6小結145 課後習題 145
第 9章動態規划算法 147
9 1引言147
9 2再遇斐波那契數 147
9 3一維動態規劃 151
9 3 1拾撿硬幣 152
9 3 2連續子序列和的最大值 155
9 3 3瘋狂的 8 157
9 3 4文本排版 161
9 3 5完全信息的 21點165
9 4二維動態規劃 169
9 4 1矩陣的括弧169
9 4 2字元串編輯距離 173
9 4 3 0-1背包問題 176
XI
9 5小結179 課後習題 180
第 10章最大流算法套用 182
10 1引言 182
10 2最大流算法 182
10 2 1 Ford-Fulkerson算法 186
10 2 2 Edmond-Karp算法 187
10 3最大流算法的套用 189
10 3 1二向圖最大匹配問題 189
10 3 2檔案傳輸中的不重合邊問題 191
10 4小結 193 課後習題 193
第 11章隨機算法 195
11 1引言 195
11 2矩陣乘積結果驗證 196
11 3快速排序 198
11 3 1根據支點數劃分輸入序列 199
11 3 2選擇支點數 200
11 3 3隨機快速排序 202
11 4選擇第 k小的數 203
11 5尋找最小割邊 206
11 6小結 209 課後習題 209
第 12章算法複雜度 210
12 1引言 210
12 2問題的分類 210
12 2 1易解與難解 210
12 2 2無解的問題 211
12 2 3難解問題的證明213
12 3 NPC問題套用 214
12 3 1決策問題214
12 3 2問題的化約 215
12 3 3 NP問題 215
12 3 4 NPC問題 216
12 4 P等於 NP嗎 218
12 5小結 219 課後習題 219 索引 221 代碼列表 222 參考文獻 226
