本书是国际著名算法专家李德财教授主编的系列丛书Lecture Notes Series on Computing中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。对概率算法、近似算法和计算几何这些近年来发展迅猛的领域也用一定的篇幅讲述了基本内容。书中每章后都附有大量的练习题，有利于读者对书中内容的理解和应用。
本书结构简明，内容丰富，适合于作为计算机学科及相关学科算法课程的教材和参考书，尤其适宜于学过数据结构和离散数学课程之后的算法课程教材。同时也可作为从事算法研究的一本好的入门书。
目录
- 第一部分 基本概念和算法导引
- 第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章 算法分析基本概念
- 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 参考注释
- 第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 树
- 3.5 根树
- 3.6 二叉树
- 3.7 练习
- 3.8 参考注释
- 第4章 堆和不相交集数据结构
- 4.1 引言
- 4.2 堆
- 4.3 不相交集数据结构
- 4.4 练习
- 4.5 参考注释
- 第二部分 基于递归的技术
- 第5章 归纳法
- 5.1 引言
- 5.2 两个简单的例子
- 5.3 基数排序
- 5.4 整数幂
- 5.5 多项式求值（Horner规则）
- 5.6 生成排列
- 5.7 寻找多数元素
- 5.8 练习
- 5.9 参考注释
- 第6章 分治
- 6.1 引言
- 6.2 二分搜索
- 6.3 合并排序
- 6.4 分治范式
- 6.5 寻找中项和第k小元素
- 6.6 快速排序
- 6.7 大整数乘法
- 6.8 矩阵乘法
- 6.9 最近点对问题
- 6.10 练习
- 6.11 参考注释
- 第7章 动态规划
- 7.1 引言
- 7.2 最长公共子序列问题
- 7.3 矩阵链相乘
- 7.4 动态规划范式
- 7.5 所有点对的最短路径问题
- 7.6 背包问题
- 7.7 练习
- 7.8 参考注释
- 第三部分 最先割技术
- 第8章 贪心算法
- 8.1 引言
- 8.2 最短路径问题
- 8.3 最小耗费生成树（Kruskal算法）
- 8.4 最小耗费生成树（Prim算法）
- 8.5 文件压缩
- 8.6 练习
- 8.7 参考注释
- 第9章 图的遍历
- 9.1 引言
- 9.2 深度优先搜索
- 9.3 深度优先搜索的应用
- 9.4 广度优先搜索
- 9.5 广度优先搜索的应用
- 9.6 练习
- 9.7 参考注释第四部分问题的复杂性
- 第10章 NP完全问题
- 10.1 引言
- 10.2 P类
- 10.3 NP类
- 10.4 NP完全问题
- 10.5 co-NP类
- 10.6 NPI类
- 10.7 四种类之间的关系
- 10.8 练习
- 10.9 参考注释
- 第11章 计算复杂性引论
- 11.1 引言
- 11.2 计算模型：图灵机
- 11.3 k带图灵机和时间复杂性
- 11.4 离线图灵机和空间复杂性
- 11.5 带压缩和线性增速
- 11.6 复杂性类之间的关系
- 11.7 归约
- 11.8 完全性
- 11.9 多项式时间层次
- 11.10 练习
- 11.11 参考注释
- 第12章 下界
- 12.1 引言
- 12.2 平凡下界
- 12.3 决策树模型
- 12.4 代数决策树模型
- 12.5 线性时间归约
- 12.6 练习
- 12.7 参考注释第五部分克服困难性
- 第13章 回溯法
- 13.1 引言
