本书不仅讲解传统的算法设计策略和技巧，而且关注算法领域不断涌现的新概念、新方法和新应用，帮助读者把握技术热点及发展趋势。书中引入了降维技术、并行算法、随机算法、层次化存储结构算法和流算法等新内容，大量使用概率分析和随机化技术，并包含众多新颖的示例，*是强调计算模型和计算环境，不再局限于理想化的随机存取机模型。全书内容简洁明快，并配有丰富的习题和拓展阅读资料，适合作为高等院校计算机相关专业的教材，也适合业界技术人员阅读参考。

出版者的话

译者序

前言

致谢

[0第0]1章　模型与分析1

1.1　计算斐波那契数1

1.2　快速乘[0法0]3

1.3　计算模型3

1.4　随[1机1]算[0法0]简介4

1.4.1　另一种随[1机1]算[0法0]6

1.5　其他计算模型8

1.5.1　外部存储器模型8

1.5.2　并行模型8

拓展阅读10

[*]题10

[0第0]2章　概率基础与尾部不等式13

2.1　概率基础13

2.2　尾部不等式17

2.3　生成随[1机1]数20

2.3.1　生成具有任意分布的随[1机1]变量21

2.3.2　由顺序文[亻牛]生成随[1机1]变量21

2.3.3　生成随[1机1]置换23

拓展阅读25

[*]题25

[0第0]3章　热身问题27

3.1　计算[*][0大0]公因子的欧几里得算[0法0]27

3.1.1　扩展欧几里得算[0法0]27

3.1.2　在密码[0学0]中的应用28

3.2　寻找[0第0]k小的元素28

3.2.1　选择随[1机1]的划分元29

3.2.2　中位数的中位数30

3.3　词的排序32

3.4　可归并的堆34

3.4.1　归并二项堆35

3.5　一个简单的半动态词典35

3.5.1　势能[0法0]与平摊分析36

3.6　下界37

拓展阅读39

[*]题39

[0第0]4章　[0优0]化Ⅰ：蛮力[0法0]与贪婪策略42

4.1　启发式搜索方[0法0]42

4.1.1　博弈树44

4.2　贪婪算[0法0]的框架46

4.2.1　[*][0大0]支撑树49

4.2.2　寻找[*]小[0权0]值子集49

4.2.3　一个调度问题50

4.3　[*]小支撑树算[0法0]的*数据结构51

4.3.1　并查集的一种简单数据结构52

4.3.2　更快的方案53

4.3.3　增长[*]慢的函数54

4.3.4　整合55

4.3.5　仅做道路压缩56

4.4　其他不同形式的贪婪策略57

4.5　与贪婪策略的折中58

4.6　梯度下降59

4.6.1　应用63

拓展阅读65

[*]题66

[0第0]5章　[0优0]化Ⅱ：动态规划69

5.1　背包问题70

5.2　上下文无关文[0法0]的解析71

5.3　[*]长单调子序列72

5.4　函数逼近74

5.5　[*][0大0]似然估计的Viterbi算[0法0]75

5.6　树中的[*][0大0][0权0][0独0]立集76

拓展阅读76

[*]题77

[0第0]6章　查找80

6.1　跳表——一个简单的字典80

6.1.1　跳表的构造80

6.1.2　分析81

6.1.3　更强的尾部估计82

6.2　树堆：随[1机1]查找树83

6.3　全域哈希86

6.3.1　全域哈希函数的存在性88

6.4　*哈希函数88

6.4.1　将期望界转换为[*]差情况的界89

6.5　一个复杂度为log log N的[0优0]先级队列89

拓展阅读91

[*]题92

[0第0]7章　多维查找与几何算[0法0]94

7.1　区间树与范围树94

7.1.1　一维范围查找94

7.1.2　二维范围查找96

7.2　kd树97

7.3　[0优0]先级查找树99

7.4　平[mian]凸包101

7.4.1　Jarvis March算[0法0]102

7.4.2　Graham扫描算[0法0]102

7.4.3　排序与凸包103

7.5　快速凸包算[0法0]104

7.5.1　分析105

7.5.2　期望运行时间106

7.6　使用持[1久1]化数据结构的点定位107

7.7　增量构造[0法0]109

拓展阅读111

[*]题111

[0第0]8章　字符串匹配与指纹函数114

8.1　RabinKarp指纹字符串查找算[0法0]114

8.2　KMP算[0法0]117

8.2.1　KMP算[0法0]的分析120

8.2.2　模式分析120

8.3　字典树及其应用121

拓展阅读123

[*]题123

[0第0]9章　快速傅里叶变换及其应用125

9.1　多项式求值与插值125

9.1.1　多项式相乘126

9.2　CooleyTukey算[0法0]126

9.3　蝶形网络128

9.4　SchonageStrassen快速乘[0法0]算[0法0]129

9.5　广义字符串匹配131

9.5.1　基于卷积的方[0法0]131

拓展阅读133

[*]题133

[0第0]10章　图算[0法0]135

10.1　深度[0优0]先搜索135

10.2　深度[0优0]先搜索的应用138

10.2.1　强连通分支138

10.2.2　[0双0]连通分支140

10.3　道路问题142

10.3.1　BellmanFord单源[*]短道路算[0法0]143

10.3.2　Dijkstra单源[*]短道路算[0法0]143

10.3.3　任意两点之间的[*]短道路算[0法0]145

10.4　计算赋[0权0]图中的支撑子145

10.5　全局[*]小割148

10.5.1　收缩算[0法0]149

10.5.2　[*]小割的概率149

拓展阅读150

[*]题151

[0第0]11章　[*][0大0]流及其应用153

11.1　[*][0大0]流的性质与算[0法0]155

11.1.1　[*][0大0]流与[*]小割155

11.1.2　FordFulkerson算[0法0]156

11.1.3　EdmondKarp可增广道路策略157

11.1.4　单调性引理及迭代次数的界158

11.2　[*][0大0]流的应用159

11.2.1　边不相交的道路159

11.2.2　二部图的匹配159

11.2.3　环流问题162

11.2.4　项目规划164

拓展阅读165

[*]题165

[0第0]12章　NPwan全性与近似算[0法0]168

12.1　分类与可归约性170

12.2　CookLevin定理172

12.3　常见的NPwan全问题173

12.4　NPwan全性的证明175

12.4.1　顶点覆盖及相关问题175

12.4.2　图的3着色问题176

12.4.3　背包问题及相关问题177

12.5　其他重要的复杂度类179

12.6　使用近似算[0法0]处理困难性181

12.6.1　[*][0大0]背包问题182

12.6.2　[*]小集合覆盖183

12.6.3　几何旅行[0商0]问题184

12.6.4　3着色问题185

12.6.5　[*][0大0]割问题185

拓展阅读186

[*]题186

[0第0]13章　降维188

13.1　随[1机1]投影与JohnsonLindenstrauss引理188

13.2　高斯消元[0法0]191

13.3　奇异值分解及其应用192

13.3.1　矩阵代数与SVD定理192

13.3.2　使用SVD的低秩近似194

13.3.3　低秩近似的应用196

13.3.4　聚类问题197

13.3.5　SVD定理的证明199

拓展阅读200

[*]题200

[0第0]14章　并行算[0法0]201

14.1　并行计算模型201

14.2　排序和比较问题202

14.2.1　寻找[*][0大0]值202

14.2.2　排序204

14.3　并行前缀208

14.4　基本的图算[0法0]212

14.4.1　列表排[0名0]212

14.4.2　连通分支214

14.5　基本的几何算[0法0]216

14.6　并行模型之间的关系217

14.6.1　网格上的路由218

拓展阅读220

[*]题220

[0第0]15章　层次化存储结构及高速缓存223

15.1　层次化存储模型223

15.2　矩阵转置224

15.2.1　矩阵乘[0法0]225

15.3　在外部存储器中进行排序226

15.3.1　我们可以改进这个算[0法0][*]227

15.4　高速缓存参数无关的算[0法0]设计228

15.4.1　参数无关的矩阵转置229

拓展阅读231

[*]题232

[0第0]16章　流数据模型233

16.1　引言233

16.2　查找流中的频繁元素233

16.3　流中的相异元素236

16.4　频数矩问题及其应用238

16.4.1　均值的中位数241

16.4.2　二阶频数矩的特例241

16.5　流模型下界的证明243

拓展阅读244

[*]题245

附录A　递推关系与生成函数247

参考文献253