算法设计与分析(第3版

第1篇 算法设计与分析的基本概念 第1章 算法的基本概念 2
1.1 引言 2
1.1.1算法的定义和特征 2
1.1.2算法设计的例子——穷举法 4
1.1.3算法的复杂性分析 7
1.2 算法的时间复杂性 8
1.2.1算法的输入规模和运行时间的阶 8
1.2.2运行时间的上界——O记号 11
1.2.3运行时间的下界——Ω记号 12
1.2.4运行时间的准确界——Θ记号 13
1.2.5O记号、Ω记号、Θ记号的性质 17
1.2.6复杂性类型和o记号 18
习题 19
参考文献 20
第2章 算法的复杂性分析 21
2.1 常用的函数和公式 21
2.1.1整数函数 21
2.1.2对数函数 22
2.1.3排列、组合和二项式系数 23
2.1.4级数求和 24
2.2 算法的时间复杂性分析 25
2.2.1循环次数的统计 26
2.2.2基本操作频率的统计 29
2.2.3计算步的统计 32
2.3 情况、 坏情况和平均情况分析 33
2.3.1情况、 坏情况和平均情况 33
2.3.2情况和 坏情况分析 34
2.3.3平均情况分析 37
2.4 用生成函数求解递归方程40
2.4.1生成函数及其性质 40
2.4.2用生成函数求解递归方程 43
2.5 用特征方程求解递归方程46
2.5.1k阶常系数线性齐次递归方程 47
2.5.2k阶常系数线性非齐次递归方程 49
2.6 用递推方法求解递归方程51
2.6.1递推 52
2.6.2用递推法求解变系数递归方程 52
2.6.3换名 54
2.7 算法的空间复杂性 56
2.8 算法 57
习题 58
参考文献 60
第2篇 算法设计的基本技术
第3章 排序问题和离散集合的操作62
3.1 合并排序 62
3.1.1合并排序算法的实现 62
3.1.2合并排序算法的分析 64
3.2 基于堆的排序 65
3.2.1堆 66
3.2.2堆的操作 67
3.2.3堆的建立 70
3.2.4堆的排序 73
3.3 基数排序 74
3.3.1基数排序算法的思想方法 74
3.3.2基数排序算法的实现 76
3.3.3基数排序算法的分析 78
3.4 离散集合的Union_Find操作 79
3.4.1用于Union_Find操作的数据结构 79
3.4.2union、find操作及路径压缩 81
习题 84
参考文献 85
第4章 递归和分治 86
4.1 基于归纳的递归算法 86
4.1.1基于归纳的递归算法的思想方法 86
4.1.2递归算法的例子 87
4.1.3排列问题的递归算法 91
4.1.4求数组主元素的递归算法 95
4.1.5整数划分问题的递归算法 98
4.2 分治法 100
4.2.1分治法的例子 100
4.2.2分治法的设计原理 104
4.2.3快速排序 111
4.2.4多项式乘积和大整数乘法 116
4.2.5平面点集 接近点对问题 123
4.2.6选择问题 130
4.2.7残缺棋盘问题 136
习题 141
参考文献 143
第5章 贪婪法 145
5.1 贪婪法概述 146
5.1.1贪婪法的设计思想 146
5.1.2贪婪法的例子——货郎担问题 147
5.2 背包问题 148
5.2.1背包问题贪婪算法的实现 148
5.2.2背包问题贪婪算法的分析 150
5.3 单源 短路径问题 151
5.3.1解 短路径的狄斯奎诺算法 151
5.3.2狄斯奎诺算法的实现 153
5.3.3狄斯奎诺算法的分析 155
5.4 花费生成树问题 156
5.4.1花费生成树概述 156
5.4.2克鲁斯卡尔算法 157
5.4.3普里姆算法 161
5.5 霍夫曼编码问题 165
5.5.1前缀码和二叉树 165
5.5.2霍夫曼编码的实现 169
习题 171
参考文献 173
第6章 动态规划 174
6.1 动态规划的思想方法 174
6.1.1动态规划的决策原理 174
6.1.2动态规划实例——货郎担问题 175
6.2 多段图的 短路径问题177
6.2.1多段图的决策过程 178
6.2.2多段图动态规划算法的实现 180
6.3 资源分配问题 181
6.3.1资源分配的决策过程 182
6.3.2资源分配算法的实现 184
6.4 设备更新问题 187
6.4.1设备更新问题的决策过程 187
6.4.2设备更新算法的实现 190
6.5 公共子序列问题 192
6.5.1公共子序列的搜索过程 192
6.5.2公共子序列算法的实现 195
6.60/1背包问题 196
6.6.10/1背包问题的求解过程 196
6.6.20/1背包问题的实现 198
6.7RNA碱基对匹配问题 199
6.7.1RNA碱基对匹配的搜索过程 200
6.7.2RNA碱基对匹配算法的实现 203
习题 205
参考文献 207
第7章 回溯 208
7.1 回溯法的思想方法 208
7.1.1问题的解空间和状态空间树 208
7.1.2状态空间树的动态搜索 209
7.1.3回溯法的一般性描述 211
7.2n皇后问题 213
7.2.1n皇后问题的求解过程 213
7.2.2n皇后问题算法的实现 215
7.3 图的着色问题 217
7.3.1图着色问题的求解过程 218
7.3.2图的m着色问题算法的实现 220
7.4 哈密尔顿回路问题 222
7.4.1哈密尔顿回路的求解过程 222
7.4.2哈密尔顿回路算法的实现 224
7.50/1背包问题 225
7.5.1回溯法解0/1背包问题的求解过程 226
7.5.2回溯法解0/1背包问题算法的实现 229
7.6 回溯法的效率分析 231
习题 234
参考文献 235
第8章 分支与限界 236
8.1 分支与限界法的基本思想236
8.2 作业分配问题 238
8.2.1分支限界法解作业分配问题的思想方法 238
8.2.2分支限界法解作业分配问题算法的实现 241
8.3 单源 短路径问题 244
8.3.1分支限界法解单源 短路径问题的思想方法 244
8.3.2分支限界法解单源 短路径问题算法的实现 246
8.40/1背包问题 248
8.4.1分支限界法解0/1背包问题的思想方法和求解过程 249
8.4.20/1背包问题分支限界算法的实现 251
8.5 货郎担问题 254
8.5.1费用矩阵的特性及归约 254
8.5.2界限的确定和分支的选择 256
8.5.3货郎担问题的求解过程 259
8.5.4几个辅助函数的实现 262
8.5.5货郎担问题分支限界算法的实现 268
习题 271
参考文献 272
第9章 算法 273
9.1 算法概述 273
9.1.1算法的类型 273
9.1.2数发生器 274
9.2 舍伍德算法 275
9.2.1快速排序算法 275
9.2.2选择算法 277
9.3 拉斯维加斯算法 280
9.3.1字符串匹配 280
9.3.2整数因子 284
9.4 蒙特卡罗算法 285
9.4.1数组的主元素问题 285
9.4.2素数测试 287
习题 290
参考文献 291
第3篇 计算机应用领域的一些基法
0章 图和网络问题 294
10.1图的遍历 294
10.1.1图的深度优先搜索遍历 294
10.1.2图的广度优先搜索遍历 299
10.1.3无向图的接合点 301
10.1.4有向图的强连通分支 305
10.2网络流 308
10.2.1网络流的概念 308
10.2.2Ford_Fulkerson方法和容量增广 312
10.2.3 短路径增广 315
10.3二分图的匹配问题 320
10.3.1预备知识 321
10.3.2二分图匹配的匈牙利树方法 323
习题 329
参考文献 331
1章 计算几何问题 332
11.1引言 332
11.2平面线段的交点问题 334
11.2.1寻找平面线段交点的思想方法 335
11.2.2寻找平面线段交点的实现 337
11.3凸壳问题 342
11.3.1凸壳问题的格雷厄姆扫描法 343
11.3.2格雷厄姆扫描法的实现 344
11.4平面点集的直径问题 346
11.4.1求取平面点集直径的思想方法 346
11.4.2平面点集直径的求取 348
习题 350
参考文献 351
第4篇 算法设计与分析的一些理论问题
2章 NP完全问题 354
12.1P类和NP类问题 355
12.1.1P类问题 355
12.1.2NP类问题 356
12.2NP完全问题 358
12.2.1NP完全问题的定义 358
12.2.2几个典型的NP完全问题 360
12.2.3其他NP完全问题 366
12.3co_NP类和NPI类问题 366
习题 369
参考文献 370
3章 计算复杂性 371
13.1计算模型 371
13.1.1图灵机的基本模型 371
13.1.2k带图灵机和时间复杂性 374
13.1.3离线图灵机和空间复杂性 376
13.1.4可满足性问题和Cook定理 379
13.2复杂性类型之间的关系 381
13.2.1时间复杂性和空间复杂性的关系 382
13.2.2时间谱系定理和空间谱系定理 384
13.2.3填充变元 389
13.3归约性关系 391
13.4完备性 394
13.4.1NLOGSPACE完全问题 394
13.4.2PSPACE完全问题和P完全问题 396
习题 397
参考文献 398
4章 下界 399
14.1平凡下界 399
14.2判定树模型 399
14.2.1检索问题 400
14.2.2排序问题 401
14.3代数判定树模型 402
14.3.1代数判定树模型及下界定理 402
14.3.2极点问题 404
14.4线性时间归约 405
14.4.1凸壳问题 406
14.4.2多项式插值问题 406
习题 408
参考文献 408
5章 近似算法 409
15.1近似算法的性能 409
15.2装箱问题 410
15.2.1首次适宜算法 411
15.2.2 适宜算法及其他算法 412
15.3顶点覆盖问题 414
15.4货郎担问题 416
15.4.1欧几里得货郎担问题 417
15.4.2一般的货郎担问题 419
15.5多项式近似方案 419
15.5.10/1背包问题的多项式近似方案 420
15.5.2子集求和问题的完全多项式近似方案 423
习题 425
参考文献 426
参考文献 427