前言
教學建議
第1章 概述 1
1.1 算法與數據結構及程序的關係 1
1.1.1 什麼是算法 1
1.1.2 算法與數據結構的關係 1
1.1.3 算法與程序的關係 1
1.1.4 選擇排序的例子 2
1.1.5 算法的僞碼錶示 2
1.2 算法復雜度分析 3
1.2.1 算法復雜度的度量 3
1.2.2 算法復雜度與輸入數據規模的關係 3
1.2.3 輸入數據規模的度量模型 4
1.2.4 算法復雜度分析中的兩個簡化假設 4
1.2.5 最好情況、最壞情況和平均情況的復雜度分析 5
1.3 函數增長漸近性態的比較 6
1.3.1 三種比較關係及O、Ω、Θ記號 6
1.3.2 錶示算法復雜度的常用函數 6
1.4 算法復雜度與問題復雜度的關係 8
1.4.1 問題復雜度是算法復雜度的下界 8
1.4.2 問題復雜度與最佳算法 8
1.4.3 易處理問題和難處理問題 8
習題 9
第2章 分治法 10
2.1 分治法原理 10
2.1.1 二元搜索的例子 10
2.1.2 錶示復雜度的遞推關係 11
2.2 遞推關係求解 11
2.2.1 替換法 12
2.2.2 序列求和法和遞歸樹法 13
2.2.3 常用序列和公式 14
2.2.4 主方法求解 16
習題 16
第3章 基於比較的排序算法 19
3.1 插入排序 19
3.1.1 插入排序的算法 19
3.1.2 插入排序算法的復雜度分析 20
3.1.3 插入排序的優缺點 20
3.2 閤並排序 21
3.2.1 閤並算法及其復雜度 21
3.2.2 閤並排序的算法及其復雜度 22
3.2.3 閤並排序的優缺點 24
3.3 堆排序 24
3.3.1 堆的數據結構 24
3.3.2 堆的修復算法及其復雜度 25
3.3.3 為輸入數據建堆 27
3.3.4 堆排序算法 28
3.3.5 堆排序算法的復雜度 29
3.3.6 堆排序算法的優缺點 29
3.3.7 堆用作優先隊列 30
3.4 快排序 31
3.4.1 快排序算法 31
3.4.2 快排序算法最壞情況復雜度 33
3.4.3 快排序算法平均情況復雜度 34
3.4.4 快排序算法最好情況復雜度 34
3.4.5 快排序算法優缺點 36
習題 36
第4章 不基於比較的排序算法 39
4.1 比較排序的下界 39
4.1.1 決策樹模型及最壞情況下界 39
*4.1.2 二叉樹的外路徑總長與平均情況下界 41
*4.1.3 二叉樹的全路徑總長及堆排序最好情況下界 43
4.2 不基於比較的綫性時間排序算法 46
4.2.1 計數排序 46
4.2.2 基數排序 48
4.2.3 桶排序 49
習題 51
第5章 中位數和任一順序數的選擇 53
5.1 問題定義 53
5.2 最大數和最小數的選擇 53
5.2.1 最大和最小順序數的選擇算法及其復雜度 53
5.2.2 同時找齣最大數和最小數的算法 54
5.3 綫性時間找齣任一順序數的算法 55
5.3.1 最壞情況復雜度為O (n)的算法 56
5.3.2 平均情況復雜度為O (n)的算法 58
5.4 找齣k個最大順序數的算法 58
5.4.1 一個理論聯係實際的問題 58
5.4.2 利用堆來找k個最大的順序數的算法 59
5.4.3 利用錦標賽樹來找k個最大順序數的算法 59
習題 60
第6章 動態規劃 62
6.1 動態規劃的基本原理 62
6.2 矩陣連乘問題 63
6.3 最長公共子序列問題 68
*6.4 最佳二元搜索樹 71
6.5 多級圖及其應用 76
6.6 最長遞增子序列問題 78
習題 80
第7章 貪心算法 86
7.1 最佳郵局設置問題 86
7.2 最佳活動安排問題 87
7.3 哈夫曼編碼問題 89
7.3.1 前綴碼 89
7.3.2 最佳前綴碼——哈夫曼編碼 90
7.4 最佳加油計劃問題 94
習題 96
第8章 圖的周遊算法 100
8.1 圖的錶示 100
8.1.1 鄰接錶 100
8.1.2 鄰接矩陣 101
8.2 廣度優先搜索及應用 101
8.2.1 廣度優先搜索策略 101
8.2.2 廣度優先搜索算法及距離樹 102
8.2.3 無嚮圖的二著色問題 105
8.3 深度優先搜索及應用 107
8.3.1 深度優先搜索策略 107
8.3.2 深度優先搜索算法和深度優先樹 107
8.3.3 深度優先搜索算法舉例和圖中邊的分類 110
8.3.4 拓撲排序 112
8.3.5 無迴路有嚮圖中最長路徑問題及應用 114
8.3.6 有嚮圖的強連通分支的分解 116
8.3.7 無嚮圖的雙連通分支的分解 119
習題 124
第9章 圖的最小支撐樹 128
9.1 計算最小支撐樹的一個通用的貪心算法策略 129
9.2 Kruskal算法 130
9.3 Prim算法 133
習題 137
第10章 單源最短路徑 140
10.1 Dijkstra算法 140
10.2 Bellman-Ford算法 144
習題 148
第11章 網絡流 150
11.1 網絡模型和最大網絡流問題 150
11.2 網絡中流與割的關係 152
11.2.1 網絡中的割及其容量 153
11.2.2 剩餘網絡和增廣路徑 154
11.2.3 最大流最小割定理 156
11.3 Ford-Fulkerson 方法 157
11.3.1 Ford-Fulkerson 的通用方法 157
11.3.2 Edmonds-Karp算法 159
11.3.3 Dinic算法 161
11.3.4 0-1網絡的最大流問題 164
11.4 二部圖的匹配問題 165
11.4.1 用網絡流求二部圖的最大匹配算法 166
11.4.2 Philip-Hall婚配定理 167
11.4.3 Birkhoff-von Neuman定理 169
11.5 推進-重標號算法簡介 170
11.5.1 預流和高度函數 170
11.5.2 在剩餘圖中對頂點的兩個操作 171
11.5.3 推進-重標號算法的初始化 172
11.5.4 推進-重標號的通用算法 172
習題 174
第12章 計算幾何基礎 177
12.1 平麵綫段及相互關係 177
12.1.1 嚮量的點積和叉積 177
12.1.2 平麵綫段的相互關係 178
12.2 平掃綫技術和綫段相交的確定 181
12.2.1 平掃綫的狀態 182
12.2.2 用平掃綫確定綫段相交的算法 182
12.3 平麵點集的凸包 185
12.3.1 Graham掃描法 186
12.3.2 Jarvis 行進法 190
12.4 最近點對問題 192
習題 195
第13章 字符串匹配 197
13.1 一個樸素的字符串匹配算法 197
13.2 Rabin-Karp算法 198
13.3 基於有限狀態自動機的匹配算法 199
13.3.1 有限狀態自動機簡介 199
13.3.2 字符串匹配自動機 200
13.3.3 基於有限狀態自動機的串匹配算法 202
13.4 Knuth-Morris-Pratt（KMP）算法 203
13.4.1 模式的前綴函數 203
13.4.2 KMP算法的僞碼 205
習題 207
第14章 NP完全問題 208
14.1 預備知識 209
14.1.1 圖靈機 209
14.1.2 符號集和編碼對計算復雜度的影響 210
14.1.3 判斷型問題和優化型問題及其關係 210
14.1.4 判斷型問題的形式語言錶示 211
14.1.5 多項式關聯和多項式歸約 212
14.2 P和NP語言類 214
14.2.1 非確定圖靈機和NP語言類 214
14.2.2 多項式檢驗算法和NP類語言 215
14.3 NP完全語言類和NP完全問題 216
14.3.1 第一個NPC問題 217
14.3.2 若乾著名NPC問題的證明 220
習題 231
第15章 近似算法 236
15.1 近似算法的性能評價 236
15.2 頂點覆蓋問題 237
15.3 貨郎擔問題 238
15.3.1 滿足三角不等式關係的貨郎擔問題 238
15.3.2 無三角不等式關係的一般貨郎擔問題 241
15.4 集閤覆蓋問題 242
15.5 MAX-3-SAT問題 244
15.6 加權的頂點覆蓋問題 245
15.7 子集和問題 247
15.7.1 一個保證最優解的指數型算法 247
15.7.2 子集和問題的一個完全多項式近似機製 248
*15.8 鴻溝定理和不可近似性 251
15.8.1 鴻溝定理 251
15.8.2 任務均勻分配問題 252
習題 254
第16章 窮舉搜索 257
16.1 搜索問題及方法的描述 257
16.2 迴溯法 259
16.2.1 迴溯法的通用算法 259
16.2.2 n皇後問題 259
16.2.3 子集和問題 260
16.2.4 迴溯法的效率估計 262
16.3 分支限界法 263
16.3.1 分支限界法解n皇後問題 264
16.3.2 0/1背包問題 266
16.4 博弈樹和α-β剪枝 271
16.4.1 博弈樹及其評估的方法 271
16.4.2 α-β剪枝法 275
習題 276
附錄 紅黑樹 278
參考文獻 289
· · · · · · (收起)