電腦演算法基礎 第2版

沈孝鈞，美國密蘇裏大學榮休教授。他本科畢業於清華大學，後來留學美國，就讀於伊利諾大學香檳分校，師從著名電腦科學家C.L.Liu教授。獲得博士後，受聘於密蘇裏大學堪薩斯分校計算機系直至退休。在30餘年的教學和研究工作中，他主要教授電腦演算法和離散數學。他研究的領域包括離散數學、幾何演算法、平行處理、電腦網絡中的調度演算法等。除了會議文章外，他還有數十篇論文發表在國際著名期刊上，包括SIAM Journal on Computing、Discrete Mathematics、Discrete Applied Mathematics、IEEE Journal on Selected Areas in Communications、IEEE Transactions on Networking等。

目　　錄
前言
教學建議
第1章　概論　1
1.1　演算法與資料結構及程式的關係　1
1.1.1　什麼是演算法　1
1.1.2　演算法與資料結構的關係　1
1.1.3　演算法與程式的關係　2
1.1.4　選擇排序的範例　2
1.1.5　演算法的偽碼表示　2
1.2　演算法複雜度分析　 3
1.2.1　演算法複雜度的度量　3
1.2.2　演算法複雜度與輸入資料規模的關係　4
1.2.3　輸入資料規模的度量模型　4
1.2.4　演算法複雜度分析中的兩個簡化假設　5
1.2.5　最好情況、最壞情況和平均情況的複雜度分析　5
1.3　函數成長漸近性態的比較　6
1.3.1　三種比較關係及O、、記號　6
1.3.2　表示演算法複雜度的常用函數　7
1.4　問題複雜度與演算法複雜度的關係　9
1.4.1　問題複雜度是演算法複雜度的下界　9
1.4.2　問題複雜度與最佳演算法　9
1.4.3　易處理問題和難處理問題　9
習題　 10
第2章　分治法　11
2.1　分治法原理　11
2.1.1　二元搜尋的例子　11
2.1.2　表示複雜度的遞推關係　12
2.2　遞推關係式求解　13
2.2.1　替換法　13
2.2.2　序列求和法與遞歸樹法　15
2.2.3　常用序列和公式　16
2.2.4　主方法求解　18
2.3　範例示範　19
習題　 20
第3章　基於比較的排序演算法　24
3.1　插入排序　　24
3.1.1　插入排序的演算法 24
3.1.2　插入排序演算法的複雜度分析　25
3.1.3　插入排序的優缺點　26
3.2　合併排序　26
3.2.1　合併演算法及其複雜度　26
3.2.2　合併排序的演算法及其複雜度　27
3.2.3　合併排序的優缺點　29
3.3　堆排序　 30
3.3.1　堆的資料結構　30
3.3.2　堆的修復演算法及其複雜度　31
3.3.3　為輸入資料建堆　32
3.3.4　堆排序演算法　33
3.3.5　堆排序演算法的複雜度　34
3.3.6　堆排序演算法的優缺點　35
3.3.7　堆用作優先隊列　35
3.4　快排序　36
3.4.1　快排序演算法　36
3.4.2　快排序演算法最壞情況複雜度　39
3.4.3　快排序演算法平均狀況複雜度　40
3.4.4　快排序演算法最好情況複雜度　41
3.4.5　快排序演算法的優缺點　42
習題　 42
第4章　不基於比較的排序演算法　46
4.1　比較排序的下界　46
4.1.1　決策樹模型及排序最壞情況下界　46
4.1.2　二元樹的外路徑總長與排序平均情況下界　 49
4.1.3　二元樹的全路徑總長與堆排序最好情況下界　 51
4.2　不基於比較的線性時間排序演算法　54
4.2.1　計數排序　 54
4.2.2　基數排序　57
4.2.3　桶排序　58
習題　60
第5章　中位數和任一順序數的選擇　63
5.1　問題定義　63
5.2　最大數與最小數的選擇　63
5.2.1　最大與最小順序數的選擇演算法及其複雜度　64
5.2.2　同時找出最大數與最小數的演算法　65
5.3　線性時間求任一順序數的演算法　66
5.3.1　最壞情況複雜度為O(n)的演算法 66
5.3.2　平均情況複雜度為O(n)的演算法　 68
5.4　求k個最大順序數的演算法　69
5.4.1　一個理論連結實際的問題　69
5.4.2　利用堆疊來找k個最大順序數的演算法　 70
5.4.3　利用錦標賽樹來找k個最大順序數的演算法　70
習題　 71
第6章　動態規劃　 73
6.1　動態規劃的基本原理　73
6.2　矩陣連乘問題　 75
6.2.1　定義子問題　75
6.2.2　歸納公式　77
6.2.3　演算法偽碼與範例　78
6.3　最長公共子序列問題　81
6.3.1　定義子問題　81
6.3.2　歸納公式　82
6.3.3　演算法偽碼與範例　82
6.4　最佳二元搜尋樹問題　84
6.4.1　定義子問題和歸納公式　85
6.4.2　演算法偽碼與範例　87
6.5　多級圖及其應用　 89
6.6　最長遞增子序列問題　92
6.6.1　定義子問題　93
6.6.2　歸納公式　93
6.6.3　演算法偽碼與範例　93
習題　 95
第7章　貪心演算法　 103
7.1　最佳郵局設定問題　103
7.2　一個簡單的最佳活動安排問題　105
7.3　其他最佳活動安排問題　106
7.3.1　兩個大禮堂的最佳活動安排問題　106
7.3.2　等長時間的活動的最佳安排問題　109
7.4　哈夫曼編碼問題　112
7.4.1　前綴碼　112
7.4.2　最佳前綴碼－哈夫曼編碼　114
7.5　最佳加油計畫問題　118
7.5.1　最佳加油計畫問題的描述　118
7.5.2　貪心演算法的基本思路　119
7.5.3　貪心演算法的偽碼　120
習題　 121
第8章　圖的周遊演算法　 128
8.1　圖的表示　128
8.1.1　鄰接表　129
8.1.2　鄰接矩陣 129
8.2　廣度優先搜尋及應用程式　130
8.2.1　廣度優先搜尋策略　130
8.2.2　廣度優先搜尋演算法及距離樹　131
8.2.3　無向圖的二著色問題　133
8.3　深度優先搜尋及應用　136