第1章 绪论 1
1.1 什么是算法 1
1.1.1 算法的由来 1
1.1.2 算法的发展 3
1.1.3 算法的例子 4
1.2 重要的问题类型 5
1.2.1 排序 6
1.2.2 查找 6
1.2.3 字符串匹配 6
1.2.4 图问题 7
1.2.5 组合问题 7
1.2.6 几何问题 7
1.2.7 数值问题 8
1.3 基本数据结构 8
1.3.1 线性结构 8
1.3.2 树结构 8
1.3.3 图结构 9
1.3.4 集合 9
1.3.5 数据的物理结构 10
1.4 算法问题求解基础 10
1.4.1 算法求解框架 10
1.4.2 算法设计步骤 10
1.5 算法的表示 14
1.6 为什么学习算法 15
总结 16
习题1 16
第2章 算法效率分析基础 17
2.1 算法分析框架 17
2.1.1 算法分析概述 17
2.1.2 算法正确性分析 17
2.1.3 时空效率分析 17
2.1.4 算法分析过程 19
2.2 渐进符号和基本效率类型 20
2.2.1 三种渐进符号 20
2.2.2 渐进符号的特性 20
2.2.3 基本效率类型 21
2.3 非递归算法的数学分析方法 22
2.4 递归算法的数学分析 26
2.4.1 递归算法的数学分析方法 26
2.4.2 斐波那契数列 29
2.5 算法的其他分析方法 31
总结 32
习题2 32
第3章 蛮力法 33
3.1 概述 33
3.2 排序问题 35
3.2.1 选择排序 35
3.2.2 冒泡排序 36
3.3 查找问题 37
3.3.1 顺序查找 38
3.3.2 字符串匹配 38
3.4 几何问题 39
3.4.1 最近对问题 40
3.4.2 凸包问题 40
3.5 组合问题 42
3.5.1 旅行商问题 42
3.5.2 背包问题 44
总结 45
习题3 45
第4章 分治法 46
4.1 概述 46
4.2 分治法的基本策略及步骤 46
4.2.1 分治法的基本策略 46
4.2.2 分治法的基本步骤 47
4.3 排序问题 48
4.3.1 合并排序 48
4.3.2 快速排序 49
4.4 查找问题 51
4.4.1 折半查找 51
4.4.2 二叉树遍历及其相关特性 53
4.5 数值计算问题 54
4.5.1 大整数乘法 54
4.5.2 Strassen矩阵乘法 56
4.6 几何问题 58
4.6.1 用分治法解最近对问题 58
4.6.2 用分治法解凸包问题 59
4.7 分析分治法在安排循环赛中的应用 60
总结 62
习题4 62
第5章 分治策略变体——减治策略和变治策略 64
5.1 减治策略 64
5.1.1 插入排序 65
5.1.2 拓扑排序 67
5.1.3 生成组合对象的算法 68
5.1.4 减常因子算法 71
5.1.5 减可变规模算法 73
5.2 变治策略 75
5.2.1 排序问题 75
5.2.2 平衡查找树 80
5.2.3 霍纳法则和二进制幂 86
5.2.4 问题化简 88
总结 89
习题5 89
第6章 动态规划 91
6.1 概述 91
6.2 算法特点 93
6.2.1 备忘录方法 94
6.2.2 最优化原理 98
6.2.3 求解步骤 98
6.3 矩阵连乘问题 99
6.4 最长公共子序列 104
6.5 0-1背包问题 107
6.6 最大子段和 113
6.7 最优二叉查找树 116
总结 122
习题6 122
第7章 时空权衡技术 125
7.1 时空权衡策略 125
7.2 计数排序 126
7.3 字符串匹配 128
7.4 散列法 134
总结 139
习题7 139
第8章 贪心算法 141
8.1 概述 141
8.1.1 贪心算法的基本要素 142
8.1.2 贪心算法的求解过程 142
8.2 活动安排问题 143
8.3 背包问题 146
8.4 最小生成树问题 148
8.4.1 Prim算法 150
8.4.2 Kruskal算法 153
8.5 单源（点）最短路径问题 158
8.6 哈夫曼编码 162
总结 168
习题8 168
第9章 回溯法和分支限界法 171
9.1 回溯法 171
9.1.1 概述 171
9.1.2 子集和问题 176
9.1.3 n皇后问题 178
9.1.4 哈密顿回路 180
9.1.5 装载问题 182
9.2 分支限界法 186
9.2.1 概述 186
9.2.2 0-1背包问题 191
9.2.3 任务分配问题 194
9.2.4 多段图的最短路径问题 199
9.2.5 旅行商问题 204
总结 210
习题9 210
第10章 NP完全性理论 212
10.1 判定问题和最优化问题 212
10.2 P类问题 214
10.3 NP类问题 215
10.4 NP完全问题 216
10.5 典型的NP完全问题 218
10.6 其他NP完全问题 220
10.7 NP完全问题的计算机处理 221
总结 222
习题10 222
第11章 案例精选 223
11.1 果园篱笆问题 223
11.2 空中飞行管理问题 223
11.3 去数问题 224
11.4 极差问题 224
11.5 最优合并问题 225
11.6 在棋盘中实现从初始布局到目标布局的转变 226
11.7 商店购物问题 227
11.8 旅游预算问题 229
11.9 防卫导弹问题 231
11.10 钓鱼问题 232
11.11 胖男孩问题 234
11.12 护卫队问题 235
参考文献 237