本書不僅講解傳統(tǒng)的算法設計策略和技巧，而且關注算法領域不斷涌現(xiàn)的新概念、新方法和新應用，幫助讀者把握技術熱點及發(fā)展趨勢。書中引入了降維技術、并行算法、隨機算法、層次化存儲結構算法和流算法等新內容，大量使用概率分析和隨機化技術，并包含眾多新穎的示例，特別是強調計算模型和計算環(huán)境，不再局限于理想化的隨機存取機模型。全書內容簡潔明快，并配有豐富的習題和拓展閱讀資料，適合作為高等院校計算機相關專業(yè)的教材，也適合業(yè)界技術人員閱讀參考。
出版者的話
譯者序
前言
致謝
第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章 概率基礎與尾部不等式13
2.1 概率基礎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 在密碼學中的應用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 尋找最小權值子集49
4.2.3 一個調度問題50
4.3 最小支撐樹算法的高效數(shù)據(jù)結構51
4.3.1 并查集的一種簡單數(shù)據(jù)結構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 應用63
拓展閱讀65
習題66
第5章 優(yōu)化Ⅱ：動態(tài)規(guī)劃69
5.1 背包問題70
5.2 上下文無關文法的解析71
5.3 最長單調子序列72
5.4 函數(shù)逼近74
5.5 最大似然估計的Viterbi算法75
5.6 樹中的最大權獨立集76
拓展閱讀76
習題77
第6章 查找80
6.1 跳表——一個簡單的字典80
6.1.1 跳表的構造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 將期望界轉換為最差情況的界89
6.5 一個復雜度為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ù)結構的點定位107
7.7 增量構造法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 字典樹及其應用121
拓展閱讀123
習題123
第9章 快速傅里葉變換及其應用125
9.1 多項式求值與插值125
9.1.1 多項式相乘126
9.2 CooleyTukey算法126
9.3 蝶形網(wǎng)絡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)先搜索的應用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 計算賦權圖中的支撐子145
10.5 全局最小割148
10.5.1 收縮算法149
10.5.2 最小割的概率149
拓展閱讀150
習題151
第11章 最大流及其應用153
11.1 最大流的性質與算法155
11.1.1 最大流與最小割155
11.1.2 FordFulkerson算法156
11.1.3 EdmondKarp可增廣道路策略157
11.1.4 單調性引理及迭代次數(shù)的界158
11.2 最大流的應用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 頂點覆蓋及相關問題175
12.4.2 圖的3著色問題176
12.4.3 背包問題及相關問題177
12.5 其他重要的復雜度類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 奇異值分解及其應用192
13.3.1 矩陣代數(shù)與SVD定理192
13.3.2 使用SVD的低秩近似194
13.3.3 低秩近似的應用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 并行模型之間的關系217
14.6.1 網(wǎng)格上的路由218
拓展閱讀220
習題220
第15章 層次化存儲結構及高速緩存223
15.1 層次化存儲模型223
15.2 矩陣轉置224
15.2.1 矩陣乘法225
15.3 在外部存儲器中進行排序226
15.3.1 我們可以改進這個算法嗎227
15.4 高速緩存參數(shù)無關的算法設計228
15.4.1 參數(shù)無關的矩陣轉置229
拓展閱讀231
習題232
第16章 流數(shù)據(jù)模型233
16.1 引言233
16.2 查找流中的頻繁元素233
16.3 流中的相異元素236
16.4 頻數(shù)矩問題及其應用238
16.4.1 均值的中位數(shù)241
16.4.2 二階頻數(shù)矩的特例241
16.5 流模型下界的證明243
拓展閱讀244
習題245
附錄A 遞推關系與生成函數(shù)247
參考文獻253
書單推薦
