Python算法設(shè)計(jì)與分析

第1章 算法初步 1
1．1　什么是算法　1
1．1．1　算法的定義　1
1．1．2　算法與程序的區(qū)別　1
1．2　時(shí)間復(fù)雜度　2
1．2．1　運(yùn)行時(shí)間和程序復(fù)雜程度的
關(guān)系　2
1．2．2　時(shí)間復(fù)雜度是漸進(jìn)的　2
1．2．3　簡(jiǎn)單程序的時(shí)間復(fù)雜度分析　3
1．2．4　時(shí)間復(fù)雜度的意義　6
1．3　空間復(fù)雜度　8
1．4　算法的應(yīng)用　8
1．5　Python算法的優(yōu)勢(shì)　9
1．6　小結(jié)　9
1．7　習(xí)題　10
第2章　排序算法　12
2．1　初級(jí)排序算法　12
2．1．1　插入排序　12
2．1．2　選擇排序　14
2．1．3　冒泡排序　17
2．2　高級(jí)排序算法　19
2．2．1　歸并排序　19
2．2．2　快速排序　21
2．2．3　希爾排序　24
2．2．4　堆排序　26
2．2．5　桶排序　30
2．3　小結(jié)　32
2．4　習(xí)題　32
第3章　查找　34
3．1　順序查找　34
3．2　二分查找　35
3．3　樹　41
3．4　二叉樹　43
3．4．1　二叉樹的性質(zhì)　43
3．4．2　滿二叉樹　44
3．4．3　完全二叉樹　44
3．4．4　創(chuàng)建二叉樹　45
3．4．5　遍歷二叉樹　46
3．5　二叉搜索樹　47
3．5．1　二叉搜索樹基礎(chǔ)　47
3．5．2　二叉搜索樹的操作　47
3．6　平衡二叉樹　56
3．6．1　二叉搜索樹的效率　56
3．6．2　AVL樹　56
3．7　小結(jié)　62
3．8　習(xí)題　62
第4章　雙指針問題　65
4．1　單鏈表　65
4．1．1　建立單鏈表　65
4．1．2　遍歷單鏈表　66
4．1．3　插入單鏈表　66
4．1．4　刪除單鏈表第n個(gè)數(shù)　68
4．2　雙指針的應(yīng)用　69
4．2．1　數(shù)組合并問題　69
4．2．2　刪除單鏈表倒數(shù)第n個(gè)數(shù)　71
4．3　小結(jié)　72
4．4　習(xí)題　72
第5章　哈希算法　73
5．1　哈希算法的原理　73
5．2　哈希函數(shù)　74
5．2．1　除法哈希算法　74
5．2．2　乘法哈希算法　75
5．2．3　平方取中法　75
5．2．4　隨機(jī)數(shù)哈希算法　75
5．3　解決沖突　76
5．3．1　開放定址法　76
5．3．2　拉鏈址法　77
5．4　哈希算法的應(yīng)用　78
5．4．1　兩個(gè)數(shù)的和問題　78
5．4．2　團(tuán)體賽問題　79
5．4．3　猜數(shù)字游戲　81
5．5　小結(jié)　83
5．6　習(xí)題　83
第6章　深度優(yōu)先搜索算法　85
6．1　搜索　85
6．2　圖上的深度優(yōu)先搜索　85
6．2．1　無向圖　85
6．2．2　圖的術(shù)語　86
6．2．3　圖上的搜索　88
6．2．4　經(jīng)典例題講解（最大的油田）　89
6．3　二叉樹上的深度優(yōu)先搜索　91
6．3．1　二叉樹相關(guān)術(shù)語　91
6．3．2　二叉樹上的搜索　92
6．3．3　經(jīng)典例題講解（員工派對(duì)）　92
6．3．4　經(jīng)典例題講解（城市危機(jī)）　97
6．4　小結(jié)　105
6．5　習(xí)題　106
第7章　廣度優(yōu)先搜索算法　107
7．1　依舊是圖的搜索　107
7．2　隊(duì)列中的存儲(chǔ)方式　108
7．3　經(jīng)典例題講解　111
7．3．1　艱難旅行　111
7．3．2　混亂地鐵　114
7．3．3　溫室大棚　116
7．4　小結(jié)　120
7．5　習(xí)題　120
第8章　回溯算法　121
8．1　回溯算法原理　121
8．2　回溯算法的應(yīng)用　124
8．2．1　N皇后　124
8．2．2　數(shù)獨(dú)　128
8．2．3　排列組合　132
8．2．4　兩個(gè)擴(kuò)展問題　137
8．3　小結(jié)　139
8．4　習(xí)題　139
第9章　動(dòng)態(tài)規(guī)劃　141
9．1　動(dòng)態(tài)規(guī)劃介紹　141
9．2　礦工問題　141
9．2．1　問題描述　141
9．2．2　問題分析　142
9．2．3　參考實(shí)現(xiàn)　145
9．3　爬樓梯問題　146
9．3．1　問題描述　146
9．3．2　問題分析　147
9．3．3　參考實(shí)現(xiàn)　149
9．4　背包問題　149
9．4．1　問題描述　149
9．4．2　問題分析　150
9．4．3　問題實(shí)例　151
9．4．4　參考實(shí)現(xiàn)　153
9．5　最長(zhǎng)遞增子序列問題　154
9．5．1　問題描述　154
9．5．2　改進(jìn)算法　155
9．5．3　參考實(shí)現(xiàn)　156
9．6　小結(jié)　157
9．7　習(xí)題　157
第10章　貪心算法　158
10．1　貪心算法介紹　158
10．2　硬幣找零問題　159
10．2．1　問題描述　159
10．2．2　問題實(shí)例　159
10．2．3　參考實(shí)現(xiàn)　160
10．3　活動(dòng)安排問題　160
10．3．1　問題描述　160
10．3．2　參考實(shí)現(xiàn)　161
10．4　哈夫曼編碼　162
10．4．1　問題描述　163
10．4．2　哈夫曼樹　163
10．4．3　貪心選擇性質(zhì)　165
10．4．4　最優(yōu)子結(jié)構(gòu)性質(zhì)　166
10．4．5　參考實(shí)現(xiàn)　166
10．5　小結(jié)　167
10．6　習(xí)題　168
第11章　分治算法　169
11．1　分治算法原理　169
11．2　分治算法應(yīng)用　170
11．2．1　二分查找　170
11．2．2　二維數(shù)組的查找　171
11．2．3　快速凸包算法　173
11．2．4　快速傅氏變換　178
11．3　小結(jié)　183
11．4　習(xí)題　183
第12章　并查集　184
12．1　并查集介紹　184
12．1．1　并查集的構(gòu)造方法　184
12．1．2　并查集的應(yīng)用　184
12．1．3　并查集3種基本操作的Python實(shí)現(xiàn)　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　小結(jié)　193
12．5　習(xí)題　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　習(xí)題　222
第14章　數(shù)論算法　223
14．1　歐幾里得算法　223
14．1．1　算法分析與證明　223
14．1．2　算法代碼　224
14．1．3　算法應(yīng)用　224
14．2　中國(guó)余數(shù)定理　228
14．2．1　算法介紹　228
14．2．2　算法證明　229
14．2．3　算法代碼　229
14．3　素性檢驗(yàn)算法　230
14．3．1　費(fèi)馬素性檢驗(yàn)　230
14．3．2　米勒-拉賓素性檢驗(yàn)　231
14．3．3　算法代碼　233
14．4　小結(jié)　234
14．5　習(xí)題　234