算法設(shè)計與分析

第1章 算法的基本概念
1.1 算法的定義和特征 1
1.2 算法復(fù)雜性分析 3
1.3 漸進記號 5
1.4 最好情況、最壞情況和平均情況分析 10
1.5 遞歸算法分析 14
習(xí)題 20

第2章 排序及并查集算法
2.1 冒泡排序 24
2.2 選擇排序 25
2.3 合并排序 26
2.3.1 merge算法 26
2.3.2 合并排序算法的具體內(nèi)容 27
2.3.3 合并排序算法分析 30
2.4 堆及堆排序 30
2.4.1 堆的概念及性質(zhì) 31
2.4.2 堆的操作 32
2.4.3 堆排序 39
2.4.4 堆排序的應(yīng)用 40
2.5 桶排序 41
2.5.1 桶排序的基本步驟 41
2.5.2 桶排序的時間復(fù)雜度 43
2.6 基數(shù)排序 44
2.6.1 基數(shù)排序的基本思想 44
2.6.2 基數(shù)排序算法的實現(xiàn) 45
2.6.3 基數(shù)排序算法的合理性證明 47
2.6.4 基數(shù)排序的復(fù)雜度分析 47
2.6.5 基數(shù)排序的應(yīng)用 48
2.7 并查集算法 48
習(xí)題 52

第3章 遞歸與分治
3.1 遞歸算法 54
3.1.1 遞歸算法的基本思想 55
3.1.2 遞歸算法實例 55
3.2 分治法 60
3.2.1 分治法的基本思想 60
3.2.2 分治法的步驟 63
3.2.3 應(yīng)用分治法進行合并排序 64
3.2.4 快速排序 66
3.2.5 快速排序的改進 70
3.2.6 平面最近點對問題 71
3.2.7 BFPRT算法（TOP-K問題） 81
3.2.8 棋盤覆蓋問題 84
習(xí)題 87

第4章 貪婪法
4.1 貪婪算法 89
4.2 貪婪法的設(shè)計思想 92
4.3 區(qū)間調(diào)度問題 92
4.4 背包問題的貪婪算法 94
4.5 狄斯奎諾(Dijkstra)算法 97
4.5.1 狄斯奎諾算法的核心原理 97
4.5.2 狄斯奎諾算法的步驟描述 99
4.5.3 狄斯奎諾算法的實現(xiàn) 101
4.5.4 狄斯奎諾算法的不足 105
4.6 數(shù)列極差問題 106
4.6.1 問題分析 106
4.6.2 極差問題的算法設(shè)計 107
4.6.3 極差問題的時間和空間復(fù)雜度分析 108
4.7 分數(shù)轉(zhuǎn)化問題 108
4.8 被3整除的元素最大和問題 110
4.9 跳躍游戲問題 111
習(xí)題 114

第5章 動態(tài)規(guī)劃
5.1 動態(tài)規(guī)劃基本概述 116
5.1.1 動態(tài)規(guī)劃的基本術(shù)語 118
5.1.2 動態(tài)規(guī)劃數(shù)學(xué)模型建立的一般步驟 121
5.2 動態(tài)規(guī)劃的基本性質(zhì) 123
5.3 貨郎擔問題 124
5.4 多段圖最短路徑問題 127
5.4.1 多段圖的計算過程 128
5.4.2 多段圖的動態(tài)規(guī)劃算法實現(xiàn) 129
5.5 設(shè)備更新問題 131
5.6 最長公共子序列 134
5.6.1 最長公共子序列的搜索過程 135
5.6.2 最長公共子序列算法實現(xiàn) 137
5.7 0/1背包問題 139
5.7.1 0/1背包問題求解分析 140
5.7.2 0/1背包問題的實現(xiàn) 141
5.8 最大連續(xù)子序列和問題 143
5.9 最優(yōu)二叉搜索樹 145
5.9.1 OBST問題的動態(tài)規(guī)劃求解過程 147
5.9.2 OBST問題的實現(xiàn)過程 149
習(xí)題 151

第6章 回溯
6.1 問題的解空間和狀態(tài)空間樹 153
6.2 狀態(tài)空間樹的動態(tài)搜索 154
6.3 回溯算法的一般性描述 157
6.4 圖的著色問題 160
6.4.1 圖著色問題的求解過程分析 161
6.4.2 圖著色問題算法實現(xiàn) 163
6.5 n皇后問題 165
6.5.1 n皇后問題的求解過程分析 165
6.5.2 n皇后問題的求解實現(xiàn) 166
6.5.3 數(shù)獨問題 168
6.6 一些經(jīng)典算法的回溯求解 172
習(xí)題 182

第7章 分支與限界
7.1 分支與限界算法 184
7.2 作業(yè)分配問題 186
7.2.1 分支限界法解作業(yè)分配問題的思想方法 186
7.2.2 分支限界法解作業(yè)分配問題算法的實現(xiàn) 188
7.3 單源最短路徑問題 192
7.3.1 分支限界法解單源最短路徑問題的思想方法 192
7.3.2 分支限界法解單源最短路徑問題算法的實現(xiàn) 194
7.4 0/1背包問題 197
7.4.1 分支限界法解0/1背包問題的思想方法 197
7.4.2 0/1背包問題分支限界算法的實現(xiàn) 200
7.5 貨郎擔問題 204
7.5.1 費用矩陣的特性及歸約 204
7.5.2 分支限界法解最短漢密爾頓回路的思想 205
7.5.3 貨郎擔問題的求解過程 208
7.5.4 幾個輔助函數(shù)的實現(xiàn) 212
7.5.5 貨郎擔問題分支限界算法的實現(xiàn) 217
習(xí)題 219

第8章 隨機算法
8.1 隨機化算法 222
8.1.1 為什么要隨機化 222
8.1.2 隨機算法 222
8.2 隨機數(shù)發(fā)生器 223
8.3 數(shù)值概率算法 225
8.4 拉斯維加斯算法 229
8.4.1 隨機快速排序算法 230
8.4.2 隨機選擇算法 231
8.4.3 n皇后問題的隨機算法 232
8.4.4 隨機字符串匹配算法 234
8.4.5 整數(shù)因子 239
8.5 蒙特卡羅算法 242
8.5.1 函數(shù)極大值估計問題 243
8.5.2 主元素問題 244
8.5.3 素數(shù)測試問題 246
8.6 隨機算法的應(yīng)用 251
習(xí)題 252

第9章 NP完全問題
9.1 判定問題和優(yōu)化問題 254
9.2 P類問題和NP類問題 255
9.3 NP完全問題 260
習(xí)題 262

參考文獻