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

本书作者根据自己几十年的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分最主要的算法技术，包括分治法、贪心算法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、最小生成树问题、最短路径问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等。作者力求通过有趣和难易适中的案例说明算法的特点和应用场景，使读者能够理解如何针对具体问题选择高效的算法。本书适合作为高校计算机及相关专业算法课程的教材，也适合作为软件研发人员了解算法的技术参考书。

前　　言
计算机算法是计算机科学的一个重要分支，是计算机专业的一门必修课。作者从事这门课的教学及相关研究工作已有三十余年，在走了不少弯路后逐渐领悟到算法的思维方法和设计技巧，积累了一些经验，很希望通过书的形式让更多的读者在学习的初期就能得到正规的训练，为今后进一步深造奠定坚实的基础。即使对于不再深造的学生而言，能正确地运用算法课中的方法解决实际工作中的问题也是至关重要的。我们经常看到，有些学过算法的学生仍喜欢用自己习惯的复杂度高的方法来求解问题，这是还没真正入门的表现。本书的主要目的就是帮助学生养成自觉运用所学方法去追求最好结果的良好习惯。
书是为学生而用，为读者而写。作者本着这一宗旨，以共同探索解决问题的方式来讨论，使读者能触摸到作者的思维方法，并能建立起自己独立思考的学习习惯。为此，作者在本书的一些地方使用了与其他书不同的叙述和证明方法，避免简单照搬国内外教材，以激发读者的兴趣。培养独立思考能力和创新的欲望对从事算法工作的人来讲十分重要，没有哪一种具体的算法可以解决所有问题，也没有哪一本书是万能的，只有勤于思考的人才能较好地解决实际问题。理论要联系实际，没有理论指导很难把实际问题解决好，两者的结合要靠读者在实际工作中去实践。
本书包含了任何算法书都会包含的基本内容，并进行了扩充，主要包括网络流、字符串匹配、计算几何算法、近似算法、穷举搜索法、平摊分析及斐波那契堆等，并在附录中介绍了红黑树和用于分离集合操作的数据结构。每章后配有精心挑选的习题，其中相当一部分是作者在教学实践中设计的。全书的内容足够用于两个学期教学。经过适当地取舍，本书可用作高等院校计算机及相关专业高年级本科生、硕士生及博士生教材。
最后，作者要感谢启蒙导师朱宗正教授（已去世）、博士生导师C. L. Liu教授（已去世） 的指导和熏陶，感谢清华大学、南京理工大学、伊利诺伊大学香槟分校的培养和提供的优良学术环境，感谢密苏里大学提供的教学和研究机会，感谢东南大学的单冯教授帮助完成本书的审校工作，并感谢朋友和家人的鞭策和支持。
本书修订了第1版中的错误。此外，做了以下主要改进。
增加第17章——平摊分析和斐波那契堆。
增加附录B——用于分离集合操作的数据结构。
在第2章、第4章和第7章中增加了一些例题和证明方法。
在第6章中，改进了动态规划的定义方法和例题解释。
增加了很多难易不等的习题供教师选择。

沈孝钧
2024年2月20日

沈孝钧　 美国密苏里大学荣休教授。他本科毕业于清华大学，后留学美国，就读于伊利诺大学香槟分校，师从著名计算机科学家C. L. Liu教授。获得博士后，受聘于密苏里大学堪萨斯分校计算机系直至退休。在30余年的教学和研究工作中，他主要讲授计算机算法和离散数学。他研究的领域包括离散数学、几何算法、并行处理、计算机网络中的调度算法等。除会议文章外，他有数十篇论文发表在国际著名期刊上，包括SIAM Journal on Computing、Discrete Mathematics、Discrete Applied Mathematics、IEEE Journal on Selected Areas in Communications、IEEE Transactions on Networking等。

目　　录
前言
教学建议
第1章　概述　1
1.1　算法与数据结构及程序的关系　1
1.1.1　什么是算法　1
1.1.2　算法与数据结构的关系　1
1.1.3　算法与程序的关系　2
1.1.4　选择排序的例子　2
1.1.5　算法的伪码表示　2
1.2　算法复杂度分析　 3
1.2.1　算法复杂度的度量　3
1.2.2　算法复杂度与输入数据规模的关系　4
1.2.3　输入数据规模的度量模型　4
1.2.4　算法复杂度分析中的两个简化假设　5
1.2.5　最好情况、最坏情况和平均情况
的复杂度分析　5
1.3　函数增长渐近性态的比较　6
1.3.1　三种比较关系及O、、记号　6
1.3.2　表示算法复杂度的常用函数　7
1.4　问题复杂度与算法复杂度的关系　9
1.4.1　问题复杂度是算法复杂度的
下界　9
1.4.2　问题复杂度与最佳算法　9
1.4.3　易处理问题和难处理问题　9
习题　 10
第2章　分治法　11
2.1　分治法原理　11
2.1.1　二元搜索的例子　11
2.1.2　表示复杂度的递推关系　12
2.2　递推关系求解　13
2.2.1　替换法　13
2.2.2　序列求和法与递归树法　15
2.2.3　常用序列和公式　16
2.2.4　主方法求解　18
2.3　例题示范　19
习题　 20
第3章　基于比较的排序算法　24
3.1　插入排序　　24
3.1.1　插入排序的算法 24
3.1.2　插入排序算法的复杂度分析　25
3.1.3　插入排序的优缺点　26
3.2　合并排序　26
3.2.1　合并算法及其复杂度　26
3.2.2　合并排序的算法及其复杂度　27
3.2.3　合并排序的优缺点　29
3.3　堆排序　 30
3.3.1　堆的数据结构　30
3.3.2　堆的修复算法及其复杂度　31
3.3.3　为输入数据建堆　32
3.3.4　堆排序算法　33
3.3.5　堆排序算法的复杂度　34
3.3.6　堆排序算法的优缺点　35
3.3.7　堆用作优先队列　35
3.4　快排序　36
3.4.1　快排序算法　36
3.4.2　快排序算法最坏情况复杂度　39
3.4.3　快排序算法平均情况复杂度　40
3.4.4　快排序算法最好情况复杂度　41
3.4.5　快排序算法的优缺点　42
习题　 42
第4章　不基于比较的排序算法　46
4.1　比较排序的下界　46
4.1.1　决策树模型及排序最坏情况下界　46
4.1.2　二叉树的外路径总长与排序平均
情况下界　 49
4.1.3　二叉树的全路径总长与堆排序
最好情况下界　 51
4.2　不基于比较的线性时间排序算法　54
4.2.1　计数排序　 54
4.2.2　基数排序　57
4.2.3　桶排序　58
习题　60
第5章　中位数和任一顺序数的选择　63
5.1　问题定义　63
5.2　最大数和最小数的选择　63
5.2.1　最大和最小顺序数的选择算法及
其复杂度　64
5.2.2　同时找出最大数和最小数的
算法　65
5.3　线性时间找出任一顺序数的算法　66
5.3.1　最坏情况复杂度为O(n)的算法 66
5.3.2　平均情况复杂度为O(n)的算法　 68
5.4　找出k个最大顺序数的算法　69
5.4.1　一个理论联系实际的问题　69
5.4.2　利用堆来找k个最大顺序数的
算法　 70
5.4.3　利用锦标赛树来找k个最大顺序数
的算法　70
习题　 71
第6章　动态规划　 73
6.1　动态规划的基本原理　73
6.2　矩阵连乘问题　 75
6.2.1　定义子问题　75
6.2.2　归纳公式　77
6.2.3　算法伪码和例子　78
6.3　最长公共子序列问题　81
6.3.1　定义子问题　81
6.3.2　归纳公式　82
6.3.3　算法伪码和例子　82
6.4　最佳二元搜索树问题　84
6.4.1　定义子问题和归纳公式　85
6.4.2　算法伪码和例子　87
6.5　多级图及其应用　 89
6.6　最长递增子序列问题　92
6.6.1　定义子问题　93
6.6.2　归纳公式　93
6.6.3　算法伪码和例子　93
习题　 95
第7章　贪心算法　 103
7.1　最佳邮局设置问题　103
7.2　一个简单的最佳活动安排问题　105
7.3　其他最佳活动安排问题　106
7.3.1　两个大礼堂的最佳活动安排
问题　106
7.3.2　等长时间的活动的最佳安排
问题　109
7.4　哈夫曼编码问题　112
7.4.1　前缀码　112
7.4.2　最佳前缀码——哈夫曼编码　114
7.5　最佳加油计划问题　118
7.5.1　最佳加油计划问题的描述　118
7.5.2　贪心算法的基本思路　119
7.5.3　贪心算法的伪码　120
习题　 121
第8章　图的周游算法　 128
8.1　图的表示　128
8.1.1　邻接表　129
8.1.2　邻接矩阵 129
8.2　广度优先搜索及应用　130
8.2.1　广度优先搜索策略　130
8.2.2　广度优先搜索算法及距离树　131
8.2.3　无向图的二着色问题　133
8.3　深度优先搜索及应用　136