本書以算法設(shè)計(jì)策略為知識(shí)單元，系統(tǒng)地介紹了算法設(shè)計(jì)與分析的概念和方法。全書內(nèi)容包括算法的基本概念、排序及并查集算法、遞歸與分治策略、貪婪算法、動(dòng)態(tài)規(guī)劃算法、回溯法、分支與限界法、隨機(jī)算法、NP完全問(wèn)題等。本書從一些經(jīng)典問(wèn)題入手，分析如何求解問(wèn)題，然后使用偽代碼對(duì)問(wèn)題的算法進(jìn)行描述，最后對(duì)算法的時(shí)間復(fù)雜度進(jìn)行分析。為了便于讀者學(xué)習(xí)和實(shí)踐，本書采用C語(yǔ)言對(duì)算法進(jìn)行描述，可讀性強(qiáng)。每章內(nèi)容后附有習(xí)題，便于讀者復(fù)習(xí)鞏固。
本書可作為高等院校計(jì)算機(jī)專業(yè)本科生和研究生的教材，也可作為希望進(jìn)行算法學(xué)習(xí)和研究的相關(guān)人員的參考資料。
第1章 算法的基本概念
1.1 算法的定義和特征 1
1.2 算法復(fù)雜性分析 3
1.3 漸進(jìn)記號(hào) 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 桶排序的時(shí)間復(fù)雜度 43
2.6 基數(shù)排序 44
2.6.1 基數(shù)排序的基本思想 44
2.6.2 基數(shù)排序算法的實(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 遞歸算法實(shí)例 55
3.2 分治法 60
3.2.1 分治法的基本思想 60
3.2.2 分治法的步驟 63
3.2.3 應(yīng)用分治法進(jìn)行合并排序 64
3.2.4 快速排序 66
3.2.5 快速排序的改進(jìn) 70
3.2.6 平面最近點(diǎn)對(duì)問(wèn)題 71
3.2.7 BFPRT算法（TOP-K問(wèn)題） 81
3.2.8 棋盤覆蓋問(wèn)題 84
習(xí)題 87
第4章 貪婪法
4.1 貪婪算法 89
4.2 貪婪法的設(shè)計(jì)思想 92
4.3 區(qū)間調(diào)度問(wèn)題 92
4.4 背包問(wèn)題的貪婪算法 94
4.5 狄斯奎諾(Dijkstra)算法 97
4.5.1 狄斯奎諾算法的核心原理 97
4.5.2 狄斯奎諾算法的步驟描述 99
4.5.3 狄斯奎諾算法的實(shí)現(xiàn) 101
4.5.4 狄斯奎諾算法的不足 105
4.6 數(shù)列極差問(wèn)題 106
4.6.1 問(wèn)題分析 106
4.6.2 極差問(wèn)題的算法設(shè)計(jì) 107
4.6.3 極差問(wèn)題的時(shí)間和空間復(fù)雜度分析 108
4.7 分?jǐn)?shù)轉(zhuǎn)化問(wèn)題 108
4.8 被3整除的元素最大和問(wèn)題 110
4.9 跳躍游戲問(wèn)題 111
習(xí)題 114
第5章 動(dòng)態(tài)規(guī)劃
5.1 動(dòng)態(tài)規(guī)劃基本概述 116
5.1.1 動(dòng)態(tài)規(guī)劃的基本術(shù)語(yǔ) 118
5.1.2 動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型建立的一般步驟 121
5.2 動(dòng)態(tài)規(guī)劃的基本性質(zhì) 123
5.3 貨郎擔(dān)問(wèn)題 124
5.4 多段圖最短路徑問(wèn)題 127
5.4.1 多段圖的計(jì)算過(guò)程 128
5.4.2 多段圖的動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn) 129
5.5 設(shè)備更新問(wèn)題 131
5.6 最長(zhǎng)公共子序列 134
5.6.1 最長(zhǎng)公共子序列的搜索過(guò)程 135
5.6.2 最長(zhǎng)公共子序列算法實(shí)現(xiàn) 137
5.7 0/1背包問(wèn)題 139
5.7.1 0/1背包問(wèn)題求解分析 140
5.7.2 0/1背包問(wèn)題的實(shí)現(xiàn) 141
5.8 最大連續(xù)子序列和問(wèn)題 143
5.9 最優(yōu)二叉搜索樹 145
5.9.1 OBST問(wèn)題的動(dòng)態(tài)規(guī)劃求解過(guò)程 147
5.9.2 OBST問(wèn)題的實(shí)現(xiàn)過(guò)程 149
習(xí)題 151
第6章 回溯
6.1 問(wèn)題的解空間和狀態(tài)空間樹 153
6.2 狀態(tài)空間樹的動(dòng)態(tài)搜索 154
6.3 回溯算法的一般性描述 157
6.4 圖的著色問(wèn)題 160
6.4.1 圖著色問(wèn)題的求解過(guò)程分析 161
6.4.2 圖著色問(wèn)題算法實(shí)現(xiàn) 163
6.5 n皇后問(wèn)題 165
6.5.1 n皇后問(wèn)題的求解過(guò)程分析 165
6.5.2 n皇后問(wèn)題的求解實(shí)現(xiàn) 166
6.5.3 數(shù)獨(dú)問(wèn)題 168
6.6 一些經(jīng)典算法的回溯求解 172
習(xí)題 182
第7章 分支與限界
7.1 分支與限界算法 184
7.2 作業(yè)分配問(wèn)題 186
7.2.1 分支限界法解作業(yè)分配問(wèn)題的思想方法 186
7.2.2 分支限界法解作業(yè)分配問(wèn)題算法的實(shí)現(xiàn) 188
7.3 單源最短路徑問(wèn)題 192
7.3.1 分支限界法解單源最短路徑問(wèn)題的思想方法 192
7.3.2 分支限界法解單源最短路徑問(wèn)題算法的實(shí)現(xiàn) 194
7.4 0/1背包問(wèn)題 197
7.4.1 分支限界法解0/1背包問(wèn)題的思想方法 197
7.4.2 0/1背包問(wèn)題分支限界算法的實(shí)現(xiàn) 200
7.5 貨郎擔(dān)問(wèn)題 204
7.5.1 費(fèi)用矩陣的特性及歸約 204
7.5.2 分支限界法解最短漢密爾頓回路的思想 205
7.5.3 貨郎擔(dān)問(wèn)題的求解過(guò)程 208
7.5.4 幾個(gè)輔助函數(shù)的實(shí)現(xiàn) 212
7.5.5 貨郎擔(dān)問(wèn)題分支限界算法的實(shí)現(xiàn) 217
習(xí)題 219
第8章 隨機(jī)算法
8.1 隨機(jī)化算法 222
8.1.1 為什么要隨機(jī)化 222
8.1.2 隨機(jī)算法 222
8.2 隨機(jī)數(shù)發(fā)生器 223
8.3 數(shù)值概率算法 225
8.4 拉斯維加斯算法 229
8.4.1 隨機(jī)快速排序算法 230
8.4.2 隨機(jī)選擇算法 231
8.4.3 n皇后問(wèn)題的隨機(jī)算法 232
8.4.4 隨機(jī)字符串匹配算法 234
8.4.5 整數(shù)因子 239
8.5 蒙特卡羅算法 242
8.5.1 函數(shù)極大值估計(jì)問(wèn)題 243
8.5.2 主元素問(wèn)題 244
8.5.3 素?cái)?shù)測(cè)試問(wèn)題 246
8.6 隨機(jī)算法的應(yīng)用 251
習(xí)題 252
第9章 NP完全問(wèn)題
9.1 判定問(wèn)題和優(yōu)化問(wèn)題 254
9.2 P類問(wèn)題和NP類問(wèn)題 255
9.3 NP完全問(wèn)題 260
習(xí)題 262
參考文獻(xiàn)
書單推薦
