Python算法教程pdf中文版

第1章  引言 1

1.1  這是一本怎么樣的書   2

1.1.1 本書將主要涉及以下內(nèi)容         3

1.1.2 本書還將簡(jiǎn)單或部分涉及

以下內(nèi)容         3

1.1.3 本書不會(huì)涉足以下領(lǐng)域    3

1.2  為什么要讀這本書        3

1.3  一些準(zhǔn)備工作        5

1.4  本書主要內(nèi)容        5

1.5  本章小結(jié)        7

1.6  如果您感興趣        7

1.7  練習(xí)題   7

1.8  參考資料        8

第2章  基礎(chǔ)知識(shí) 9

2.1  計(jì)算領(lǐng)域中一些核心理念   9

2.2  漸近記法        11

2.2.1 我看不懂這些希臘文         12

2.2.2 交通規(guī)則    14

2.2.3 讓我們拿漸近性問題

練練吧     16

2.2.4 三種重要情況    19

2.2.5 實(shí)證式算法評(píng)估         20

2.3  圖與樹的實(shí)現(xiàn)        24

2.3.1 鄰接列表及其類似結(jié)構(gòu)    26

2.3.2 鄰接矩陣    29

2.3.3 樹的實(shí)現(xiàn)    32

2.3.4 多種表示法         35

2.4  請(qǐng)?zhí)岱篮诤凶?nbsp;       36

2.4.1 隱性平方級(jí)操作         37

2.4.2 浮點(diǎn)運(yùn)算的麻煩         38

2.5  本章小結(jié)        41

2.6  如果您感興趣        42

2.7  練習(xí)題   42

2.8  參考資料        43

第3章  計(jì)數(shù)初步 46

3.1  求和式的含義        46

3.1.1 更多希臘字母    47

3.1.2 求和式的運(yùn)用    47

3.2  兩種賽制的故事   48

3.2.1 握手問題    48

3.2.2 龜兔賽跑    50

3.3  子集與排列組合   54

3.4  遞歸與遞歸式        56

3.4.1 手動(dòng)推導(dǎo)    57

3.4.2 幾個(gè)重要例子    59

3.4.3 猜測(cè)與檢驗(yàn)         62

3.4.4 主定理：一刀切式的

解決方案         65

3.5  這一切究竟是什么呢   67

3.6  本章小結(jié)        69

3.7  如果您感興趣        69

3.8  練習(xí)題   70

3.9  參考資料        71

第4章  歸納、遞歸及歸簡(jiǎn) 72

4.1  哦，這其實(shí)很簡(jiǎn)單        73

4.2  一而再，再而三   74

4.3  魔鏡，魔鏡   77

4.4  基于歸納法（與遞歸法）的設(shè)計(jì)        82

4.4.1 尋找最大排列    82

4.4.2 明星問題    86

4.4.3 拓?fù)渑判騿栴}    88

4.5  更強(qiáng)的假設(shè)條件   92

4.6  不變式與正確性   94

4.7  松弛法與逐步完善        94

4.8  歸簡(jiǎn)法 換位法=困難度證明        95

4.9  一些解決問題的建議   97

4.10 本章小結(jié)      98

4.11 如果您感興趣      98

4.12 練習(xí)題 99

4.13 參考資料      101

第5章  遍歷：算法學(xué)中的萬(wàn)能鑰匙 102

5.1  公園漫步        109

5.1.1 不允許出現(xiàn)環(huán)路         109

5.1.2 停止循環(huán)遍歷的方式         110

5.2  繼續(xù)深入        111

5.3  無(wú)限迷宮與最短（不加權(quán)）

路徑問題         115

5.4  強(qiáng)連通分量   120

5.5  本章小結(jié)        123

5.6  如果您感興趣        123

5.7  練習(xí)題   124

5.8  參考資料        125

第6章  分解、合并、解決 126

6.1  樹狀問題，即平衡問題        126

6.2  經(jīng)典分治算法        129

6.3  折半搜索        129

6.3.1 搜索樹的遍歷及其剪枝    132

6.3.2 選取算法    135

6.4  折半排序        137

排序操作究竟可以有多快     140

6.5  三個(gè)額外實(shí)例        140

6.5.1 最近點(diǎn)對(duì)問題    141

6.5.2 凸包問題    142

6.5.3 最大切片問題    144

6.6  樹的平衡與再平衡        145

6.7  本章小結(jié)        151

6.8  如果您感興趣        152

6.9  練習(xí)題   152

6.10 參考資料      153

第7章  貪心有理嗎？請(qǐng)證明     154

7.1  步步為營(yíng)，萬(wàn)無(wú)一失   154

7.2  背包問題        158

7.2.1 分?jǐn)?shù)背包問題    158

7.2.2 整數(shù)背包問題    159

7.3  哈夫曼算法   159

7.3.1 具體算法    160

7.3.2 首次貪心選擇    162

7.3.3 走完剩余部分    163

7.3.4 最優(yōu)化歸并         164

7.4  最小生成樹問題   165

7.4.1 最短邊問題         166

7.4.2 其余部分的相關(guān)情況         167

7.4.3 Kruskal算法        168

7.4.4 Prim算法    170

7.5  貪心不是問題，問題是

何時(shí)貪心         173

7.5.1 堅(jiān)持做到最好    173

7.5.2 盡量做到完美    174

7.5.3 做好安全措施    175

7.6  本章小結(jié)        177

7.7  如果您感興趣        178

7.8  練習(xí)題   178

7.9  參考資料        179

第8章  復(fù)雜依賴及其記憶體化 180

8.1  不要重復(fù)自己        181

8.2  有向無(wú)環(huán)圖中的最短路徑問題   187

8.3  最長(zhǎng)遞增子序列問題   190

8.4  序列比對(duì)問題        193

8.5  背包問題的反擊   196

8.6  序列的二元分割   199

8.7  本章小結(jié)        202

8.8  如果您感興趣        203

8.9  練習(xí)題   203

8.10 參考資料      204

第9章  Dijkstra及其朋友們

從A到B的旅程     206

9.1  擴(kuò)展知識(shí)        207

9.2  松弛可“瘋狂”   208

9.3  找到隱藏的DAG圖       213

9.4  多對(duì)多問題   216

9.5 “牽強(qiáng)”的子問題 218

9.6  中途相遇        220

9.7  把握未來(lái)走向        223

9.8  本章小結(jié)        226

9.9  如果您感興趣        227

9.10 練習(xí)題 228

9.11 參考資料      228

第10章  匹配、切割及流量       229

10.1 二分圖匹配 230

10.2 不相交的路徑      233

10.3 最大流問題 236

10.4 最小切割集問題 240

10.5 最小成本的流及賦值問題 241

10.6 一些應(yīng)用      243

10.7 本章小結(jié)      247

10.8 如果您感興趣      247

10.9 練習(xí)題 248

10.10 參考資料   249

第11章  困難問題及其（有限）稀釋       250

11.1 重提歸簡(jiǎn)      251

11.2 不待在肯薩斯州了      254

11.3 但目前，我們還是得回

到肯薩斯州     255

11.4 我們應(yīng)從何處開始？

前往何處呢     259

11.5 怪物樂園      264

11.5.1 背包的返回       264

11.5.2 分團(tuán)與著色       266

11.5.3 路徑與環(huán)路       269

11.6 當(dāng)困難來(lái)臨的時(shí)候，聰明人

就開始犯錯(cuò)     272

11.7 盡力尋找解決方案      275

11.8 這些故事告訴我們      277

11.9 本章小結(jié)      279

11.10 如果您感興趣   279

11.11 練習(xí)題        280

11.12 參考資料   281

附錄A  猛踩油門！令Python加速     282

附錄B  一些著名問題與算法      286

問題部分         286

算法與數(shù)據(jù)結(jié)構(gòu)部分     289

附錄C  圖論基礎(chǔ) 295

附錄D  習(xí)題提示 301

第1章     301

第2章     301

第3章     303

第4章     304

第5章     307

第6章     308

第7章     310

第8章     312

第9章     313

第10章   314

第11章   315