《算法设计与分析基础(第3版)》课后习题答案

《算法设计与分析基础（第3版）》是2015年清华大学出版社出版的一本书，作者是(美)莱维汀。

作者基于丰富的教学经验，开发了一套全新的算法分类方法。该分类法站在通用问题求解策略的高度，对现有大多数算法准确分类，从而引领读者沿着一条清晰、一致、连贯的思路来探索算法设计与分析这一迷人领域。本书作为第3版，相对前版调整了多个章节的内容和顺序，同时增加了一些算法，并扩展了算法的应用，使得具体算法和通用算法设计技术的对应更加清晰有序；各章累计增加了70道习题，其中包括一些有趣的谜题和面试问题。

目录

• 第1章绪论 1
• 1.1　什么是算法 2
• 习题1.1 6
• 1.2　算法问题求解基础 7
• 1.2.1理解问题 8
• 1.2.2　了解计算设备的性能 8
• 1.2.3　在精确解法和近似解法之间做出选择 9
• 1.2.4　算法的设计技术 9
• 1.2.5　确定适当的数据结构 9
• 1.2.6　算法的描述 10
• 1.2.7　算法的正确性证明 10
• 1.2.8　算法的分析 11
• 1.2.9　为算法写代码 12
• 习题1.2 13
• 1.3　重要的问题类型 14
• 1.3.1　排序 15
• 1.3.2　查找 16
• 1.3.3　字符串处理 16
• 1.3.4　图问题 16
• 1.3.5　组合问题 17
• 1.3.6　几何问题 17
• 1.3.7　数值问题 18
• 习题1.3 18
• 1.4　基本数据结构 20
• 1.4.1　线性数据结构 20
• 1.4.2　图 22
• 1.4.3　树 25
• 1.4.4　集合与字典 28
• 习题1.4 29
• 小结 30
• 第2章算法效率分析基础 32
• 2.1　分析框架 33
• 2.1.1输入规模的度量 33
• 2.1.2运行时间的度量单位 34
• 2.1.3增长次数 35
• 2.1.4算法的最优、最差和平均效率 36
• 2.1.5分析框架概要 38
• 习题2.1 39
• 2.2渐近符号和基本效率类型 40
• 2.2.1非正式的介绍 40
• 2.2.2符号O 41
• 2.2.3符号 42
• 2.2.4符号 42
• 2.2.5渐近符号的有用特性 43
• 2.2.6利用极限比较增长次数 44
• 2.2.7基本的效率类型 45
• 习题2.2 46
• 2.3非递归算法的数学分析 48
• 习题2.3 52
• 2.4递归算法的数学分析 54
• 习题2.4 59
• 2.5例题：计算第n个斐波那契数 62
• 习题2.5 65
• 2.6算法的经验分析 66
• 习题2.6 69
• 2.7算法可视法 70
• 小结 73
• 第3章蛮力法 75
• 3.1选择排序和冒泡排序 76
• 3.1.1选择排序 76
• 3.1.2冒泡排序 77
• 习题3.1 78
• 3.2顺序查找和蛮力字符串匹配 80
• 3.2.1顺序查找 80
• 3.2.2蛮力字符串匹配 81
• 习题3.2 82
• 3.3最近对和凸包问题的蛮力算法 83
• 3.3.1最近对问题 83
• 3.3.2凸包问题 84
• 习题3.3 87
• 3.4穷举查找 89
• 3.4.1旅行商问题 89
• 3.4.2背包问题 90
• 3.4.3分配问题 91
• 习题3.4 93
• 3.5深度优先查找和广度优先查找 94
• 3.5.1深度优先查找 94
• 3.5.2广度优先查找 96
• 习题3.5 98
• 小结 100
• 第4章减治法 101
• 4.1插入排序 103
• 习题4.1 105
• 4.2拓扑排序 106
• 习题4.2 109
• 4.3生成组合对象的算法 111
• 4.3.1生成排列 111
• 4.3.2生成子集 113
• 习题4.3 114
• 4.4减常因子算法 115
• 4.4.1折半查找 116
• 4.4.2假币问题 117
• 4.4.3俄式乘法 118
• 4.4.4约瑟夫斯问题 119
• 习题4.4 120
• 4.5减可变规模算法 122
• 4.5.1计算中值和选择问题 122
• 4.5.2插值查找 125
• 4.5.3二叉查找树的查找和插入 126
• 4.5.4拈游戏 127
• 习题4.5 128
• 小结 129
• 第5章分治法 131
• 5.1合并排序 133
• 习题5.1 135
• 5.2快速排序 136
• 习题5.2 140
• 5.3二叉树遍历及其相关特性 141
• 习题5.3 143
• 5.4大整数乘法和Strassen矩阵乘法 144
• 5.4.1大整数乘法 145
• 5.4.2Strassen矩阵乘法 146
• 习题5.4 148
• 5.5用分治法解最近对问题和凸包问题 149
• 5.5.1最近对问题 149
• 5.5.2凸包问题 151
• 习题5.5 153
• 小结 154
• 第6章变治法 155
• 6.1预排序 156
• 习题6.1 158
• 6.2高斯消去法 160
• 6.2.1LU分解 164
• 6.2.2计算矩阵的逆 165
• 6.2.3计算矩阵的行列式 166
• 习题6.2 167
• 6.3平衡查找树 168
• 6.3.1AVL树 169
• 6.3.22-3树 173
• 习题6.3 174
• 6.4堆和堆排序 175
• 6.4.1堆的概念 176
• 6.4.2堆排序 180
• 习题6.4 181
• 6.5　霍纳法则和二进制幂 182
• 6.5.1霍纳法则 182
• 6.5.2二进制幂 184
• 习题6.5 186
• 6.6　问题化简 187
• 6.6.1求最小公倍数 188
• 6.6.2计算图中的路径数量 189
• 6.6.3优化问题的化简 189
• 6.6.4线性规划 190
• 6.6.5简化为图问题 192
• 习题6.6 193
• 小结 194
• 第7章　时空权衡 196
• 7.1　计数排序 197
• 习题7.1 199
• 7.2　字符串匹配中的输入增强技术 200
• 7.2.1　Horspool算法 201
• 7.2.2　Boyer-Moore算法 204
• 习题7.2 207
• 7.3　散列法 209
• 7.3.1　开散列(分离链) 210
• 7.3.2　闭散列(开式寻址) 211
• 习题7.3 213
• 7.4　B树 214
• 习题7.4 217
• 小结 218
• 第8章　动态规划 219
• 8.1　三个基本例子 220
• 习题8.1 224
• 8.2　背包问题和记忆功能 226
• 8.2.1　背包问题 226
• 8.2.2　记忆化 227
• 习题8.2 229
• 8.3　最优二叉查找树 230
• 习题8.3 234
• 8.4　Warshall算法和Floyd算法 235
• 8.4.1　Warshall算法 235
• 8.4.2　计算完全最短路径的Floyd算法 238
• 习题8.4 241
• 小结 242
• 第9章　贪婪技术 243
• 9.1　Prim算法 245
• 习题9.1 249
• 9.2　Kruskal算法 250
• 习题9.2 255
• 9.3　Dijkstra算法 256
• 习题9.3 259
• 9.4　哈夫曼树及编码 260
• 习题9.4 264
• 小结 265
• 第10章　迭代改进 266
• 10.1　单纯形法 267
• 10.1.1线性规划的几何解释 267
• 10.1.2单纯形法概述 270
• 10.1.3单纯形法其他要点 275
• 习题10.1 276
• 10.2最大流量问题 278
• 习题10.2 285
• 10.3二分图的最大匹配 286
• 习题10.3 291
• 10.4稳定婚姻问题 292
• 习题10.4 295
• 小结 296
• 第11章　算法能力的极限 297
• 11.1　如何求下界 298
• 11.1.1　平凡下界 298
• 11.1.2　信息论下界 299
• 11.1.3　敌手下界 299
• 11.1.4　问题化简 300
• 习题11.1 302
• 11.2　决策树 302
• 11.2.1　排序的决策树 303
• 11.2.2　查找有序数组的决策树 305
• 习题11.2 306
• 11.3　P、NP和NP完全问题 308
• 11.3.1　P和NP问题 308
• 11.3.2　NP完全问题 311
• 习题11.3 314
• 11.4　数值算法的挑战 316
• 习题11.4 322
• 小结 323
• 第12章　超越算法能力的极限 325
• 12.1　回溯法 325
• 12.1.1　n皇后问题 326
• 12.1.2　哈密顿回路问题 328
• 12.1.3　子集和问题 328
• 12.1.4　一般性说明 329
• 习题12.1 331
• 12.2　分支界限法 332
• 12.2.1　分配问题 332
• 12.2.2　背包问题 335
• 12.2.3　旅行商问题 336
• 习题12.2 338
• 12.3　NP困难问题的近似算法 339
• 12.3.1　旅行商问题的近似算法 340
• 12.3.2　背包问题的近似算法 349
• 习题12.3 352
• 12.4　解非线性方程的算法 353
• 12.4.1　平分法 355
• 12.4.2　试位法 357
• 12.4.3　牛顿法 358
• 习题12.4 360
• 小结 361
• 跋 363
• 附录A算法分析的实用公式 366
• 附录B递推关系简明指南 369
• 习题提示 380
• 参考文献 414