算法分析与设计

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

本书主要介绍经典的算法设计技术，包括递归与分治策略、动态规划法、贪心算法、回溯法、分支限界法、概率算法等。在算法分析方面，介绍了二分搜索技术、大整数的乘法、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
……