本书是一部设计与分析领域的经典著作,着重介绍了计算机算法设计
领域的基本原则和根本原理。书中深入分析了一些计算机模型上的算法,
介绍了一些和设计有效算法有关的数据结构和编程技术,为读者提供了有
关递归方法、分治方法和动态规划方面的详细实例和实际应用,并致力于
更有效算法的设计和开发。同时,对NP完全等问题能否有效求解进行了分
析,并探索了应用启发式算法解决问题的途径。另外,本书还提供了大量
富有指导意义的习题。
本书可以作为高等院校计算机算法设计与分析课程的本科生或研究生
教材,也可以作为计算机理论研究人员、计算机算法设计人员的参考书。

出版者的话
译者序
前言
第1章计算模型
1.1算法和复杂度
1.2随机存取计算机
1.3RAM程序的计算复杂度
1.4存储程序模型
1.5RAM的抽象
1.6一种基本的计算模型:图灵机
1.7图灵机模型和RAM模型的关系
1.8简化ALGOL——一种**语言
第2章有效算法的设计
2.1数据结构:表、队列和堆栈
2.2集合的表示
2.3图
2.4树
2.5递归
2.6分治法
2.7平衡
2.8动态规划
2.9后记
第3章排序和顺序统计
3.1排序问题
3.2基数排序
3.3比较排序
3.4堆排序——O(nlogn)的比较排序算法
3.5快速排序——期望时间为O(nlogn)的排序算法
3.6顺序统计学
3.7顺序统计的期望时间
第4章集合操作问题的数据结构
4.1集合的基本操作
4.2散列法
4.3二分搜索
4.4二叉查找树
4.5*优二叉查找树
4.6简单的不相交集合合并算法
4.7UNION-FIND问题的树结构
4.8UNION-FIND算法的应用和扩展
4.9平衡树方案
4.10字典和优先队列
4.11可合并堆
4.12可连接队列
4.13划分
4.14本章小结
第5章图算法
5.1*小代价生成树
5.2深度优先搜索
5.3双连通性
5.4有向图的深度优先搜索

5.5强连通性
5.6路径查找问题
5.7传递闭包算法
5.8*短路径算法
5.9路径问题与矩阵乘法
5.10单源问题
5.11有向无环图的支配集:概念整合
第6章矩阵乘法及相关操作
6.1基础知识
6.2Strassen矩阵乘法算法
6.3矩阵求逆
6.4矩阵的LUP分解
6.5LUP分解的应用
6.6布尔矩阵的乘法
第7章快速傅里叶变换及其应用
7.1离散傅里叶变换及其逆变换
7.2快速傅里叶变换算法
7.3使用位操作的FFT
7.4多项式乘积
7.5Schonhage-Strassen整数相乘算法
第8章整数与多项式计算
8.1整数和多项式的相似性
8.2整数的乘法和除法
8.3多项式的乘法和除法
8.4模算术
8.5多项式模算术和多项式计值
8.6中国余数
8.7中国余数和多项式的插值
8.8*大公因子和欧几里得算法
8.9多项式GCD的渐近快速算法
8.10整数的GCD
8.11再论中国余数
8.12稀疏多项式
第9章模式匹配算法
9.1有穷自动机和正则表达式
9.2正则表达式的模式识别
9.3子串识别
9.4双向确定型下推自动机
9.5位置树和子串标识符
第10章NP完全问题
10.1非确定型图灵机问题
10.2P类和NP类
10.3语言和问题
10.4可满足性问题的NP完全性
lO.5其他NP完全问题
10.6多项式空间界问题
第11章一些可证难的问题
11.1复杂度层次
11.2确定型图灵机的空间层次
11.3一个需要指数时间和空问的问题

11.4一个非基本的问题
第12章算术运算的下界
12.1域
12.2再论直线状代码
12.3问题的矩阵表述
12.4面向行的矩阵乘法的下界
12.5面向列的矩阵乘法的下界
12.6面向行和列的矩阵乘法的下界
12.7预处理
附录算法的C/C++代码
参考文献