本书在总结国内外计算机算法教材的基础上，根据作者多年国外教学实践，深入浅出地介绍计算机算法设计与分析的基本理论和方法。本书讲述算法复杂度的概念和表达，算法和数据结构的关系，算法设计与分析的主要技术和策略，其中包括递归与分治技术、贪心法、动态规划、图的遍历技术、平摊分析等。在讲述这些技术的同时，本书介绍一系列重要问题的算法，包括排序问题、选择问题、最小生成树问题、最短路经问题、网络流问题、二分图的匹配问题以及字符串的匹配问题等。由于这些问题的解法与所用技术及有效的数据结构紧密相连，本书不把它们分开讨论，而是有机地编排在一起讨论。此外，本书还介绍了问题本身的计算复杂性的概念和NP-完全问题的理论。
本书层次清晰,概念准确,内容丰富,例子有趣，适合学生循序渐进地学习。它可以作为计算机科学、电子工程、计算机信息系统等系中为本科生、研究生开设的“计算机设计与分析”课程教材，也可以作为从事计算机设计与分析的教师与研究人员的参考书。

封底
计算机算法是计算机科学的一个重要分支，也是一个难点。本书作者根据自己20多年在国内、国外的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分最主要的算法技术，包括：分治法、贪心法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、最小生成树问题、最短路径问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等，还介绍了问题本身的计算复杂性的概念和NP完全问题的理论，并介绍近似算法的设计和分析。
主要特点如下
精心设计了大量案例，并深入浅出地进行分析，使读者能够逐步领悟到算法的精妙之处。
推理严谨、丝丝入扣，对比了各种算法的方案，使学生能养成自觉地运用所学方法去追求最好结果的良好习惯。
以探索解决问题的方式进行讲解，使读者能清晰触摸到作者的思维方法，并建立起自己独立思考的学习习惯。
为了方便教学，每章配有难易适度的习题，并为教师免费提供电子课件。
作者简介
沈孝钧?美国密苏里大学堪萨斯分校计算机科学系教授，在美国20多年教授计算机算法、分布式算法、计算机体系结构、并行计算机体系结构、离散数学和计算机网络等课程，目前兼任中科院研究生院、东南大学客座教授，主讲计算机算法课程。曾在离散数学、几何算法、并行处理和计算机网络领域做过多年的研究，并发表过大约30篇杂志论文和30篇会议论文。目前主要研究方向是计算机网络，包括传感器网络中各种调度算法问题。

计算机算法是计算机科学的一个重要分支，是计算机专业的一门必修课。作者从事这门课的教学及相关研究工作二十余年，在走了不少弯路后逐渐领悟到算法的思维方法和设计技巧，积累了一些经验，希望通过书的形式让更多的读者一开始便得到正规的训练，为今后进一步深造奠定坚实的基础。即使是不再深造的学生，能正确地运用第一门算法课中的方法解决实际工作中的问题也是至关重要的。我们经常看到，有些学过算法的学生仍喜欢用自己习惯的复杂度高的方法来解决问题，这是还没真正入门的表现。这本书的主要目的就是使学生能养成自觉地运用所学方法去追求最好结果的良好习惯。
　　书是为学生而用，为读者而写。作者本着这一宗旨，以共同探索解决问题的方式来写作，使读者能触摸到作者的思维方法，并能建立起自己独立思考的学习习惯。培养独立思考和创新的欲望对从事算法工作的人来讲十分重要，没有哪一种具体的算法可以解决所有问题，也没有哪一本书是万能的，只有勤于思考的人才能最好地解决实际问题。
　　本书包含了任何算法书都会包含的基本内容，并进行了扩充，主要包括网络流、字符串匹配、计算几何算法、近似算法以及穷举搜索法等，并在附录中介绍了红黑树。每章后配有精心挑选的习题，其中相当一部分是作者在教学实践中设计的。打星号的章节和题目较难或较偏，供选择。全书的内容足够用于两个学期教学，经过适当地取舍，本书可用于高等院校计算机及相关专业高年级本科生、硕士生及博士生教材。
　　最后，作者要感谢启蒙导师朱宗正教授（已去世）、博士生导师C. L. Liu教授的指导和熏陶，感谢清华大学、南京理工大学、伊利诺大学香滨分校的培养和提供的优良学术环境，感谢密苏里大学提供的教学和研究机会，并感谢朋友和家人的鞭策和支持。
　　因作者水平有限，疏漏之处在所难免，欢迎读者批评指正。

沈孝钧
2013年3月20日

计算机科学及应用

计算机算法是计算机科学的一个重要分支，也是一个难点。本书作者根据自己20多年在国内、国外的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分最主要的算法技术，包括：分治法、贪心法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、最小生成树问题、最短路经问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等，还介绍了问题本身的计算复杂性的概念和NP完全问题的理论，并介绍近似算法的设计和分析。

主要特点如下：
　精心设计了大量案例，并深入浅出地进行分析，使读者能够逐步领悟到算法的精妙之处。
　推理严谨、丝丝入扣，对比了各种算法的方案，使学生能养成自觉地运用所学方法去追求最好结果的良好习惯。
　以探索解决问题的方式进行讲解，使读者能清晰触摸到作者的思维方法，并建立起自己独立思考的学习习惯。
　为了方便教学，每章配有难易适度的习题，并为教师免费提供电子课件。

沈孝钧　编著：沈孝钧，美国密苏里大学堪萨斯分校计算机科学系教授，在美国20多年教授计算机算法、分布式算法、计算机体系结构、并行计算机体系结构、离散数学和计算机网络等课程，目前兼任中科院研究生院、东南大学客座教授，主讲计算机算法课程。曾在离散数学、几何算法、并行处理和计算机网络领域做过多年的研究，并发表过大约30篇杂志论文和30篇会议论文。目前主要研究方向是计算机网络，包括传感器网络中各种调度算法问题。

前言
教学建议
第1章　概述 1
1.1　算法与数据结构及程序的关系 1
1.1.1　什么是算法 1
1.1.2　算法与数据结构的关系 1
1.1.3　算法与程序的关系 1
1.1.4　选择排序的例子 2
1.1.5　算法的伪码表示 2
1.2　算法复杂度分析 3
1.2.1　算法复杂度的度量 3
1.2.2　算法复杂度与输入数据规模的关系 3
1.2.3　输入数据规模的度量模型 4
1.2.4　算法复杂度分析中的两个简化假设 4
1.2.5　最好情况、最坏情况和平均情况的复杂度分析 5
1.3　函数增长渐近性态的比较 6
1.3.1　三种比较关系及O、Ω、Θ记号 6
1.3.2　表示算法复杂度的常用函数 6
1.4　算法复杂度与问题复杂度的关系 8
1.4.1　问题复杂度是算法复杂度的下界 8
1.4.2　问题复杂度与最佳算法 8
1.4.3　易处理问题和难处理问题 8
习题 9
第2章　分治法 10
2.1　分治法原理 10
2.1.1　二元搜索的例子 10
2.1.2　表示复杂度的递推关系 11
2.2　递推关系求解 11
2.2.1　替换法 12
2.2.2　序列求和法和递归树法 13
2.2.3　常用序列和公式 14
2.2.4　主方法求解 16
习题 16
第3章　基于比较的排序算法 19
3.1　插入排序 19
3.1.1　插入排序的算法 19
3.1.2　插入排序算法的复杂度分析 20
3.1.3　插入排序的优缺点 20
3.2　合并排序 21
3.2.1　合并算法及其复杂度 21
3.2.2　合并排序的算法及其复杂度 22
3.2.3　合并排序的优缺点 24
3.3　堆排序 24
3.3.1　堆的数据结构 24
3.3.2　堆的修复算法及其复杂度 25
3.3.3　为输入数据建堆 27
3.3.4　堆排序算法 28
3.3.5　堆排序算法的复杂度 29
3.3.6　堆排序算法的优缺点 29
3.3.7　堆用作优先队列 30
3.4　快排序 31
3.4.1　快排序算法 31
3.4.2　快排序算法最坏情况复杂度 33
3.4.3　快排序算法平均情况复杂度 34
3.4.4　快排序算法最好情况复杂度 34
3.4.5　快排序算法优缺点 36
习题 36
第4章　不基于比较的排序算法 39
4.1　比较排序的下界 39
4.1.1　决策树模型及最坏情况下界 39
*4.1.2　二叉树的外路径总长与平均情况下界 41
*4.1.3　二叉树的全路径总长及堆排序最好情况下界 43
4.2　不基于比较的线性时间排序算法 46
4.2.1　计数排序 46
4.2.2　基数排序 48
4.2.3　桶排序 49
习题 51
第5章　中位数和任一顺序数的选择 53
5.1　问题定义 53
5.2　最大数和最小数的选择 53
5.2.1　最大和最小顺序数的选择算法及其复杂度 53
5.2.2　同时找出最大数和最小数的算法 54
5.3　线性时间找出任一顺序数的算法 55
5.3.1　最坏情况复杂度为O (n)的算法 56
5.3.2　平均情况复杂度为O (n)的算法 58
5.4　找出k个最大顺序数的算法 58
5.4.1　一个理论联系实际的问题 58
5.4.2　利用堆来找k个最大的顺序数的算法 59
5.4.3　利用锦标赛树来找k个最大顺序数的算法 59
习题 60
第6章　动态规划 62
6.1　动态规划的基本原理 62
6.2　矩阵连乘问题 63
6.3　最长公共子序列问题 68
*6.4　最佳二元搜索树 71
6.5　多级图及其应用 76
6.6　最长递增子序列问题 78
习题 80
第7章　贪心算法 86
7.1　最佳邮局设置问题 86
7.2　最佳活动安排问题 87
7.3　哈夫曼编码问题 89
7.3.1　前缀码 89
7.3.2　最佳前缀码——哈夫曼编码 90
7.4　最佳加油计划问题 94
习题 96
第8章　图的周游算法 100
8.1　图的表示 100
8.1.1　邻接表 100
8.1.2　邻接矩阵 101
8.2　广度优先搜索及应用 101
8.2.1　广度优先搜索策略 101
8.2.2　广度优先搜索算法及距离树 102
8.2.3　无向图的二着色问题 105
8.3　深度优先搜索及应用 107
8.3.1　深度优先搜索策略 107
8.3.2　深度优先搜索算法和深度优先树 107
8.3.3　深度优先搜索算法举例和图中边的分类 110
8.3.4　拓扑排序 112
8.3.5　无回路有向图中最长路径问题及应用 114
8.3.6　有向图的强连通分支的分解 116
8.3.7　无向图的双连通分支的分解 119
习题 124
第9章　图的最小支撑树 128
9.1　计算最小支撑树的一个通用的贪心算法策略 129
9.2　Kruskal算法 130
9.3　Prim算法 133
习题 137
第10章　单源最短路径 140
10.1　Dijkstra算法 140
10.2　Bellman-Ford算法 144
习题 148
第11章　网络流 150
11.1　网络模型和最大网络流问题 150
11.2　网络中流与割的关系 152
11.2.1　网络中的割及其容量 153
11.2.2　剩余网络和增广路径 154
11.2.3　最大流最小割定理 156
11.3　Ford-Fulkerson 方法 157
11.3.1　Ford-Fulkerson 的通用方法 157
11.3.2　Edmonds-Karp算法 159
11.3.3　Dinic算法 161
11.3.4　0-1网络的最大流问题 164
11.4　二部图的匹配问题 165
11.4.1　用网络流求二部图的最大匹配算法 166
11.4.2　Philip-Hall婚配定理 167
11.4.3　Birkhoff-von Neuman定理 169
11.5　推进-重标号算法简介 170
11.5.1　预流和高度函数 170
11.5.2　在剩余图中对顶点的两个操作 171
11.5.3　推进-重标号算法的初始化 172
11.5.4　推进-重标号的通用算法 172
习题 174
第12章　计算几何基础 177
12.1　平面线段及相互关系 177
12.1.1　向量的点积和叉积 177
12.1.2　平面线段的相互关系 178
12.2　平扫线技术和线段相交的确定 181
12.2.1　平扫线的状态 182
12.2.2　用平扫线确定线段相交的算法 182
12.3　平面点集的凸包 185
12.3.1　Graham扫描法 186
12.3.2　Jarvis 行进法 190
12.4　最近点对问题 192
习题 195
第13章　字符串匹配 197
13.1　一个朴素的字符串匹配算法 197
13.2　Rabin-Karp算法 198
13.3　基于有限状态自动机的匹配算法 199
13.3.1　有限状态自动机简介 199
13.3.2　字符串匹配自动机 200
13.3.3　基于有限状态自动机的串匹配算法 202
13.4　Knuth-Morris-Pratt（KMP）算法 203
13.4.1　模式的前缀函数 203
13.4.2　KMP算法的伪码 205
习题 207
第14章　NP完全问题 208
14.1　预备知识 209
14.1.1　图灵机 209
14.1.2　符号集和编码对计算复杂度的影响 210
14.1.3　判断型问题和优化型问题及其关系 210
14.1.4　判断型问题的形式语言表示 211
14.1.5　多项式关联和多项式归约 212
14.2　P和NP语言类 214
14.2.1　非确定图灵机和NP语言类 214
14.2.2　多项式检验算法和NP类语言 215
14.3　NP完全语言类和NP完全问题 216
14.3.1　第一个NPC问题 217
14.3.2　若干著名NPC问题的证明 220
习题 231
第15章　近似算法 236
15.1　近似算法的性能评价 236
15.2　顶点覆盖问题 237
15.3　货郎担问题 238
15.3.1　满足三角不等式关系的货郎担问题 238
15.3.2　无三角不等式关系的一般货郎担问题 241
15.4　集合覆盖问题 242
15.5　MAX-3-SAT问题 244
15.6　加权的顶点覆盖问题 245
15.7　子集和问题 247
15.7.1　一个保证最优解的指数型算法 247
15.7.2　子集和问题的一个完全多项式近似机制 248
*15.8　鸿沟定理和不可近似性 251
15.8.1　鸿沟定理 251
15.8.2　任务均匀分配问题 252
习题 254
第16章　穷举搜索 257
16.1　搜索问题及方法的描述 257
16.2　回溯法 259
16.2.1　回溯法的通用算法 259
16.2.2　n皇后问题 259
16.2.3　子集和问题 260
16.2.4　回溯法的效率估计 262
16.3　分支限界法 263
16.3.1　分支限界法解n皇后问题 264
16.3.2　0/1背包问题 266
16.4　博弈树和α-β剪枝 271
16.4.1　博弈树及其评估的方法 271
16.4.2　α-β剪枝法 275
习题 276
附录　红黑树 278
参考文献 289