本书全面介绍算法设计思想以及算法分析原理。全书共分为四个部分：第一部分是基础知识，包含第1章与第2章，主要介绍算法的基本概念、算法复杂度分析的基本方法、随机算法以及理解本书所需掌握的数据结构知识等；第二部分包含第3～9章，介绍各种算法设计思想，包括分治策略、贪心策略、动态规划、搜索与遍历、回溯、分支定界、代数方法等；第三部分包含第10～12章，介绍算法复杂度理论知识，包括下界定理、NP难和NP完全问题以及近似算法等；最后一部分是并行算法，包括第13～15章，介绍PRAM算法、网格算法以及超立方算法。

本书结构完整，内容从易到难，包含丰富实例与习题，对所涉及算法均提供C++或伪代码，不仅可作为计算机专业本科或研究生的算法课程教材，也可作为算法爱好者的自学参考书。

如果我们预挑出计算机科学中那些影响长久的贡献，算法（algorithm）一定位列其中。自从人类发明了可以执行基本数学运算的机器，什么是可以计算的以及如何计算就成为人们一直研究的课题。伴随此项研究，人们发现了大量的重要算法以及设计方法。算法成为计算机科学领域中的一项重要组成部分。本书的目的就是对有关算法的内容精心地组织，从而使得使用本书的同学以及实践者可以设计和分析全新的算法。

一本包含所有已发明的算法的书将会异常冗长。传统的算法书通常只对很少的几个问题领域有深入的阐述。对于每个问题，通常会给出并分析效率最高的算法。这样的做法有一个主要缺点。尽管同学们了解了很多很快的算法并且也掌握了分析算法的工具，但还是对如何设计一个好的算法信心不足。

这里所欠缺的就是没有强调设计（design）技术。设计方面的知识一定可以帮助创造好的算法，没有分析工具则无法判断算法的优劣。这样设计为主分析为辅的关系就自然地延伸为有效的讲授之道：我们将围绕基本的算法设计策略来组织本书。基本的设计策略是相对比较少的。并且大部分读者想要学习的算法可以划分到这些分类中；例如归并排序和快速排序是分治策略的例子，而Kruskal的最小生成树算法和Dijkstra的单源最短路径算法是贪心策略的例子。理解这些策略是掌握设计技能的重要的第一步。

尽管我们深切地认为强调设计以及分析是组织算法学习的正确之路，这里还是要给出一些注意事项。首先，我们并没有包括所有的设计原理。例如线性规划是最成功的技术之一，由于它往往由单独的课程所讲述从而没有包含到本书中。其次，读者不应该死板地学习算法设计，认为每个算法都是由一种技术得到的。事实并不是如此。

本书的主要篇幅，第3～9章，描述了不同的设计策略。每种策略首先描述一个大概。通常给出一个“程序抽象”来描述采用该策略所形成的计算模式的大纲。接着给出一系列的例子来讲述该策略的复杂以及变化。这些例子往往是按照由易到难的次序安排。其复杂的程度可以在不同的方面升高。我们通常先给出一个非常容易理解的例子，所使用的数据结构也仅仅为一维的数组。对这个例子，所用设计策略显而易见可以得到正确的解法。后面的例子可能需要证明基于该设计技术的算法是正确的。也可能是需要更加复杂的数据结构（例如树或者图），并且分析更加复杂。这样组织的主要目的是强调组成和分析算法的艺术。另外还希望能让读者体会好的程序结构以及算法正确性的证明。

第1～12章中的算法都是用C++或者伪C++代码给出。很多是可以直接运行并且已经经过测试的。选择C++是因为它是面向对象的程序语言。C++在计算机业界被广泛接受还有其他的很多理由。选择这种程序语言并不是说不熟悉C++的读者就不能用这本书。因为本书中大部分的算法都是比较短的，用来描述这些算法的代码也足够简单可以被广大读者所理解。第13～15章讲述并行计算。并行计算是一个飞速发展的领域，没有一个被广泛接受的模型或者程序语言。因此，我们选择用伪代码来描述这些算法。第1～12章中也有些简单的算法是用伪代码描述的。这是因为我们认为这些算法的核心思想用伪代码描述更加清晰。如何将这些伪代码转换为C++代码将作为练习留给读者。

另外本书的一大特色是广泛地讨论了随机算法。第13～15章中的很多算法是随机的。其他章节中也包含了一些随机算法。一门学季制的并行算法导论课程可以包含第13～15章，以及其他少量的补充内容。

我们也标出了一些内容（用*号）是适用于高级课程的。这本书的内容可以作为本科高年级学生或者研究生的一门学期制课程，或者两门学季制的课程。它需要学生具备高级语言的编程能力，其余的内容都自完备的。实践上，一门数据结构课也是有帮助的，这样学生具备更成熟的编程能力。如果是学季制的学校，第一个学季可以讲授一些基本的设计技术，例如第3章～第9章中的分治、贪心、动态规划、搜索和遍历、回溯、分治定界以及代数方法（见表Ⅰ）。第二个学季可以讲授第10～15章：下界定理、 D_Dd__________ǒe??_____________

如果课程是一个学期的，并且学生之前没有接触过数据结构和大O表示，那么第1～7章、第11章以及第13章的内容比较合适（见表Ⅲ）。

如果进度更加紧凑一些可以包含第1～7章、第11章、第13章以及第14章的内容（见表Ⅳ）。

如果学生已经掌握了数据结构和大O表示，可以由第3～11章，以及第13～15章构成一门高级课程（见表Ⅴ）。

表Ⅰ  第一学季

周次

内容

阅读

1

引言

1.1-1.3

2

引言

数据结构

1.4

2.1、2.2

3

数据结构

2.3-2.6

4

分治

第3章

第一次作业

5

贪心算法

第4章

期中考试

6

动态规划

第5章

7

搜索与遍历

第6章

第二次作业

8

回溯

第7章

9

分支定界

第8章

10

代数方法

第9章

第三次作业

期末考试

表Ⅱ  第二学季

周次

内容

阅读

1

下界定理

10.1-10.3

2

下界定理

完全和难问题

10.4

11.1，11.2

3

完全和难问题

11.3，11.4

4

完全和难问题

近似算法

11.5，11.6

12.1，12.2

第一次作业

5

近似算法

12.3-12.6

期中考试

6

PRAM算法

13.1-13.4

7

PRAM算法

13.5-13.9

第二次作业

8

网格算法

14.1-14.5

9

网格算法

超立方算法

14.6-14.8

15.1-15.3

10

超立方算法

15.4-15.8

第三次作业

期末考试

表Ⅲ  学期：中速（无基础）

周次

内容

阅读

1

引言

1.1-1.3

2

引言

数据结构

1.4

2.1，2.2

3

数据结构

2.3-2.6

4

分治

3.1-3.4

第一次作业

5

分治

3.5-3.7

考试Ⅰ

6

贪心算法

4.1-4.4

7

贪心算法

4.5-4.7

第二次作业

8

动态规划

5.1-5.5

9

动态规划

5.6-5.10

10

搜索与遍历

6.1-6.4

第三次作业

考试Ⅱ

11

回溯

7.1-7.3

12

回溯

7.4-7.6

续表    

周次

内容

阅读

13

完全和难问题

11.1-11.3

第四次作业

14

完全和难问题

11.4-11.6

15

PRAM算法

13.1-13.4

16

PRAM算法

13.5-13.9

第五次作业

考试Ⅲ

表Ⅳ  学期：快速（无基础）

周次

内容

阅读

1

引言

1.1-1.3

2

引言

数据结构

1.4

2.1，2.2

3

数据结构

2.3-2.6

4

分治

3.1-3.5

第一次作业

5

分治

贪心算法

3.6-3.7

4.1-4.3

考试Ⅰ

6

贪心算法

4.4-4.7

7

动态规划

5.1-5.7

第二次作业

8

动态规划

搜索与遍历

5.8-5.10

6.1-6.2

9

搜索与遍历

回溯

6.3-6.4

7.1-7.2

10

回溯

7.3-7.6

第三次作业

考试Ⅱ

11

完全和难问题

11.1-11.3

12

完全和难问题

11.4-11.6

13

PRAM算法

13.1-13.4

第四次作业

14

PRAM算法

13.5-13.9

15

网格算法

14.1-14.3

16

网格算法

14.4-14.8

第五次作业

考试Ⅲ

表Ⅴ  学期：高级课程（快速）

周次

内容

阅读

1

分治

3.1-3.5

2

分治

贪心算法

3.6-3.7

4.1-4.3

3

贪心算法

4.4-4.7

4

动态规划

第5章

第一次作业

5

搜索与遍历

第6章

考试Ⅰ

6

回溯

第7章

7

分支定界

第8章

第二次作业

8

代数方法

第9章

9

下界定理

第10章

10

完全和难问题

11.1-11.3

第三次作业

考试Ⅱ

11

完全和难问题

11.4-11.6

12

PRAM算法

13.1-13.4

13

PRAM算法

13.5-13.9

第四次作业

14

网格算法

14.1-14.5

15

网格算法

超立方算法

14.6-14.8

15.1-15.3

16

超立方算法

15.4-15.8

第五次作业

考试Ⅲ

每章的最后给出了大量的习题可以作为课程作业。我们发现最受欢迎并且最有启发性的作业是让学生在同一个数据集上运行两个算法并且比较两个算法的运行时间。本书的绝大多数算法都有实现的细节，供学生们使用。将这些C++程序转换为其他语言的程序也不困难。那么剩余的就是构造合适的数据集以及编写一个main函数来完成上述的运行记时。记时的结果应该与算法的时间复杂度渐进分析的结论相一致。这项任务并不简单，是有教育意义并且很有趣的。最重要的是它强调了一个往往被人们忽视的方面，也就是算法在实用过程中还有实践性的一面。

在这个新版中，我们还加入一些新的例子以及习题，加强了平摊复杂度，更新了每章最后的参考文献以及阅读。

致谢

我们要感谢Martin J. Biernat、Jeff Jenness、Saleem Khan、Ming-Yang Kao、Douglas M. Compbell以及Stephen P. Leach的意见和建议。我们要感谢佛罗里达大学的同学指出了较早版本中的错误。我们还要感谢Teo Gonzalez、Danny Krizanc以及David Wei仔细阅读了部分章节。

Ellis Horowitz

Sartaj Sahni

Sanguthevar Rajasekaran

第1章  导论 1

1.1  什么是算法 1

1.2  算法规范 3

1.2.1  导论 3

1.2.2  递归算法 5

1.3  性能分析 8

1.3.1  空间复杂度 8

1.3.2  时间复杂度 9

1.3.3  平摊复杂度 16

1.3.4  渐进符号（ 

1.3.5  实际复杂度 29

1.3.6  性能测量 31

1.4  概率算法 39

1.4.1  概率论基础 39

1.4.2  随机算法：正规描述 42

1.4.3  确认重复元素 43

1.4.4  素数测试 44

1.4.5  优缺点 47

1.5  参考文献及阅读 49

第2章  数据结构基础 50

2.1  栈与队列 50

2.2  树 56

2.2.1  术语 57

2.2.2  二叉树 58

2.3  字典 60

2.3.1  二叉搜索树 61

2.4  优先队列 66

2.4.1  堆 67

2.4.2  堆排序 71

2.5  集合与不相交集合的并集 73

2.5.1  导论 73

2.5.2  求并集及查找操作 74

2.6  图 80

2.6.1  导论 80

2.6.2  定义 81

2.6.3  图的表示 83

2.7  参考文献及阅读 89

第3章  分治策略 90

3.1  一般方法 90

3.2  残缺棋盘 93

3.3  二分搜索 96

3.4  找最大值和最小值 101

3.5  合并排序 105

3.6  快速排序 111

3.6.1  性能测量 114

3.6.2  随机排序算法 115

3.7  选择 117

3.7.1  最差情况下的最优算法 120

3.7.2  Select2的实现 122

3.8  矩阵相乘 127

3.9  凸包 130

3.9.1  几种几何基本 130

3.9.2  QuickHull算法 131

3.9.3  Graham扫描 132

3.9.4  O(nlogn)的分治算法 134

3.10  参考文献及阅读 136

3.11  附加习题 137

第4章  贪心法 139

4.1  一般方法 139

4.2  集装箱装船 142

4.3  背包问题 144

4.4  树节点分裂 147

4.5  有期限的工作序列化 150

4.6  最小生成树 156

4.6.1  Prim算法 157

4.6.2  Kruskal算法 159

4.6.3  最优的随机算法（*） 162

4.7  磁带最优存储 164

4.8  最优合并模式 168

4.9  单源最短路径 172

4.10  参考文献及阅读 177

4.11  附加习题 178

第5章  动态规划 180

5.1  一般方法 180

5.2  多段图 183

5.3  每对顶点间最短路径 187

5.4  单源最短路径：一般权重 190

5.5  最优二叉搜索树（*） 193

5.6  串编辑 198

5.7  0/1背包 201

5.8  可靠性设计 207

5.9  旅行商问题 209

5.10  流水车间调度 211

5.11  参考文献及阅读 215

5.12  附加习题 215

第6章  基本遍历及搜索技术 219

6.1  二叉树的遍历及搜索 219

6.2  图的遍历及搜索 222

6.2.1  广度优先搜索及遍历 223

6.2.2  深度优先搜索及遍历 225

6.3  连通分支及生成树 226

6.4  双连通分支 228

6.5  参考文献及阅读 234

第7章  回溯 235

7.1  一般方法 235

7.2  八皇后问题 243

7.3  子集求和 246

7.4  图着色 248

7.5  哈密尔顿回路 251

7.6  背包问题 253

7.7  参考文献及阅读 256

7.8  附加习题 257

第8章  分支定界 260

8.1  方法 260

8.1.1  最少代价（LC）搜索 260

8.1.2  15拼图：一个例子 262

8.1.3  最少代价搜索的控制抽象 265

8.1.4  定界 266

8.1.5  FIFO分支定界 268

8.1.6  LC分支定界 268

8.2  0/1背包问题 269

8.2.1  LC分支定界解法 270

8.2.2  FIFO分支定界解法 272

8.3  旅行商问题（*） 275

8.4  效率 280

8.5  参考文献及阅读 282

第9章  代数问题 283

9.1  一般方法 283

9.2  求值与插值 284

9.3  快速傅里叶变换（FFT） 292

9.3.1  In-place版本的快速傅里叶变换 296

9.3.2  继续思考 298

9.4  模算术 299

9.5  更快的求值和插值 305

9.6  参考文献及阅读 310

第10章  下界理论 312

10.1  比较树 312

10.1.1  有序搜索 313

10.1.2　排序 314

10.1.3  选择 316

10.2  预言及对手论证 318

10.2.1  合并 318

10.2.2  最大和次大 319

10.2.3  状态空间法 320

10.2.4  选择 321

10.3　规约求下界 322

10.3.1　找凸包 323

10.3.2　不相交集合问题 324

10.3.3　在线中位数查找 324

10.3.4　三角形矩阵相乘 325

10.3.5　下三角形矩阵求逆 326

10.3.6　计算传递闭包 327

10.4　代数问题中的技巧（*） 329

10.5　参考文献及阅读 335

第11章  难及完全问题 336

11.1  基本概念 336

11.1.1  非确定算法 336

11.1.2   

11.2  Cook定理（*） 344

11.3   ______

11.3.1  团判定问题（CDP） 350

11.3.2  点覆盖判定问题（NCDP） 351

11.3.3  色数判定问题（CNDP） 352

11.3.4  有向图哈密尔顿回路问题（DHC）（*） 353

11.3.5  旅行商判定问题（TSP） 355

11.3.6  AND/OR图判定问题（AOG） 355

11.4   D_Dd___

11.4.1  调度相同处理器 360

11.4.2  流水车间调度 362

11.4.3  作业车间调度 363

11.5  难的代码生成问题 364

11.5.1  有公共子表达式的代码生成 366

11.5.2  实现并行赋值指令 369

11.6  简化的 D_Dd

11.7  参考文献及阅读 372

11.8  附加习题 373

第12章  近似算法 375

12.1  导论 375

12.2  绝对近似 377

12.2.1  平面图着色 377

12.2.2  最大程序存储问题 378

12.2.3   D_Dd___

12.3  ε近似 380

12.3.1  调度独立任务 380

12.3.2  装箱 382

12.3.3   ________

12.4  多项式时间近似方案 388

12.4.1  调度独立任务 388

12.4.2  0/1背包 389

12.5  完全多项式时间近似方案 393

12.5.1  舍入 394

12.5.2  区间划分 397

12.5.3  间隔 397

12.6  概率上好的近似方案（*） 400

12.7  参考文献及阅读 402

12.8  附加习题 402

第13章  PRAM算法 406

13.1  介绍 406

13.2  计算模型 408

13.3  基本技巧和算法 412

13.3.1  前缀计算 413

13.3.2  表排列 414

13.4  选取 420

13.4.1  使用n2个处理器选取最大元 420

13.4.2  使用 D_Dd______

13.4.3  整数范围内的最大元 421

13.4.4  使用n2个处理进行一般性选择 423

13.4.5  工作最优的随机化选择算法（*） 423

13.5  归并 426

13.5.1  对数时间的算法 426

13.5.2  奇偶归并 426

13.5.3  工作最优的算法 428

13.5.4  一个运行时间为O(log log m)的算法 429

13.6  排序 430

13.6.1  奇偶归并排序 430

13.6.2  一个可供选择的随机化算法 431

13.6.3  Preparata算法 431

13.6.4  Reischuk随机化算法（*） 432

13.7  图问题 434

13.7.1  传递闭包的另一种计算方法 436

13.7.2  全点对的最小路径问题 436

13.8  凸包计算 437

13.9  下界 439

13.9.1  排序的平均运行时间下界 440

13.9.2  寻找最大元 441

13.10  参考文献及阅读 442

13.11  附加习题 443

第14章  网格算法 445

14.1  计算模型 445

14.2  数据包路由 446

14.2.1  线性数组中的数据包路由 447

14.2.2  网格上PPR问题的贪心算法 450

14.2.3  使用小队列的随机化算法 450

14.3  基本算法 452

14.3.1  广播 453

14.3.2  前缀计算 454

14.3.3  数据聚集 455

14.3.4  稀疏列举排序 456

14.4  选取 459

14.4.1  n = p′情形下的随机化算法（*） 459

14.4.2  n > p情形下的随机化算法（*） 460

14.4.3  n > p情形下的确定性算法 460

14.5  归并 463

14.5.1  通过秩实现线性数组上的归并 463

14.5.2  线性数组上的奇偶归并 464

14.5.3  网格上的奇偶归并 465

14.6  排序 466

14.6.1  线性数组上的排序 466

14.6.2  网格上的排序 467

14.7  图问题 470

14.7.1  n×n 网格上的传递闭包算法 471

14.7.2  全点对最短路径算法 472

14.8  凸包计算 472

14.9  参考文献及阅读 475

14.10  附加习题 477

第15章  超立方算法 479

15.1  计算模型 479

15.1.1  超立方 479

15.1.2  蝴蝶网络 480

15.1.3  其他网络的嵌入 482

15.2  偏转置路由 484

15.2.1  贪心算法 484

15.2.2  随机化算法 485

15.3  基本算法 487

15.3.1  广播 487

15.3.2  前缀计算 488

15.3.3  数据聚集 489

15.3.4  稀疏列举排序 491

15.4  选取 492

15.4.1  n= p情形下的随机化算法（*） 492

15.4.2  n > p情形下的随机化选取算法（*） 493

15.4.3  n > p情形下的确定性算法 493

15.5  归并 495

15.5.1  奇偶归并 495

15.5.2  双调归并 496

15.6  排序 498

15.6.1  奇偶归并排序 498

15.6.2  双调排序 498

15.7  图问题 499

15.8  凸包计算 500

15.9  参考文献及阅读 501

15.10  附加习题 502