本書不僅講解傳統(tǒng)的算法設(shè)計策略和技巧，而且關(guān)注算法領(lǐng)域不斷涌現(xiàn)的新概念、新方法和新應(yīng)用，幫助讀者把握技術(shù)熱點及發(fā)展趨勢。書中引入了降維技術(shù)、并行算法、隨機算法、層次化存儲結(jié)構(gòu)算法和流算法等新內(nèi)容，大量使用概率分析和隨機化技術(shù)，并包含眾多新穎的示例，特別是強調(diào)計算模型和計算環(huán)境，不再局限于理想化的隨機存取機模型。全書內(nèi)容簡潔明快，并配有豐富的習題和拓展閱讀資料，適合作為高等院校計算機相關(guān)專業(yè)的教材，也適合業(yè)界技術(shù)人員閱讀參考。
出版者的話
譯者序
前言
致謝
第1章 模型與分析1
1.1 計算斐波那契數(shù)1
1.2 快速乘法3
1.3 計算模型3
1.4 隨機算法簡介4
1.4.1 另一種隨機算法6
1.5 其他計算模型8
1.5.1 外部存儲器模型8
1.5.2 并行模型8
拓展閱讀10
習題10
第2章 概率基礎(chǔ)與尾部不等式13
2.1 概率基礎(chǔ)13
2.2 尾部不等式17
2.3 生成隨機數(shù)20
2.3.1 生成具有任意分布的隨機變量21
2.3.2 由順序文件生成隨機變量21
2.3.3 生成隨機置換23
拓展閱讀25
習題25
第3章 熱身問題27
3.1 計算最大公因子的歐幾里得算法27
3.1.1 擴展歐幾里得算法27
3.1.2 在密碼學中的應(yīng)用28
3.2 尋找第k小的元素28
3.2.1 選擇隨機的劃分元29
3.2.2 中位數(shù)的中位數(shù)30
3.3 詞的排序32
3.4 可歸并的堆34
3.4.1 歸并二項堆35
3.5 一個簡單的半動態(tài)詞典35
3.5.1 勢能法與平攤分析36
3.6 下界37
拓展閱讀39
習題39
第4章 優(yōu)化Ⅰ：蠻力法與貪婪策略42
4.1 啟發(fā)式搜索方法42
4.1.1 博弈樹44
4.2 貪婪算法的框架46
4.2.1 最大支撐樹49
4.2.2 尋找最小權(quán)值子集49
4.2.3 一個調(diào)度問題50
4.3 最小支撐樹算法的高效數(shù)據(jù)結(jié)構(gòu)51
4.3.1 并查集的一種簡單數(shù)據(jù)結(jié)構(gòu)52
4.3.2 更快的方案53
4.3.3 增長最慢的函數(shù)54
4.3.4 整合55
4.3.5 僅做道路壓縮56
4.4 其他不同形式的貪婪策略57
4.5 與貪婪策略的折中58
4.6 梯度下降59
4.6.1 應(yīng)用63
拓展閱讀65
習題66
第5章 優(yōu)化Ⅱ：動態(tài)規(guī)劃69
5.1 背包問題70
5.2 上下文無關(guān)文法的解析71
5.3 最長單調(diào)子序列72
5.4 函數(shù)逼近74
5.5 最大似然估計的Viterbi算法75
5.6 樹中的最大權(quán)獨立集76
拓展閱讀76
習題77
第6章 查找80
6.1 跳表——一個簡單的字典80
6.1.1 跳表的構(gòu)造80
6.1.2 分析81
6.1.3 更強的尾部估計82
6.2 樹堆：隨機查找樹83
6.3 全域哈希86
6.3.1 全域哈希函數(shù)的存在性88
6.4 完美哈希函數(shù)88
6.4.1 將期望界轉(zhuǎn)換為最差情況的界89
6.5 一個復(fù)雜度為log log N的優(yōu)先級隊列89
拓展閱讀91
習題92
第7章 多維查找與幾何算法94
7.1 區(qū)間樹與范圍樹94
7.1.1 一維范圍查找94
7.1.2 二維范圍查找96
7.2 kd樹97
7.3 優(yōu)先級查找樹99
7.4 平面凸包101
7.4.1 Jarvis March算法102
7.4.2 Graham掃描算法102
7.4.3 排序與凸包103
7.5 快速凸包算法104
7.5.1 分析105
7.5.2 期望運行時間106
7.6 使用持久化數(shù)據(jù)結(jié)構(gòu)的點定位107
7.7 增量構(gòu)造法109
拓展閱讀111
習題111
第8章 字符串匹配與指紋函數(shù)114
8.1 RabinKarp指紋字符串查找算法114
8.2 KMP算法117
8.2.1 KMP算法的分析120
8.2.2 模式分析120
8.3 字典樹及其應(yīng)用121
拓展閱讀123
習題123
第9章 快速傅里葉變換及其應(yīng)用125
9.1 多項式求值與插值125
9.1.1 多項式相乘126
9.2 CooleyTukey算法126
9.3 蝶形網(wǎng)絡(luò)128
9.4 SchonageStrassen快速乘法算法129
9.5 廣義字符串匹配131
9.5.1 基于卷積的方法131
拓展閱讀133
習題133
第10章 圖算法135
10.1 深度優(yōu)先搜索135
10.2 深度優(yōu)先搜索的應(yīng)用138
10.2.1 強連通分支138
10.2.2 雙連通分支140
10.3 道路問題142
10.3.1 BellmanFord單源最短道路算法143
10.3.2 Dijkstra單源最短道路算法143
10.3.3 任意兩點之間的最短道路算法145
10.4 計算賦權(quán)圖中的支撐子145
10.5 全局最小割148
10.5.1 收縮算法149
10.5.2 最小割的概率149
拓展閱讀150
習題151
第11章 最大流及其應(yīng)用153
11.1 最大流的性質(zhì)與算法155
11.1.1 最大流與最小割155
11.1.2 FordFulkerson算法156
11.1.3 EdmondKarp可增廣道路策略157
11.1.4 單調(diào)性引理及迭代次數(shù)的界158
11.2 最大流的應(yīng)用159
11.2.1 邊不相交的道路159
11.2.2 二部圖的匹配159
11.2.3 環(huán)流問題162
11.2.4 項目規(guī)劃164
拓展閱讀165
習題165
第12章 NP完全性與近似算法168
12.1 分類與可歸約性170
12.2 CookLevin定理172
12.3 常見的NP完全問題173
12.4 NP完全性的證明175
12.4.1 頂點覆蓋及相關(guān)問題175
12.4.2 圖的3著色問題176
12.4.3 背包問題及相關(guān)問題177
12.5 其他重要的復(fù)雜度類179
12.6 使用近似算法處理困難性181
12.6.1 最大背包問題182
12.6.2 最小集合覆蓋183
12.6.3 幾何旅行商問題184
12.6.4 3著色問題185
12.6.5 最大割問題185
拓展閱讀186
習題186
第13章 降維188
13.1 隨機投影與JohnsonLindenstrauss引理188
13.2 高斯消元法191
13.3 奇異值分解及其應(yīng)用192
13.3.1 矩陣代數(shù)與SVD定理192
13.3.2 使用SVD的低秩近似194
13.3.3 低秩近似的應(yīng)用196
13.3.4 聚類問題197
13.3.5 SVD定理的證明199
拓展閱讀200
習題200
第14章 并行算法201
14.1 并行計算模型201
14.2 排序和比較問題202
14.2.1 尋找最大值202
14.2.2 排序204
14.3 并行前綴208
14.4 基本的圖算法212
14.4.1 列表排名212
14.4.2 連通分支214
14.5 基本的幾何算法216
14.6 并行模型之間的關(guān)系217
14.6.1 網(wǎng)格上的路由218
拓展閱讀220
習題220
第15章 層次化存儲結(jié)構(gòu)及高速緩存223
15.1 層次化存儲模型223
15.2 矩陣轉(zhuǎn)置224
15.2.1 矩陣乘法225
15.3 在外部存儲器中進行排序226
15.3.1 我們可以改進這個算法嗎227
15.4 高速緩存參數(shù)無關(guān)的算法設(shè)計228
15.4.1 參數(shù)無關(guān)的矩陣轉(zhuǎn)置229
拓展閱讀231
習題232
第16章 流數(shù)據(jù)模型233
16.1 引言233
16.2 查找流中的頻繁元素233
16.3 流中的相異元素236
16.4 頻數(shù)矩問題及其應(yīng)用238
16.4.1 均值的中位數(shù)241
16.4.2 二階頻數(shù)矩的特例241
16.5 流模型下界的證明243
拓展閱讀244
習題245
附錄A 遞推關(guān)系與生成函數(shù)247
參考文獻253
書單推薦
