算法導(dǎo)論(原書(shū)第3版) 內(nèi)容簡(jiǎn)介：

在有關(guān)算法的書(shū)中，有一些敘述非常嚴(yán)謹(jǐn)，但不夠全面；另一些涉及了大量的題材，但又缺乏嚴(yán)謹(jǐn)性。本書(shū)將嚴(yán)謹(jǐn)性和全面性融為一體，深入討論各類算法，并著力使這些算法的設(shè)計(jì)和分析能為各個(gè)層次的讀者接受。全書(shū)各章自成體系，可以作為獨(dú)立的學(xué)習(xí)單元；算法以英語(yǔ)和偽代碼的形式描述，具備初步程序設(shè)計(jì)經(jīng)驗(yàn)的人就能看懂；說(shuō)明和解釋力求淺顯易懂，不失深度和數(shù)學(xué)嚴(yán)謹(jǐn)性。

《算法導(dǎo)論(原書(shū)第3版)》選材經(jīng)典、內(nèi)容豐富、結(jié)構(gòu)合理、邏輯清晰，對(duì)本科生的數(shù)據(jù)結(jié)構(gòu)課程和研究生的算法課程都是非常實(shí)用的教材，在it專業(yè)人員的職業(yè)生涯中，本書(shū)也是一本案頭必備的參考書(shū)或工程實(shí)踐手冊(cè)。

第3版的主要變化：
新增了van emde boas樹(shù)和多線程算法，并且將矩陣基礎(chǔ)移至附錄。
修訂了遞歸式（現(xiàn)在稱為“分治策略”）那一章的內(nèi)容，更廣泛地覆蓋分治法。
移除兩章很少講授的內(nèi)容：二項(xiàng)堆和排序網(wǎng)絡(luò)。
修訂了動(dòng)態(tài)規(guī)劃和貪心算法相關(guān)內(nèi)容。
流網(wǎng)絡(luò)相關(guān)材料現(xiàn)在基于邊上的全部流。
由于關(guān)于矩陣基礎(chǔ)和strassen算法的材料移到了其他章，矩陣運(yùn)算這一章的內(nèi)容所占篇幅更小。
修改了對(duì)knuth-morris-pratt字符串匹配算法的討論。
新增100道練習(xí)和28道思考題，還更新并補(bǔ)充了參考文獻(xiàn)。

算法導(dǎo)論(原書(shū)第3版)  目錄：
第一部分　基礎(chǔ)知識(shí)
第1章　算法在計(jì)算中的作用3
1.1　算法3
1.2　作為一種技術(shù)的算法6
思考題8 本章注記8
第2章　算法基礎(chǔ)9
2.1　插入排序9
2.2　分析算法13
2.3　設(shè)計(jì)算法16
2.3.1　分治法16
2.3.2　分析分治算法20
思考題22
本章注記24
第3章　函數(shù)的增長(zhǎng)25
3.1　漸近記號(hào)25
3.2　標(biāo)準(zhǔn)記號(hào)與常用函數(shù)30
思考題35 本章注記36
第4章　分治策略37
4.1　最大子數(shù)組問(wèn)題38
4.2　矩陣乘法的strassen算法43
4.3　用代入法求解遞歸式47
4.4　用遞歸樹(shù)方法求解遞歸式50
4.5　用主方法求解遞歸式53
4.6　證明主定理55
4.6.1　對(duì)b的冪證明主定理56
4.6.2　向下取整和向上取整58
思考題60
本章注記62
第5章　概率分析和隨機(jī)算法65
5.1　雇用問(wèn)題65
5.2　指示器隨機(jī)變量67
5.3　隨機(jī)算法69
?5.4　概率分析和指示器隨機(jī)變量的進(jìn)一步使用73
5.4.1　生日悖論73
5.4.2　球與箱子75
5.4.3　特征序列76
5.4.4　在線雇用問(wèn)題78
思考題79
本章注記80
第二部分　排序和順序統(tǒng)計(jì)量
第6章　堆排序84
6.1　堆84
6.2　維護(hù)堆的性質(zhì)85
6.3　建堆87
6.4　堆排序算法89
6.5　優(yōu)先隊(duì)列90
思考題93
本章注記94
第7章　快速排序95
7.1　快速排序的描述95
7.2　快速排序的性能97
7.3　快速排序的隨機(jī)化版本100
7.4　快速排序分析101
7.4.1　最壞情況分析101
7.4.2　期望運(yùn)行時(shí)間101
思考題103
本章注記106
第8章　線性時(shí)間排序107
8.1　排序算法的下界107
8.2　計(jì)數(shù)排序108
8.3　基數(shù)排序110
8.4　桶排序112
思考題114
本章注記118
第9章　中位數(shù)和順序統(tǒng)計(jì)量119
9.1　最小值和最大值119
9.2　期望為線性時(shí)間的選擇算法120
9.3　最壞情況為線性時(shí)間的選擇算法123
思考題125
本章注記126
第三部分　數(shù)據(jù)結(jié)構(gòu)
第10章　基本數(shù)據(jù)結(jié)構(gòu)129
10.1　棧和隊(duì)列129
10.2　鏈表131
10.3　指針和對(duì)象的實(shí)現(xiàn)134
10.4　有根樹(shù)的表示137
思考題139
本章注記141
第11章　散列表142
11.1　直接尋址表142
11.2　散列表143
11.3　散列函數(shù)147
11.3.1　除法散列法147
11.3.2　乘法散列法148
11.3.3　全域散列法148
11.4　開(kāi)放尋址法151
11.5　完全散列156
思考題158
本章注記160
第12章　二叉搜索樹(shù)161
12.1　什么是二叉搜索樹(shù)161
12.2　查詢二叉搜索樹(shù)163
12.3　插入和刪除165
12.4　隨機(jī)構(gòu)建二叉搜索樹(shù)169
思考題171
本章注記173
第13章　紅黑樹(shù)174
13.1　紅黑樹(shù)的性質(zhì)174
13.2　旋轉(zhuǎn)176
13.3　插入178
13.4　刪除183
思考題187
本章注記191
第14章　數(shù)據(jù)結(jié)構(gòu)的擴(kuò)張193
14.1　動(dòng)態(tài)順序統(tǒng)計(jì)193
14.2　如何擴(kuò)張數(shù)據(jù)結(jié)構(gòu)196
14.3　區(qū)間樹(shù)198
思考題202
本章注記202
第四部分　高級(jí)設(shè)計(jì)和分析技術(shù)
第15章　動(dòng)態(tài)規(guī)劃204
15.1　鋼條切割204
15.2　矩陣鏈乘法210
15.3　動(dòng)態(tài)規(guī)劃原理215
15.4　最長(zhǎng)公共子序列222
15.5　最優(yōu)二叉搜索樹(shù)226
思考題231 本章注記236
第16章　貪心算法237
16.1　活動(dòng)選擇問(wèn)題237
16.2　貪心算法原理242
16.3　赫夫曼編碼245
16.4　擬陣和貪心算法250
16.5　用擬陣求解任務(wù)調(diào)度問(wèn)題253
思考題255
本章注記257
第17章　攤還分析258
17.1　聚合分析258
17.2　核算法261
17.3　勢(shì)能法262
17.4　動(dòng)態(tài)表264
17.4.1　表擴(kuò)張265
17.4.2　表擴(kuò)張和收縮267
思考題270
本章注記273
第五部分　高級(jí)數(shù)據(jù)結(jié)構(gòu)
第18章　b樹(shù)277
18.1　b樹(shù)的定義279
18.2　b樹(shù)上的基本操作281
18.3　從b樹(shù)中刪除關(guān)鍵字286
思考題288 本章注記289
第19章　斐波那契堆290
19.1　斐波那契堆結(jié)構(gòu)291
19.2　可合并堆操作292
19.3　關(guān)鍵字減值和刪除一個(gè)結(jié)點(diǎn)298
19.4　最大度數(shù)的界300
思考題302
本章注記305
第20章　van emde boas樹(shù)306
20.1　基本方法306
20.2　遞歸結(jié)構(gòu)308
20.2.1　原型van emde boas結(jié)構(gòu)310
20.2.2　原型van emde boas結(jié)構(gòu)上的操作311
20.3　van emde boas樹(shù)及其操作314
20.3.1　van emde boas樹(shù)315
20.3.2　van emde boas樹(shù)的操作317
思考題322
本章注記323
第21章　用于不相交集合的數(shù)據(jù)結(jié)構(gòu)324
21.1　不相交集合的操作324
21.2　不相交集合的鏈表表示326
21.3　不相交集合森林328
*21.4　帶路徑壓縮的按秩合并的分析331
思考題336
本章注記337
第六部分　圖算法
第22章　基本的圖算法341
22.1　圖的表示341
22.2　廣度優(yōu)先搜索343
22.3　深度優(yōu)先搜索349
22.4　拓?fù)渑判?55
22.5　強(qiáng)連通分量357
思考題360
本章注記361
第23章　最小生成樹(shù)362
23.1　最小生成樹(shù)的形成362
23.2　kruskal算法和prim算法366
思考題370 本章注記373
第24章　單源最短路徑374
24.1　bellman?ford算法379
24.2　有向無(wú)環(huán)圖中的單源最短路徑問(wèn)題381
24.3　dijkstra算法383
24.4　差分約束和最短路徑387
24.5　最短路徑性質(zhì)的證明391
思考題395
本章注記398
第25章　所有結(jié)點(diǎn)對(duì)的最短路徑問(wèn)題399
25.1　最短路徑和矩陣乘法400
25.2　floyd?warshall算法404
25.3　用于稀疏圖的johnson算法409
思考題412 本章注記412
第26章　最大流414
26.1　流網(wǎng)絡(luò)414
26.2　ford?fulkerson方法418
26.3　最大二分匹配428
26.4　推送重貼標(biāo)簽算法431
26.5　前置重貼標(biāo)簽算法438
思考題446
本章注記449
第七部分　算法問(wèn)題選編
第27章　多線程算法453
27.1　動(dòng)態(tài)多線程基礎(chǔ)454
27.2　多線程矩陣乘法465
27.3　多線程歸并排序468
思考題472
本章注記476
第28章　矩陣運(yùn)算478
28.1　求解線性方程組478
28.2　矩陣求逆486
28.3　對(duì)稱正定矩陣和最小二乘逼近489
思考題493
本章注記494
第29章　線性規(guī)劃495
29.1　標(biāo)準(zhǔn)型和松弛型499
29.2　將問(wèn)題表達(dá)為線性規(guī)劃504
29.3　單純形算法507
29.4　對(duì)偶性516
29.5　初始基本可行解520
思考題525
本章注記526
第30章　多項(xiàng)式與快速傅里葉變換527
30.1　多項(xiàng)式的表示528
30.2　dft與fft531
30.3　高效fft實(shí)現(xiàn)536
思考題539
本章注記541
第31章　數(shù)論算法543
31.1　基礎(chǔ)數(shù)論概念543
31.2　最大公約數(shù)547
31.3　模運(yùn)算550
31.4　求解模線性方程554
31.5　中國(guó)余數(shù)定理556
31.6　元素的冪558
31.7　rsa公鑰加密系統(tǒng)561
31.8　素?cái)?shù)的測(cè)試565
31.9　整數(shù)的因子分解571
思考題574 本章注記576
第32章　字符串匹配577
32.1　樸素字符串匹配算法578
32.2　rabin?karp算法580
32.3　利用有限自動(dòng)機(jī)進(jìn)行字符串匹配583
32.4　knuth?morris?pratt算法588
思考題594
本章注記594
第33章　計(jì)算幾何學(xué)595
33.1　線段的性質(zhì)595
33.2　確定任意一對(duì)線段是否相交599
33.3　尋找凸包604
33.4　尋找最近點(diǎn)對(duì)610
思考題613
本章注記615
第34章　np完全性616
34.1　多項(xiàng)式時(shí)間619
34.2　多項(xiàng)式時(shí)間的驗(yàn)證623
34.3　np完全性與可歸約性626
34.4　np完全性的證明633
34.5　np完全問(wèn)題638
34.5.1　團(tuán)問(wèn)題638
34.5.2　頂點(diǎn)覆蓋問(wèn)題640
34.5.3　哈密頓回路問(wèn)題641
34.5.4　旅行商問(wèn)題644
34.5.5　子集和問(wèn)題645
思考題647
本章注記649
第35章　近似算法651
35.1　頂點(diǎn)覆蓋問(wèn)題652
35.2　旅行商問(wèn)題654
35.2.1　滿足三角不等式的旅行商問(wèn)題654
35.2.2　一般旅行商問(wèn)題656
35.3　集合覆蓋問(wèn)題658
35.4　隨機(jī)化和線性規(guī)劃661
35.5　子集和問(wèn)題663
思考題667
本章注記669
第八部分　附錄：數(shù)學(xué)基礎(chǔ)知識(shí)
附錄a　求和672
a.1　求和公式及其性質(zhì)672
a.2　確定求和時(shí)間的界674
思考題678 附錄注記678
附錄b　集合等離散數(shù)學(xué)內(nèi)容679
b.1　集合679
b.2　關(guān)系682
b.3　函數(shù)683
b.4　圖685
b.5　樹(shù)687
b.5.1　自由樹(shù)688
b.5.2　有根樹(shù)和有序樹(shù)689
b.5.3　二叉樹(shù)和位置樹(shù)690
思考題691
附錄注記692
附錄c　計(jì)數(shù)與概率693
c.1　計(jì)數(shù)693
c.2　概率696
c.3　離散隨機(jī)變量700
c.4　幾何分布與二項(xiàng)分布702
*c.5　二項(xiàng)分布的尾部705
思考題708
附錄注記708
附錄d　矩陣709
d.1　矩陣與矩陣運(yùn)算709
d.2　矩陣基本性質(zhì)712
思考題714
附錄注記715
參考文獻(xiàn)716