内容简介

本书主要介绍经典的算法设计技术，包括递归与分治策略、动态规划法、贪心算法、回溯法、分支限界法、概率算法等。在算法分析方面，介绍了二分搜索技术、大整数的乘法、Strassen矩阵乘法、棋盘覆盖、合并排序、快速排序、循环赛日程表、矩阵连乘问题、最长公共子序列、凸多边形最优三角剖分、多边形游戏、图像压缩、活动安排问题、最优装载、哈夫曼编码、最小生成树问题、套利问题、n皇后问题、图的m着色问题、15谜问题、单源最短路径问题、旅行商问题等，并对有的问题进行算法优化设计。书中主要突出对问题本身的分析和求解方法，并进行了问题的计算复杂性分析。本书每章均精选了一些基础的算法习题,针对各章节不同的算法设计技术设计了多个上机实验，并提供多套自测试卷,有助于学生了解自己对学习内容的掌握程度,自测学习效果。

本书可作为大学计算机科学与技术、软件工程等专业本科生的教学用书，也可作为从事实际问题求解的算法设计与分析工作人员的参考书。

编辑推荐

可作为大学计算机科学与技术、软件工程等专业本科生的教学用书，本书每章后精选了一些基础的算法习题,针对各章节不同的算法设计技术，设计了多个上机实验，并提供多套自测试卷,有助于学生了解自己对学习内容的掌握程度,自测学习效果。

目录

第1章算法概述/1

1.1什么是算法1

1.2算法复杂性2

1.3算法复杂性计量3

1.4算法复杂性的表示4

1.4.1算法复杂性的渐近性态4

1.4.2复杂性渐近阶5

1.4.35个渐近意义下的记号 5

1.4.4常见的算法时间复杂度6

1.5算法复杂性的重要性7

习题18

第2章递归与分治策略 /11

2.1递归的概念11

2.2分治法的基本思想16

2.3二分搜索技术18

2.3.1线性查找18

2.3.2二分搜索法18

2.3.3二分搜索算法复杂性最坏情形分析19

2.3.4二分搜索算法复杂性平均情形分析20

2.4大整数的乘法20

2.4.1大整数乘积的分治算法描述20

2.4.2大整数乘积的时间复杂度递推方程21

2.5Strassen矩阵乘法21

2.5.1Strassen矩阵分治乘法21

2.5.2时间复杂度递推方程22

2.6棋盘覆盖问题22

2.6.1问题描述22

2.6.2算法复杂性分析25

2.7合并排序25

2.7.1基于比较的排序时间复杂度下界25

2.7.2用递归树解递归关系式26

2.7.3合并排序27

2.8快速排序30

2.8.1算法描述30

2.8.2时间复杂度分析32

2.9循环赛日程表安排32

2.9.1问题描述32

2.9.2问题的分治法设计思想33

2.9.3分治算法实现33

习题234

第3章动态规划法/41

3.1动态规划法概述41

3.1.1最优性原理41

3.1.2动态规划法的基本步骤41

3.2矩阵连乘问题45

3.2.1问题描述45

3.2.2分析最优解的结构47

3.2.3建立递归关系47

3.2.4计算最优值48

3.2.5构造最优解49

3.3动态规划算法的基本要素50

3.3.1最优子结构50

3.3.2重叠子问题50

3.3.3备忘录方法52

3.4最长公共子序列问题53

3.4.1问题描述53

3.4.2最长公共子序列的结构54

3.4.3子问题的递归结构54

3.4.4计算最优值55

3.4.5构造最长公共子序列56

3.4.6算法的改进57

3.5凸多边形的最优三角剖分问题57

3.5.1问题描述57

3.5.2三角剖分的结构及其相关问题58

3.5.3最优子结构性质60

3.5.4最优三角剖分对应的权的递归结构60

3.5.5计算最优值60

3.5.6构造最优三角剖分61

3.6多边形游戏61

3.6.1问题描述61

3.6.2最优子结构性质 62

3.6.3递归求解63

3.6.4算法描述63

3.7图像压缩65

3.7.1图像压缩实例65

3.7.2最优子结构性质67

3.7.3递归计算最优值67

3.7.4算法实现68

习题370

第4章贪心算法/74

4.1活动安排问题74

4.1.1贪心算法设计的特点74

4.1.2问题描述74

4.1.3活动安排问题的贪心算法 75

4.2贪心算法的基本要素76

4.2.1贪心选择性质76

4.2.2最优子结构性质77

4.2.3贪心算法的求解过程77

4.2.4贪心算法与动态规划法的差异78

4.3最优装载79

4.3.1问题描述79

4.3.2贪心选择性质79

4.3.3最优子结构性质80

4.3.4算法描述80

4.4最短路径问题80

4.4.1问题描述80

4.4.2算法基本思想81

4.4.3算法实现82

4.5哈夫曼编码84

4.5.1哈夫曼树84

4.5.2构造一棵哈夫曼树86

4.5.3哈夫曼编码87

4.5.4算法分析与设计89

4.5.5哈夫曼算法的正确性91

4.6TSP问题92

4.6.1TSP问题研究进展92

4.6.2最近邻点贪心策略93

4.6.3最短链接贪心策略95

4.7最小生成树96

4.7.1Prim算法（最近顶点策略）96

4.7.2Kruskal算法（最短边策略）97

4.8套利问题98

4.8.1套利问题描述98

4.8.2问题的贪心选择性质99

4.8.3问题的最优子结构性质99

4.8.4算法实例99

习题4101

第5章回溯法/107

5.1回溯法的算法框架107

5.1.1明确定义问题的解空间107

5.1.2运用回溯法解题的步骤108

5.1.3回溯法的算法框架108

5.2n皇后问题110

5.2.1问题描述110

5.2.2算法设计110

5.2.3算法实现111

5.2.48皇后问题的不等效解分析与实现111

5.3图的m着色问题117

5.3.1问题描述117

5.3.2算法实现119

5.4回溯法的效率分析120

5.4.1重排原理120

5.4.2估算结点数120

5.4.3回溯法的效率122

习题5122

第6章分支限界法/127

6.1分支限界法的基本思想127

6.2分支限界法的算法实例128

6.2.1分支限界法解01背包问题128

6.2.2分支限界法解旅行商问题130

6.2.3分支限界法解15谜问题132

6.3单源最短路径问题136

6.3.1问题描述136

6.3.2算法分析136

6.3.3分支限界算法实现137

6.4装载问题141

6.4.1队列式分支限界法141

6.4.2算法的改进143

6.4.3构造最优解143

6.4.4最大收益分支限界（优先队列式）144

习题6145

第7章概率算法/147

7.1随机数147

7.2数值概率算法152

7.2.1用随机投点法计算π值152

7.2.2计算定积分154

7.2.3解非线性方程158

7.2.4解非线性方程组160

7.3蒙特卡罗算法170

7.3.1蒙特卡罗算法的基本思想170

7.3.2蒙特卡罗算法的简单应用171

7.3.3主元素问题174

7.3.4素数测试176

7.4拉斯维加斯算法181

7.4.1n皇后问题181

7.4.2整数因子分解187

7.5舍伍德算法188

7.5.1线性时间选择算法189

7.5.2跳跃表191

习题7193

第8章实验指导/195

实验1分治法上机实验195

实验11棋盘覆盖问题的分治法设计195

实验12利用分治法实现合并排序197

实验13用分治法实现快速排序算法200

实验14循环赛日程表安排问题的分治法设计201

实验15最大子段和问题的分治法设计203

实验2动态规划法上机实验204

实验21矩阵连乘问题的动态规划法设计205

实验22最长公共子序列的动态规划法设计207

实验23图像压缩问题的动态规划法设计208

实验3贪心算法上机实验213

实验31找硬币问题的贪心算法设计214

实验32活动安排问题的贪心算法215

实验33单源最短路径问题的贪心算法设计216

实验4回溯法上机实验219

实验418皇后问题的回溯法设计219

实验42图的着色问题的回溯法设计222

第9章算法自测卷/225

9.1算法自测卷1225

9.2算法自测卷2226

9.3算法自测卷3231

附录习题参考答案/234

习题1参考答案234

习题2参考答案235

习题3参考答案237

习题4参考答案241

习题5参考答案246

习题6参考答案248

习题7参考答案252

算法自测卷1参考答案266

算法自测卷2参考答案268

算法自测卷3参考答案272