本书是国际著名算法专家李德财教授主编的系列丛书Lecture Notes Series on Computing中的一本。本书涵盖了绝大多数算法设计中的一般技术， 在讲解每一种技术时， 阐述了它的应用背景， 注重用与其他技术相比较的方法说明它的特征， 并提供大量实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。全书分七部分共18 章， 从算法设计与算法分析的基本概念和方法入手， 先后介绍了递归、分治、动态规划、贪心算法、图的遍历等技术， 对NP 完全问题进行了基本但清晰的讨论。作者对概率算法、近似算法和计算几何这些发展迅猛的领域也用一定的篇幅讲述了基本内容。书中每章后都附有大量的练习， 有利于读者对书中内容的理解和应用。

修订版译者序 这本书的第一版在国内高校使用已超过20年了。感谢朱洪教授推荐了一本内容合适的教材， 为高校算法课程的教师提供了一个很好的教材选择。 在本书的修订版中， 内容组织结构有了较多的调整， 特别对新的发展趋势及算法应用领域进行了补充。 新版内容很适合国内相关课程的需要。本书只提及少量的数据结构概念， 避免了和数据结构课程内容的重叠。本书把阐述的重点放在了算法设计技术和算法分析方面。修订版增加了关于随机化的数学基础内容。部分内容调整具体列举如下： 附录A新增了数学基础知识； 附录B是全新的， 讨论了概率及统计的基本知识； 其他各章也有部分内容调整， 练习也连带有调整，比如第1章新增了1.15节“分治法递归式”， 丰富了算法分析的相关实例。另外， 随机算法中的内容也有所增加， 可以消除学生在了解新兴算法领域时的陌生感。 这本书内容全面， 取舍较好。对大学生参加ICPC竞赛有明显帮助。通过数年的观察对比， 学习完这本书的学生， 其分析与解决问题的能力明显增强， 并且竞赛成绩明显提升。这从实际效果上体现了本书具有完整性、合理性的优势, 并且也有助于提高学生将相关模型转化为算法的能力。 在翻译过程中， 译者想使中文内容表达准确、流畅、易于理解，但鉴于译者水平所限， 书中缺点乃至错误恐怕难以避免。欢迎各位专家及广大读者批评指正。 感谢并致敬本书上一版本的译者吴伟昶、方世昌老师及审校者朱洪老师， 感谢他们的辛苦付出。 曹霑懋 前 言 早在20世纪60年代初期， 最初的电子计算机用户开始注意程序的执行性能， 计算机算法领域随即活跃起来。在那个年代， 计算机的有限资源也促进了有效算法的设计。人们在这个领域进行了广泛的研究之后， 出现了大量解决不同问题的有效算法。属于一定问题类的不同问题之间的相似性产生了一般算法设计技术， 本书所强调的大多数算法设计技术在解决许多问题中已经证明是有用的。涵盖顺序算法设计中的最普遍技术是本书的一个尝试。对于每一种技术都通过如下方法表述： 首先， 叙述这种技术可以应用的场合； 其次， 总结出它的技术特点； 再次， 如果可能， 和其他技术进行比较； 最后也是最重要的， 通过把它应用在几个实际问题中来举例说明这种技术。 虽然本书的主题是算法设计技术， 但也强调了算法设计中的另一个重要组成部分： 算法分析。本书对大多数给出的算法进行了详细的分析。附录A给出了在算法分析中有用的数学基础知识， 第10章是计算复杂性领域的一个导论， 第11章论述了在求解各种问题时建立下界的基础。这几章在有效算法的设计中是不可缺少的。 本书论述的重点是设计技术的实际应用。每一种技术通过提供具备充足数据的求解某些问题的算法来说明， 这些问题通常出现在科学和工程的许多应用中。 在本书中， 算法的表现方式是比较直接的， 并且使用了与结构化程序设计语言的语法类似的伪代码， 例如ifthenelse、for和while结构。在需要时， 伪代码中混有说明性文字。利用说明性文字描述算法的一部分当然是有益的， 它可以使读者花费最少的时间来了解算法思想。但是有时用伪代码会使算法描述变得更简单和更形式化。例如， 赋值语句B［1…n］ ← A［1…n］的功能是， 对于1≤i≤n中的所有i， 用每个A［i］代替每个B［i］。利用for…end for结构， 或者用简洁的说明性文字， 都不会比这条赋值语句表述得更清楚和更简单。 本书分为七个部分， 每部分由相关的几章组成， 每章包含具有共同特征或相同主题的一些算法设计技术。第一部分是为本书的余下部分做准备的， 另外也提供了后面章节需要的背景材料。第二部分致力于递归设计技术的研究， 它是极其重要的， 因为这部分强调了计算机科学领域中的一个基本工具： 递归。第三部分涉及了两个直观和自然的设计技术：贪心算法和图的遍历。第四部分是关于研究“对于一个给定问题， 或者为这个问题提供一个有效算法， 或者证明它是难解的”所需要的一些技术。这部分包含了NP完全问题、计算复杂性和下界的相关内容。第五部分讨论了应对困难问题的技术， 这些技术包括回溯、随机化， 以及在合理的时间内寻找合理的可接受的近似解。第六部分利用两个受到高度关注的重要问题——寻找网络最大流及在无向图中寻找最大匹配， 介绍了迭代改进的概念， 以得出越来越有效的算法。最后， 第七部分介绍了一个快速发展的领域——计算几何。其中， 我们以这个领域中的重要问题作为例子， 讲解了广泛使用的几何扫描技术。在另外一章中， 讨论了Voronoi图解这个通用的工具， 并且讲述了它的一些应用。 本书可作为算法设计与分析课程的教材， 其中包含了可作为两学期算法课程的内容。第1章到第9章提供了大学本科三、四年级算法课程的核心材料， 有些内容可以略过， 如合并查找算法的平摊分析、稠图情况下的最短路径和最小生成树的线性时间算法。教师可能会发现， 加上后面章节的一些内容， 如回溯、随机算法、近似算法或几何扫描是很有用的。余下的内容可用于研究生的算法课程。 本书所要求的预备知识已经减到最少， 仅需要离散数学和数据结构的基本知识。 感谢King Fahd University of Petroleum ＆ Minerals(KFUPM)的支持和对手稿准备工作提供的帮助。本书的编写得到KFUPM的项目ics/algorithm/182的资助。我还要感谢那些认真阅读手稿各部分且提出许多有益建议的人， 包括一些在KFUPM学习算法课程的本科生和研究生。特别感谢S.Albassam、 H.Almuallim和S.Ghanta的珍贵评注。

目 录 第一部分 基本概念和算法导引第1章 算法分析基本概念 1.1 引言 1.2 历史背景 1.3 二分搜索 1.4 合并两个已排序的表 1.5 选择排序 1.6 插入排序 1.7 自底向上合并排序 1.8 时间复杂性 1.9 空间复杂性 1.10 最优算法 1.11 如何估计算法的运行时间 1.12 最坏情况和平均情况的分析 1.13 平摊分析 1.14 输入大小和问题实例 1.15 分治递推式 1.16 练习 1.17 参考注释第2章 数据结构 2.1 引言 2.2 链表 2.3 图 2.4 树 2.5 根树 2.6 二叉树 2.7 练习 2.8 参考注释第3章 堆和不相交集数据结构 3.1 引言 3.2 堆 3.3 不相交集数据结构 3.4 练习 3.5 参考注释 第二部分 基于递归的技术第4章 归纳法 4.1 引言 4.2 寻找多数元素 4.3 整数幂 4.4 多项式求值（Horner规则） 4.5 基数排序 4.6 生成排列 4.7 练习 4.8 参考注释第5章 分治 5.1 引言 5.2 二分搜索 5.3 合并排序 5.4 分治范式 5.5 选择： 寻找中项和第k小的元素 5.6 快速排序 5.7 多选 5.8 大整数乘法 5.9 矩阵乘法 5.10 最近点对问题 5.11 练习 5.12 参考注释第6章 动态规划 6.1 引言 6.2 最长公共子序列问题 6.3 矩阵链相乘 6.4 动态规划范式 6.5 所有点对的最短路径问题 6.6 背包问题 6.7 练习 6.8 参考注释 第三部分 最先割技术第7章 贪心算法 7.1 引言 7.2 最短路径问题 7.3 最小耗费生成树（Kruskal算法） 7.4 最小耗费生成树(Prim算法) 7.5 文件压缩 7.6 练习 7.7 参考注释第8章 图的遍历 8.1 引言 8.2 深度优先搜索 8.3 深度优先搜索的应用 8.4 广度优先搜索 8.5 广度优先搜索的应用 8.6 练习 8.7 参考注释 第四部分 问题的复杂性第9章 NP完全问题 9.1 引言 9.2 P类 9.3 NP类 9.4 NP完全问题的分析 9.5 coNP类 9.6 三种复杂性类之间的关系 9.7 练习 9.8 参考注释第10章 计算复杂性引论 10.1 引言 10.2 计算模型：图灵机 10.3 k带图灵机和时间复杂性 10.4 离线图灵机和空间复杂性 10.5 带压缩和线性加速 10.6 复杂性类之间的关系 10.7 归约 10.8 完全性 10.9 多项式时间层次 10.10 练习 10.11 参考注释第11章 下界 11.1 引言 11.2 平凡下界 11.3 决策树模型 11.4 代数决策树模型 11.5 线性时间归约 11.6 练习 11.7 参考注释 第五部分 克服困难性第12章 回溯法 12.1 引言 12.2 3着色问题 12.3 8皇后问题 12.4 一般回溯法 12.5 分支限界法 12.6 练习 12.7 参考注释第13章 随机算法 13.1 引言 13.2 Las Vegas和Monte Carlo算法 13.3 两个简单的例子 13.4 随机快速排序 13.5 随机选择 13.6 占有问题 13.7 尾部界 13.8 Chernoff界的应用：多选 13.9 随机取样 13.10 最小割问题 13.11 测试串的相等性 13.12 模式匹配 13.13 素数测试 13.14 练习 13.15 参考注释第14章 近似算法 14.1 引言 14.2 基本定义 14.3 差界 14.4 相对性能界 14.5 多项式近似方案 14.6 完全多项式近似方案 14.7 练习 14.8 参考注释 第六部分 域指定问题的迭代改进第15章 网络流 15.1 引言 15.2 预备知识 15.3 FordFulkerson方法 15.4 最大容量增值 15.5 最短路径增值 15.6 Dinic算法 15.7 MPM算法 15.8 练习 15.9 参考注释第16章 匹配 16.1 引言 16.2 预备知识 16.3 二分图上的网络流方法 16.4 二分图的匈牙利树方法 16.5 一般图中的最大匹配 16.6 二分图的On2.5算法 16.7 练习 16.8 参考注释 第七部分 计算几何技术第17章 几何扫描 17.1 引言 17.2 一个简单的例子：计算点集中的极大点 17.3 几何预备知识 17.4 计算线段的交点 17.5 凸包问题 17.6 计算点集的直径 17.7 练习 17.8 参考注释第18章 Voronoi图解 18.1 引言 18.2 最近点Voronoi图解 18.3 Voronoi图解的应用 18.4 最远点Voronoi图解 18.5 最远点Voronoi图解的应用 18.6 练习 18.7 参考注释附录A 数学预备知识 附录B 离散概率简介 参考文献