本书作者均是世界著名的计算机科学家，在计算机科学理论和算法领域做出了杰出的贡献。本书着重在计算机科学发展领域中，推动新的计算机算法的设计和分析，是一本经典著作，也是计算机算法方面的重要参考书。书中为读者提供了计算机算法的设计技术，对计算机算法的实际设计提供了有效的算法分析。在计算机算法设计方面提供了大量的详细实例和实际应用，并致力于随机算法和并行算法富有成效的深入研究和开发。本书为读者提供了当前流行的对象设计语言C++的实现版本，以及现代计算机科学发展和研究的最新研究成果。

无

在计算机科学领域，影响深远的成就之一要算是对算法（algorithm）这个概念的精确定义。自人类发明了能实现基本算术运算的机器以来，就一直在研究可以计算什么和如何做得更好。计算机的出现促进了许多重要算法和设计方法的发现。计算机科学学科已经将算法研究纳为其中的一部分。本书的目的就是将与算法有关的知识连贯地组织起来，帮助学生和研究人员学会自己设计和分析新的算法。
　　若想用一本书涵盖所有的算法，那么这本书将会非常庞大。以前的算法书籍专注于在深度上研究问题的一个比较窄的领域。对于每个指定的问题提出并分析最有效的算法。这种方法有一个很大的不足，即尽管学生会知道一些快速算法并可能掌握分析工具，但却仍不知道如何设计好的算法。
　　这些图书缺失的部分是不重视设计（design）技术。设计方面的知识肯定会帮助我们创建好的算法，虽然没有分析工具也不可能确定算法的质量。算法设计和算法分析的教学必须合拍，这为本书的设计提供了参考：围绕算法设计的基本策略组织本书。基本设计策略非常少，而所有算法都可以纳入这些类中进行研究。例如，归并排序和快速排序是分治策略的完美例子，Kruskal最小生成树算法和Dijkstra单源最短路径算法是贪心策略的直接例子。了解这些策略是快速掌握设计技术的第一步。
　　尽管我们认为对设计和分析的并重是组织算法学习的合适途径，但还必须注意顺序。首先，我们没有给出所有已知的设计原则。例如，线性规划是一种非常成熟的技术，但通常在其课程中讨论。其次，学生应该避免生搬硬套算法设计的规则，每个算法都不一定是从某种单个技术得出的。
　　第3～9章作为本书的重点，讨论不同的设计策略。首先，使用通用术语描述每种策略。通常，如果应用某种策略，就使用“程序概要”（program abstraction）给出计算的框架。然后使用一些例子帮助了解这些策略的复杂性和变形。例子的复杂度逐渐加深，复杂度增加的方式可能有这么几种。通常，我们会给出非常容易理解的问题，只需要一维数组，不需要其他数据结构。通常设计策略都能很明显地为该问题生成正确解。接下来的例子可能需要证明基于这种设计策略的算法是正确的，或者该算法需要更复杂的数据结构（例如，树或图）且分析过程更复杂。这样组织的目的是突出整体的工艺性和算法分析。另一个目的是让学生了解好的程序结构和算法正确性的依据。
　　第1～12章的算法用C++或C++伪代码书写。其中的很多程序都是可执行的，并已经过测试。选择使用C++描述算法的原因是其具有面向对象的特性。基于此以及其他一些原因，C++已在计算机科学领域得到广泛应用。本书中的大部分算法都很短小，用于描述算法的语言结构也很简单易懂，所以采用C++并不会妨碍对C++不熟悉的人使用本书。第13章、第14章和第15章讨论并行计算。并行计算领域发展很快，因此在该领域不存在广泛接受的单个模型或某种语言。正因为这个原因，我们使用伪代码表示并行算法。在第1～12章中也使用了伪代码描述一些复杂的算法。因为我们觉得这些算法背后的概念用伪代码要比用晦涩的C++结构来描述更好解释清楚。将这些伪代码转化成C++程序的工作留给读者作为习题。
　　本书的另一个特征是广泛覆盖了随机算法领域。在第13章、第14章和第15章中讨论的许多算法都是随机的。在其他章节中也提出了一些随机算法。可以使用一个季度的课程介绍第13章、第14章和第15章的随机算法，还可以涉及一小部分附加材料。
　　有些章节标了星号*，比较适合在高级课程中使用。本书比较适合供大三、大四学生或研究生在一个学期或两个季度内完成。需要有高级语言编程的预备知识，其他所需具备的知识在本书中都已包含。坦率地说，对于已具备成熟编程经验的学生，如果了解数据结构方面的知识对本书的学习会更有帮助。如果学校按季度组织教学，可以在第1个季度讲解第3章～第9章的基本设计技术：分治、贪心算法、动态规划、查找和遍历、回溯、分支限界和代数方法，具体见表1。第2个季度讲解第10章～第15章：下界理论、完全和近似算法、PRAM算法、网格算法和超立方体算法，具体见表2。

表1　 第1个季度
周　　　次主　　　题进　　　度
1导论11节～13节
2导论、数据结构14节、21节、22节
3数据结构23节～26节
4分治算法第3章，第1次作业
5贪心算法第4章，第1次测试
6动态规划第5章
7查找和遍历技术第6章，第2次作业
8回溯第7章
9分支限界第8章
10代数方法第9章，第3次作业，第2次测试

表2　 第2个季度
周　　　次主　　　题进　　　度
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节，第1
次作业
5近似算法123节～126节，第1次测试
6PRAM算法131节～134节
7PRAM算法135节～139节，第2次作业
8网格算法141节～145节
9网格算法、超立方体算法146节～148节、151节～153节
10超立方体算法154节～158节，第3次作业，第2次测试

　　对于按学期安排课程，如果学生不具备数据结构和O符号的知识，就学习第1～7章、第11章和第13章，具体见表3。
　　如果速度更快些，可以学习第1～7章、第11章、第13章和第14章，具体见表4。
　　对于有数据结构和O符号预备知识的学生，可以开设高级班，学习第3～11章、第13～15 章，具体见表5。
　　本书中大部分算法的程序可以从网址http://wwwciseufledu/～raj/BOOKhtml得到。请把您的意见发到raj@ciseufledu。
　　每章后面有大量习题，可以留作作业。我们发现，最有效的做法是让学生在同一个数据集上执行两个程序并分别计时。本书中的大部分算法都提供了实现细节，所以可以很容易加以使用。将这些C++程序转换成其他语言也很容易。留下的问题就是设计合适的数据集并编写主程序来输出计时结果。测得的时间应该与算法已有的渐近分析结果一致。这是一项重要的工作，兼顾指导性和趣味性。更重要的是，它重视通常容易被忽视的对算法的实践。

表3　 学期-中速（不具备基础知识）
周　　　次主　　　题进　　　度
1导论11节～13节
2导论、数据结构14节、21节、22节
3数据结构23节～26节
4分治算法31节～34节，第1次作业
5分治算法35节～37节，第1次测试
6贪心算法41节～44节
7贪心算法45节～47节，第2次作业
8动态规划51节～55节
9动态规划56节～510节
10查找和遍历技术61节～64节，第3次作业，第2次测试
11回溯71节～73节
12回溯74节～76节
13难和完全问题111节～113节，第4次作业
14难和完全问题114节～116节
15PRAM算法131节～134节
16PRAM算法135节～139节，第5次作业，第3次测试

表4　 学期-快速（不具备基础知识）
周　　　次主　　　题进　　　度
1导论11节～13节
2导论、数据结构14节、21节、22节
3数据结构23节～26节
4分治算法31节～35节，第1次作业
5分治算法、贪心算法36节、37节、41节～43节，第1次测试
6贪心算法44节～47节
7动态规划51节～57节，第2次作业
8动态规划、查找和遍历技术58节～510节、61节、62节
9查找和遍历技术、回溯63节、64节、71节、72节
10回溯73节～76节，第3次作业，第2次测试
11难和完全问题111节～113节
12难和完全问题114节～116节
13PRAM算法131节～134节，第4次作业
14PRAM算法135节～139节
15网格算法141节～143节
16网格算法144节～148节，第5次作业，第3次测试

表5　 学期-高级班（快速）
周　　　次主　　　题进　　　度
1分治算法31节～35节
2分治算法、贪心算法36节、37节、41节～43节
3贪心算法44节～47节
4动态规划第5章，第1次作业
5查找和遍历技术第6章，第1次测试
6回溯第7章
7分支限界第8章，第2次作业
8代数方法第9章
9下界理论第10章
10难和完全问题111节～113节，第3次作业，第2次测试
11难和完全问题114节～116节
12PRAM算法131节～134节
13PRAM算法135节～139节，第4次作业
14网格算法141节～145节
15网格算法、超立方体算法146节～148节、151节～153节
16超立方体算法154节～158节，第5次作业，第3次测试


致谢
　　非常感谢Martin J Biernat, Jeff Jenness, Saleem Khan, Ming-Yang Kao, Douglas M Campbell和Stephen P Leach提供的重要意见，这使本书有了极大的提高。感谢UF的学生指出初稿中的一些错误。还要感谢Teo Gonzalez, Danny Krizanc和David Wei仔细阅读了本书的部分章节。

Ellis Horowitz
Sartaj Sahni
Sanguthevar Rajasekaran

无

Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran：Ellis Horowitz:　　Ellis Horowitz于威斯康星-迈迪逊大学获得计算机科学博士学位，从事数据结构、算法和软件设计等领域的计算机科学教育。他是美国国家科学基金会主要调查员。
Sartaj Sahni: Sartaj Sahni于康奈尔大学获得计算机科学博士学位，是佛罗里达大学计算机和信息工程系的资深教授和系主任，是数据结构研究和算法开发方面的资深专家。
Sanguthevar Rajasekaran: Sanguthevar Rajasekaran是佛罗里达大学的教授，是并行算法和随机算法研究开发领域的资深专家。

冯博琴　叶茂 高海昌 等：暂无简介

如果没有算法，计算机就不能完成指定的任务，不能像今天这样为生活带来各种便利，更不要谈模仿人的行为、代替人去工作。不仅计算机专业的从业人员必须了解和使用算法，许多非计算机专业的相关人员也需要设计算法以完成相应的任务。如今算法已广泛应用于社会生活的各个方面，例如进行科学计算、数据分析、知识发现、股票分析、医疗诊断、电梯控制、航班调度、电子邮件系统和病毒防护等。可以毫不夸张地说，计算机上运行的各个程序都是算法的实现。
　　算法是指令的有限集合，包含了执行任务的过程和思想。算法的设计并不简单，它需要一些策略和技术，好的策略和技术能帮助你以更少的时间设计更好的算法。如果不了解这些基本策略，那么在算法设计的道路上可能会困难重重，甚至完全理不清头绪。此外，算法在设计完成后还需要进行分析。解决某个问题的方法可能有很多，不同的方法会产生不同的算法，需要使用分析技术评估算法的性能、比较各种算法的优劣、论证在实际应用中是否可行。而这一点往往容易被忽略。本书就将教你如何设计并分析算法。
　　本书第1章介绍了算法和算法性能分析的基础知识，这是设计和分析算法必须具备的。第2章提供了基本的数据结构知识，为后续章节的介绍做准备。第3章～第9章是本书的重点，讨论不同的算法设计策略。第10章研究下界理论，论证所得算法是不是求解某个问题的渐进最好算法，帮助确定是否存在更快的算法。第11章研究NP难和NP完全问题，讨论了多种经典的NP难问题。第12章介绍近似算法，提供了求解一部分NP难问题的方案。第13章～第15章讨论并行算法，其中涉及到很多随机算法。
　　与其他介绍算法的书籍相比，本书有以下4个特点。第1个特点是对设计技术的重视，作者围绕算法设计的一些基本设计策略组织全书，对这些策略的掌握是快速设计算法的关键。这里介绍的策略并不多，读者在学习本书后便可熟练掌握这些技术。第2个特点是算法的涉及面广，尤其是广泛地覆盖了随机算法领域。第3个特点是将算法设计和分析结合在一起，帮助读者在学会设计的同时学会分析，用分析来论证设计所得算法的优劣，系统地提高算法设计和分析水平。第4个特点是使用C++或伪C++形式给出本书中讨论的很多算法；其中的很多程序都是可执行的，并已经过测试，而伪代码形式的算法则很容易转变成代码实现。
　本书很适合作为高校教材使用，作者在前言中给出了按不同的学时和教学要求制定的教学进度，包括作业的布置和测试的安排等。在每个章节后面附有大量习题。另外，本书也很适合作为算法设计与分析的自学用书或参考书。
　　本书由冯博琴教授组织翻译，叶茂、高海昌和王宇参与译稿、统稿和校阅，参与本书翻译的还有薛亮、韩冰、傅向华、何明、陈宁、朱玉惠、李燕、饶元、霍华及王自强。
　　在翻译过程中，我们力求忠实、准确地把握原著的内容，但由于译者水平有限，翻译时间仓促，书中难免有错误和不准确之处，敬请广大读者批评指正。

译　 者
于西安交通大学
2005年6月

无

第1章　 导论
　 11　 什么是算法
　 12　 算法规范
　　　121　 引言
　　　122　 递归算法
　 13　 性能分析
　　　131　 空间复杂度
　　　132　 时间复杂度
　　　133　 渐近符号 （O、 Ω、 Θ）
　　　134　 实际复杂度
　　　135　 性能度量
　 14　 随机算法
　　　141　 概率论基础
　　　142　 随机算法： 非形式化的描述
　　　143　 识别重复元素
　　　144　 素数测试
　　　145　 优点与缺点
　 15　 参考文献和读物

第2章　 基本数据结构
　 21　 栈和队列
　 22　 树
　　　221　 术语
　　　222　 二叉树
　 23　 字典
　　　231　 二叉查找树
　　　232　 代价分摊
　 24　 优先队列
　　　241　 堆
　　　242　 堆排序
　 25　 集合和不相交集合的并
　　　251　 概述
　　　252　 并和查找操作
　 26　 图
　　　261　 概述
　　　262　 定义
　　　263　 图的表示方法
　 27　 参考文献和读物

第3章　 分治算法
　 31　 一般方法
　 32　 二叉查找
　 33　 查找最大值和最小值
　 34　 归并排序
　 35　 快速排序
　　　351　 性能度量
　　　352　 随机排序算法
　 36　 选择
　　　361　 最坏情况下的最优算法
　　　362　 Select2的实现
　 37　 Strassen矩阵乘法
　 38　 凸包
　　　381　 几种原始几何方法
　　　382　 QuickHull算法
　　　383　 Graham扫描算法
　　　384　 一个O(nlogn)的分治算法
　 39　 参考文献和读物
　 310　 附加习题

第4章　 贪心算法
　 41　 一般方法
　 42　 背包问题
　 43　 树节点分割
　 44　 带有期限的作业顺序问题
　 45　 最小代价生成树
　　　451　 Prim算法
　　　452　 Kruskal算法
　　　453　 一个最优随机算法（*）
　 46　 磁带的最优存储
　 47　 最优归并模式
　 48　 单源最短路径
　 49　 参考文献和读物
　 410　 附加习题

第5章　 动态规划
　 51　 一般方法
　 52　 多部图
　 53　 每一对顶点之间的最短路径
　 54　 单源最短路径： 普通权值
　 55　 最优二叉查找树(*)
　 56　 串编辑
　 57　 0/1背包
　 58　 可靠性设计
　 59　 旅行商问题
　 510　 流水作业调度
　 511　 参考文献和读物
　 512　 附加习题

第6章　 基本的查找和遍历技术
　 61　 二叉树算法
　 62　 图算法
　　　621　 广度优先搜索和遍历
　　　622　 深度优先搜索和遍历
　 63　 连通分支和生成树
　 64　 双连通分支和DFS算法
　 65　 参考文献和读物

第7章　 回溯
　 71　 一般方法
　 72　 8皇后问题
　 73　 子集求和问题
　 74　 图的着色
　 75　 哈密顿回路
　 76　 背包问题
　 77　 参考文献和读物
　 78　 附加习题

第8章　 分支限界法
　 81　 一般方法
　　　811　 最小代价查找
　　　812　 15拼板： 一个例子
　　　813　 LC查找的控制抽象
　　　814　 限界
　　　815　 FIFO分支限界法
　　　816　 LC分支限界法
　 82　 0/1背包问题
　　　821　 LC分支限界法求解
　　　822　 FIFO分支限界法求解
　 83　 旅行商问题()
　 84　 效率因素
　 85　 参考文献和读物

第9章　 代数问题
　 91　 一般方法
　 92　 计算和插值
　 93　 快速傅里叶变换
　　　931　 FFT的原地版本
　　　932　 一些保留问题
　 94　 模运算
　 95　 更快的计算和插值
　 96　 参考文献和读物

第10章　 下界理论
　 101　 比较树
　　　1011　 有序查找
　　　1012　 排序
　　　1013　 选择
　 102　 喻示和对立论
　　　1021　 归并
　　　1022　 最大和次大
　　　1023　 状态空间方法
　　　1024　 选择
　 103　 通过规约求下界
　　　1031　 寻找凸包
　　　1032　 不相交集合问题
　　　1033　 即时中值查找
　　　1034　 三角矩阵相乘
　　　1035　 下三角矩阵求逆
　　　1036　 计算传递闭包
　 104　 解决代数问题的技术(*)
　 105　 参考文献和读物

第11章　 难与完全问题
　 111　 基本概念
　　　1111　 非确定性算法
　　　1112　 难和完全类
　 112　 Cook定理（*）
　 113　 难的图问题
　　　1131　 团判定问题
　　　1132　 节点覆盖判定问题
　　　1133　 色数判定问题
　　　1134　 有向哈密顿回路（*）
　　　1135　 旅行商判定问题
　　　1136　 与/或图判定问题
　 114　 难的调度问题
　　　1141　 调度相同的处理器
　　　1142　 流水作业调度
　　　1143　 作业安排调度
　 115　 难的代码生成问题
　　　1151　 带有公共子表达式的代码生成
　　　1152　 实现并行赋值指令
　 116　 一些简化的难问题
　 117　 参考文献和读物
　 118　 附加习题

第12章　 近似算法
　 121　 概述
　 122　 绝对近似
　　　1221　 平面图着色
　　　1222　 最多程序存储问题
　　　1223　 难的绝对近似

　 123　 ε近似
　　　1231　 独立任务的调度
　　　1232　 装箱问题
　　　1233　 难的ε近似问题
　 124　 多项式时间近似方案
　　　1241　 独立任务的调度
　　　1242　 0/1背包
　 125　 完全多项式时间近似方案
　　　1251　 舍入法
　　　1252　 区间划分法
　　　1253　 分割法
　 126　 概率上的好算法(*)
　 127　 参考文献和读物
　 128　 附加习题

第13章　 PRAM算法
　 131　 概述
　 132　 计算模型
　 133　 基本技术和算法
　　　1331　 前缀计算
　　　1332　 表排序
　 134　 选择
　　　1341　 使用n2个处理器选择最大值
　　　1342　 使用n个处理器选择最大值
　　　1343　 在整数中选择最大值
　　　1344　 使用n2个处理器的一般选择问题
　　　1345　 一个工作最优的随机算法(*)
　 135　 归并
　　　1351　 对数时间算法
　　　1352　 奇偶归并
　　　1353　 工作最优的算法
　　　1354　 O(log logm)时间算法
　 136　 排序
　　　1361　 奇偶归并排序
　　　1362　 随机选择算法
　　　1363　 Preparata算法
　　　1364　 Reischuk随机算法（*）
　 137　 图问题
　　　1371　 计算传递闭包的另一种算法
　　　1372　 每一对顶点之间的最短路径
　 138　 计算凸包
　 139　 下界
　　　1391　 平均情况下排序的下界
　　　1392　 寻找最大值
　 1310　 参考文献和读物
　 1311　 附加习题

第14章　 网格算法
　 141　 计算模型
　 142　 分组路由
　　　1421　 线性阵列中的分组路由
　　　1422　 网格上PPR的贪心算法
　　　1423　 具有小队列的随机算法
　 143　 基本算法
　　　1431　 广播
　　　1432　 前缀计算
　　　1433　 数据集中
　　　1434　 稀疏枚举排序
　 144　 选择
　　　1441　 n=p(*)时的随机算法
　　　1442　 n＞p(*)时的随机选择
　　　1443　 n＞p时的确定性算法
　 145　 归并
　　　1451　 在线性阵列上的顺序号归并
　　　1452　 线性阵列上的奇偶归并
　　　1453　 在网格上的奇偶归并
　 146　 排序
　　　1461　 在线性阵列上的排序
　　　1462　 在网格上的排序
　 147　 图问题
　　　1471　 传递闭包的n×n网格算法
　　　1472　 每一对顶点之间的最短路径
　 148　 计算凸包
　 149　 参考文献和读物
　 1410　 附加习题

第15章　 超立方体算法
　 151　 计算模型
　　　1511　 超立方体
　　　1512　 蝶形网络
　　　1513　 其他网络的嵌入
　 152　 PPR路由
　　　1521　 贪心算法
　　　1522　 随机算法
　 153　 基本算法
　　　1531　 广播
　　　1532　 前缀计算
　　　1533　 数据集中
　　　1534　 稀疏枚举排序
　 154　 选择
　　　1541　 n=p(*)时的随机算法
　　　1542　 n＞p(*)时的随机选择
　　　1543　 n＞p时的确定性算法
　 155　 归并
　　　1551　 奇偶归并
　　　1552　 双调谐归并
　 156　 排序
　　　1561　 奇偶归并排序
　　　1562　 双调谐排序
　 157　 图问题
　 158　 计算凸包
　 159　 参考文献和读物
　 1510　 附加习题
索引
　 ⅩⅣ