算法分析与设计

第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