第一部分 基础知识 3
第1章 算法设计基础 3
1.1算法的基本概念 3
1.1.1算法及其重要特性 3
1.1.2算法的描述方法 5
1.1.3算法设计的一般过程 6
1.2为什么要学习和研究算法 7
1.2.1算法在问题求解中的地位 8
1.2.2算法训练能够提高计算思维能力 10
1.2.3算法研究是推动计算机技术发展的关键 11
1.3重要的问题类型 12
1.3.1查找问题 12
1.3.2排序问题 12
1.3.3图问题 13
1.3.4组合问题 13
1.3.5几何问题 13
阅读材料——算法研究与图灵奖 14
习题1 16
第2章 算法分析基础 17
2.1算法的时间复杂性分析 17
2.1.1输入规模与基本语句 18
2.1.2算法的渐进分析 19
2.1.3最好、最坏和平均情况 20
2.1.4非递归算法的时间复杂性分析 20
2.1.5递归算法的时间复杂性分析 22
2.2算法的空间复杂性分析 23
2.3最优算法 23
2.3.1问题的计算复杂性下界 24
2.3.2平凡下界 25
2.3.3判定树模型 25
阅读材料——算法的实验分析 26
习题2 28
第二部分 基本的算法设计技术 33
第3章 蛮力法 33
3.1概述 33
3.1.1蛮力法的设计思想 33
3.1.2一个简单的例子——百元买百鸡问题 34
3.2查找问题中的蛮力法 36
3.2.1顺序查找 36
3.2.2串匹配问题 37
3.3排序问题中的蛮力法 42
3.3.1选择排序 42
3.3.2起泡排序 43
3.4组合问题中的蛮力法 44
3.4.1 0/1背包问题 44
3.4.2任务分配问题 45
3.5图问题中的蛮力法 46
3.5.1哈密顿回路问题 46
3.5.2 TSP问题 47
3.6几何问题中的蛮力法 48
3.6.1最近对问题 48
3.6.2凸包问题 49
阅读材料——KMP算法中next值的计算 51
习题3 53
第4章 分治法 55
4.1概述 55
4.1.1分治法的设计思想 55
4.1.2一个简单的例子——数字旋转方阵 57
4.2排序问题中的分治法 59
4.2.1归并排序 59
4.2.2快速排序 61
4.3组合问题中的分治法 64
4.3.1最大子段和问题 64
4.3.2棋盘覆盖问题 65
4.4几何问题中的分治法 67
4.4.1最近对问题 68
4.4.2凸包问题 71
阅读材料——递归函数的执行过程 72
习题4 74
第5章 减治法 77
5.1概述 77
5.1.1减治法的设计思想 77
5.1.2一个简单的例子——两个序列的中位数 78
5.2查找问题中的减治法 80
5.2.1折半查找 80
5.2.2二叉查找树 82
5.2.3选择问题 84
5.3排序问题中的减治法 86
5.3.1插入排序 86
5.3.2堆排序 88
5.4组合问题中的减治法 90
5.4.1淘汰赛冠军问题 90
5.4.2假币问题 91
阅读材料——假币问题的复杂版本 93
习题5 94
第6章 动态规划法 97
6.1概述 97
6.1.1多阶段决策过程 98
6.1.2动态规划法的设计思想 99
6.1.3一个简单的例子——数塔问题 100
6.2图问题中的动态规划法 102
6.2.1多段图的最短路径问题 102
6.2.2多源点最短路径问题 106
6.2.3 TSP问题 107
6.3组合问题中的动态规划法 109
6.3.1最长递增子序列问题 109
6.3.2最长公共子序列问题 111
6.3.3 0/1背包问题 114
6.4查找问题中的动态规划法 116
6.4.1最优二叉查找树 116
6.4.2近似串匹配问题 119
阅读材料——人工神经网络 121
习题6 124
第7章 贪心法 127
7.1概述 127
7.1.1贪心法的设计思想 127
7.1.2一个简单的例子——埃及分数 128
7.2图问题中的贪心法 129
7.2.1 TSP问题 129
7.2.2图着色问题 132
7.2.3最小生成树问题 134
7.3组合问题中的贪心法 138
7.3.1背包问题 138
7.3.2活动安排问题 140
7.3.3多机调度问题 142
阅读材料——贪心法的正确性证明 144
习题7 146
第三部分 基于搜索的算法设计技术 151
第8章 回溯法 151
8.1概述 151
8.1.1问题的解空间树 151
8.1.2回溯法的设计思想 152
8.1.3回溯法的时间性能 153
8.1.4一个简单的例子——素数环问题 154
8.2图问题中的回溯法 155
8.2.1图着色问题 155
8.2.2哈密顿回路问题 158
8.3组合问题中的回溯法 160
8.3.1八皇后问题 160
8.3.2批处理作业调度问题 163
阅读材料——遗传算法 166
习题8 169
第9章 分支限界法 171
9.1概述 171
9.1.1分支限界法的设计思想 171
9.1.2分支限界法的时间性能 172
9.1.3一个简单的例子——圆排列问题 173
9.2图问题中的分支限界法 175
9.2.1 TSP问题 175
9.2.2多段图的最短路径问题 178
9.3组合问题中的分支限界法 180
9.3.1 0/1背包问题 180
9.3.2任务分配问题 182
9.3.3批处理作业调度问题 184
阅读材料——蚁群算法 187
习题9 189
第四部分 计算的限制 193
第10章 问题的复杂性 193
10.1问题的复杂性分类 193
10.1.1什么是计算 194
10.1.2可计算问题与不可计算问题 195
10.1.3易解问题与难解问题 197
10.2 P类问题和NP类问题 199
10.2.1判定问题 199
10.2.2确定性算法与P类问题 199
10.2.3非确定性算法与NP类问题 200
10.3 NP完全问题 201
10.3.1问题变换 201
10.3.2 NP完全问题的定义 202
10.3.3基本的NP完全问题 202
10.3.4 NP完全问题的计算机处理 203
阅读材料——Cook定理 204
习题10 207
第11章 近似算法 209
11.1概述 209
11.1.1近似算法的设计思想 209
11.1.2一个简单的例子——求π的近似值 210
11.2图问题中的近似算法 211
11.2.1顶点覆盖问题 211
11.2.2 TSP问题 212
11.3组合问题中的近似算法 214
11.3.1装箱问题 214
11.3.2子集和问题 216
阅读材料——粒子群算法 219
习题11 221
第12章 概率算法 223
12.1概述 223
12.1.1概率算法的设计思想 224
12.1.2随机数发生器 224
12.2舍伍德型概率算法 225
12.2.1舍伍德型概率算法的设计思想 225
12.2.2快速排序 226
12.2.3二叉查找树 227
12.3拉斯维加斯型概率算法 228
12.3.1拉斯维加斯型概率算法的设计思想 228
12.3.2八皇后问题 229
12.3.2整数因子划分问题 230
12.4蒙特卡罗型概率算法 231
12.4.1蒙特卡罗型概率算法的设计思想 231
12.4.2主元素问题 232
12.4.3素数测试问题 233
阅读材料——模拟淬火算法 234
习题12 235
附录A名词索引 237
参考文献 243