1.1 问题、算法和程序 1
第1章 基本概念 1
1.2 表述算法的方法 2
1.3 伪代码的语法规则 3
习题 6
第2章 数学预备知识 7
2.1 集合、函数关系 7
2.1.1 集合的表示 7
2.1.2 集合的子集 8
2.1.3 集合的运算 8
2.1.4 序列和多元组 8
2.2 函数关系 9
2.2.3 等价关系 10
2.3 布尔逻辑 10
2.2.2 二元关系的性质 10
2.2.1 二元关系 10
2.4 证明 11
2.4.1 直接证明法 11
2.4.2 间接证明 11
2.4.3 反证法 11
2.4.4 反例证明法 12
2.4.5 数学归纳法 12
2.5 取下整和取上整函数 13
2.6 取模运算 14
2.7 对数 14
2.8 级数求和 14
2.9 求和运算法则 15
2.10 用定积分解求和式的近似值 15
2.11 阶乘函数和二项式系数 16
2.11.1 阶乘 16
2.11.2 二项式系数 16
2.11.3 二项式定理 17
2.12 递推方程 19
2.12.1 常系数线性齐次递推式的求解 19
2.12.2 常系数线性非齐次递推方程的求解 21
2.12.3 扩展递推方程 22
2.12.4 用生成函数法求解递推关系 23
习题 26
第3章 算法复杂性分析 29
3.1 输入规模的度量 29
3.2 运行时间的度量单位 29
3.3 渐进符号基本增长率类型 33
3.3.1 上限 33
3.3.2 下限 33
3.3.3 Θ表示法 34
3.4 化简法则 34
3.5 非递归算法运行时间的计算 34
3.6 递归算法运行时间的计算 36
3.6.1 分治递归的定理方法 37
3.6.2 递归树的方法 38
3.7 算法的最佳、最差和平均复杂性 39
3.8 空间复杂性 41
习题 41
第4章 递归与迭代 45
4.1 递归 45
4.1.1 递归方法计算两个正整数相乘 45
4.1.2 递归方法计算阶乘函数 45
4.1.3 递归方法解全排列问题 46
4.2 迭代 48
4.2.1 迭代方法计算两个正整数相乘 48
4.2.2 迭代方法计算阶乘函数 48
4.2.3 迭代的方法解排列问题 48
4.3 梵天塔问题 49
4.3.1 递归方法解梵天塔问题 49
4.3.2 迭代方法解梵天塔问题 51
4.4.1 递归方法1解阿克曼函数 55
4.4 阿克曼函数 55
4.4.2 递归方法2解阿克曼函数 57
习题 57
第5章 递归与分形图形 59
5.1 递归与分形图形 59
5.2 涡旋曲线 59
5.3 康托（Cantor）三分集 60
5.4 谢尔宾斯基（Sierpinski）垫片 61
5.5 谢尔宾斯基（Sierpinski）地毯 62
5.6 科赫（Koch）曲线 64
习题 66
第6章 算法设计策略的比较与选择 68
6.1 求解斐波那契数列 68
6.1.1 时间复杂性为O(1.618)n+1递归算法 68
6.1.3 时间复杂性为O（n）、空间复杂性为O（l）迭代算法 69
6.1.2 时间和空间复杂性分别为O（n）迭代算法 69
6.1.4 时间复杂性为O（n）、空间复杂性为O（l）递归算法 70
6.1.5 时间复杂性为O（log n）、空间复杂性为O（l）递归算法1 70
6.1.6 时间复杂性为O（1og n）、空间复杂性为O（l）递归算法2 72
6.1.7 时间复杂性为O（1og n）、空间复杂性为O（l）递归算法3 73
6.2 最大子段和问题 74
6.2.1 时间复杂性为O（n3）算法1 74
6.2.2 时间复杂性为O（n3）算法2 75
6.2.3 时间复杂性为O（n2）算法 76
6.2.4 时间和空间复杂性分别为O（n2）算法1 76
6.2.5 时间和空间复杂性分别为O（n2）算法2 77
6.2.6 时间复杂性为O（n log n）算法 78
6.2.7 时间复杂性为O（n）算法 80
习题 80
第7章 排序 83
7.1 插入排序 83
7.2 起泡排序 84
7.3 选择排序 86
7.4 快速排序 88
7.5 归并排序 92
7.6 堆排序 95
7.7 计数排序 99
7.8 基数排序 102
7.9 排序问题的下限 104
习题 106
第8章 分治 109
8.1 求解数组中元素与x相等的个数 109
8.1.1 求解数组中元素与x相等的个数迭代算法 109
8.1.2 求解数组中元素与x相等的个数递归算法 109
8.1.3 求解数组中元素与x相等的个数分治递归算法 110
8.2 判断已排序数组中是否存在给定的元素x 110
8.2.2 判断已排序数组中是否存在给定的元素x分治递归算法 111
8.2.1 判断已排序数组中是否存在给定的元素x迭代算法 111
8.3 两个大整数相乘 112
8.3.1 两个大整数相乘迭代算法 112
8.3.2 两个大整数相乘分治递归算法1 113
8.3.3 两个大整数相乘分治递归算法2 115
8.3.4 两个大整数相乘分治递归算法3 116
8.3.5 两个大整数相乘分治递归算法4 116
8.4.1 两个矩阵相乘迭代算法 117
8.4 两个矩阵相乘 117
8.4.2 两个矩阵相乘分治递归算法1 118
8.4.3 两个矩阵相乘分治递归算法2 120
8.5 两个多项式乘积 121
8.5.1 两个多项式乘积迭代算法 122
8.5.2 两个多项式乘积分治递归算法1 123
8.5.3 两个多项式乘积分治递归算法2 124
习题 127
9.1.1 计算二项式系数递归算法 129
9.1 计算二项式系数 129
第9章 动态规划 129
9.1.2 计算二项式系数动态规划算法 130
9.2 正整数的分拆问题 132
9.2.1 正整数的分拆递归算法1 132
9.2.2 正整数的分拆递归算法2 134
9.2.3 正整数的分拆递归算法3 135
9.2.4 正整数拆分问题的上界 135
9.2.5 正整数拆分问题的下界 136
9.2.6 正整数的分拆动态规划算法 137
9.3 矩阵连乘问题 138
9.3.1 穷举法解矩阵连乘问题 139
9.3.2 递归方法解矩阵连乘问题 139
9.3.3 动态规划方法解矩阵连乘问题 142
9.4 最优二叉查找树 145
9.4.1 穷举法解最优二叉查找树 146
9.4.2 递归方法解最优二叉查找树 147
9.4.3 动态规划方法解最优二叉查找树 151
9.5 最长公共子序列问题 154
9.5.1 最长公共子序列递归算法 154
9.5.2 最长公共子序列动态规划算法 156
9.6 所有点对最短路径问题 157
9.6.1 所有点对最短路径递归算法 159
9.6.2 所有点对最短路径动态规划算法1 160
9.6.3 所有点对最短路径动态规划算法2 161
9.7 01背包问题 163
9.7.1 01背包递归算法 163
9.7.2 01背包动态规划算法 165
9.8 找零钱问题 168
9.8.1 找零钱递归算法 169
9.8.2 找零钱动态规划算法 170
习题 172
10.1 活动安排问题 175
第10章 贪心算法 175
10.2 分数背包问题 178
10.3 最短路径问题 180
10.4 最小生成树 182
10.4.1 prim算法 183
10.4.2 Kruskal算法 185
10.5 Huffman编码树 188
习题 192
第11章 回溯 194
11.1 八个皇后问题 194
11.2 旅行售货问题 198
11.3 01背包问题 201
11.4 子集合问题 202
11.4.1 子集合算法1 202
11.4.2 子集合算法2 203
11.4.3 子集合算法3 204
习题 205
12.1 15数字谜的问题 207
第12章 分支限界 207
12.2 分配任务问题 211
12.3 旅行售货问题 214
习题 216
13.1.1 寻找数组中最大元素迭代算法 217
13.1.2 寻找数组中最大元素递归算法 217
13.1 寻找数组中最大元素问题 217
第13章 寻找问题 217
13.1.3 寻找数组中最大元素分治递归算法 218
13.2 寻找数组中最小元素和最大元素问题 219
13.2.1 寻找数组中最小元素和最大元素迭代算法1 219
13.2.2 寻找数组中最小元素和最大元素迭代算法2 219
13.2.3 寻找数组中最小元素和最大元素分治递归算法 220
13.3 寻找数组中最大元素和次大元素问题 221
13.3.1 寻找数组中最大元素和次大元素锦标赛算法 221
13.4.1 寻找两个已排序数组的中位数算法1 223
13.4 寻找两个已排序数组的中位数问题 223
13.4.2 寻找两个已排序数组的中位数算法2 224
13.5 寻找两个已排序数组第k小元素问题 226
13.6 寻找数组中主元素问题 227
13.6.1 寻找数组中主元素算法1 227
13.6.2 寻找数组中主元素算法2 228
13.6.3 寻找数组中主元素算法3 228
13.7 选择数组中项和第k小元素问题 229
13.7.1 选择数组中项和第k小元素算法 229
13.7.2 划分元素5个为一组选择算法的时间复杂性 233
13.7.3 划分元素7个为一组选择算法的时间复杂性 235
13.7.4 划分元素3个为一组选择算法的时间复杂性 235
13.8 模式串匹配 235
13.8.1 直接匹配算法 236
13.8.2 模式匹配的一种改进算法 238
习题 241
14.1.1 x进制数相加算法 244
第14章 算术运算、数值算法 244
14.1 加法 244
14.1.2 二进制数相加算法 245
14.2 减法 246
14.2.1 x进制数相减算法 246
14.2.2 二进制数相减算法 247
14.3 乘法 249
14.3.1 x进制数相乘算法 249
14.3.2 二进制数相乘算法 250
14.4 除法 251
14.4.1 x进制数相除算法 251
14.4.2 二进制数相除算法 252
14.5 整数幂 253
14.5.1 整数幂迭代算法 253
14.5.2 整数幂递归算法 253
14.6 二进制幂 254
14.5.3 整数幂分治迭代算法 254
14.5.4 整数幂分治递归算法 254
14.7 模取幂运算 255
14.8 模取二进制幂运算 256
14.9 多项式的快速求值 257
14.9.1 多项式求值算法1 257
14.9.2 多项式求值算法2 258
14.9.3 伯恩斯坦（Bernstein）多项式求值 259
习题 259
第15章 数论算法 262
15.1 最大公约数问题 262
15.1.1 最大公约数迭代算法1 262
15.1.2 最大公约数迭代算法2 262
15.1.3 最大公约数迭代算法3 263
15.1.4 最大公约数递归算法 263
15.3.1 扩展欧几里得递归算法 264
15.3 扩展欧几里得算法 264
15.2 求最小公倍数 264
15.3.2 扩展欧几里得迭代算法 265
15.4 素性检测 267
15.4.1 素性检测算法1 267
15.4.2 素性检测算法2 267
15.4.3 爱拉托斯散（Eratosthenes）筛选算法 268
15.4.4 素性检测算法3 269
15.4.5 素性检测算法4 269
15.4.6 素性检测算法5 270
15.4.7 素性检测算法6 270
15.5 RSA算法 272
15.5.1 欧拉定理 272
15.5.2 RSA加密与解密算法 273
习题 274
主要参考文献 276