算法分析与设计

第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
〖1〗算法分析与设计目录〖3〗〖3〗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