算法设计与分析(Python)"
本书介绍了算法设计与分析的基本技巧，主要包括递归、分治、动态规划、贪心和随机等算法，以及利用这些算法求解计算问题的时间复杂度分析等内容。通过诸多有趣的实例，向读者介绍了算法设计的思想，以便读者能形成算法思维的固定模式去解决问题。在介绍每一类算法范式以及分析算法复杂度时，都力求建立直观的思维过程，而摒弃过深的数学证明。书中所有算法均采用 Python语言描述，读者能从中学习到许多算法实现的技巧，从而提高编写程序的能力。
本书可作为高等学校计算机专业大一、大二或者学习过程序设计的非计算机专业学生的算法设计与分析教材。
“算法设计与分析”是计算机专业非常重要的一门基础课程，它不仅是诸多计算机专业课程的基础，也是许多信息科技类公司招聘程序员时，笔试与面试重点考核的内容。算法设计与分析已经有了诸多经典的著作，比如美国麻省理工学院（ MIT）几位教授合著的《算法导论》 ①等。然而，这些经典著作当作教材使用时，都会存在对内容进行适当裁剪，以便更适合 48或者 32个学时教学的问题。我们写本书的目的就是对初等算法内容进行合理的编排，让初学者能很快地掌握解决计算问题的常用算法，以及分析算法效率的方法。
本书算法均采用 Python语言进行描述， Python是一类解释性语言，其语法简单直观，有一定程序设计基础的学生可以很快入门。 Python语法简单并不意味着功能弱，它在科学计算、 Web应用等诸多领域都有着广泛的应用。国外知名的高校，如麻省理工学院，也在算法设计课中采用 Python语言描述。与采用伪代码描述算法的书比较而言，采用 Python描述算法能给读者直接的运算结果，从而可以使读者更易于揣摩算法实现的技巧。
计算机算法不仅涉及诸多理论，还有各种技术细节。比如介绍随机算法时，有些执行时间的分析就需要较多的概率论知识；而算法实现技术细节则不仅关注如何存储数据，甚至对执行算法的硬件环境也会考虑在内。本书的内容安排则介于两者之间，在数学分析与实现之间期望取得合理的平衡。首先，在分析算法效率时尽量避免过深的数学证明，但关键步骤依然会给出直观的解释。其次，在实现算法时本书尽量利用 Python已有的数据结构和库函数，从而简化算法实现的技术难度。
如果将要处理的数据、问题看作是食材，那么算法就是将食材“转化”成各种令人垂涎的美食的过程。中国菜肴到处都是充满想象力的转化，将原本普通的食材（如大豆和糯米等）转化为营养和美味的食物（豆腐、酒酿和酱料等）。本书的主线就是转化，它不仅有问题的转化，也有方法的转化（如图 1所示）。通过问题的转化将问题“化繁为简”，通过方法的转化以便融会贯通各种算法设计的技巧。
本书主要内容
由于计算机已经成为现代科技、生活不可缺少的工具。因此，解决计算问题的算法涉及的内容可以说包罗万象，从简单的排序和查找到复杂的语音识别、文字翻译，甚至
①见参考文献 [1]。
图 1本书的主线 转化
游戏等都离不开算法。本书内容涵盖了大部分的经典算法，主要内容包括递归算法、分治算法、排序算法、动态规划算法、图搜索算法、最大流算法、随机算法和算法复杂度。
第 1章主要介绍算法的基本概念，通过实例向读者展示解决同一问题的不同算法的确存在效率上显著的差异。第 2章介绍度量算法效率的记号，以及分析简单函数执行时间的常用技巧。第 3章通过解决文档比较、单词拼写纠正和稳定匹配这三个有趣的问题，帮助读者熟悉 Python语言。第 4章介绍了递归算法以及递归函数求解，从而为后续章节复杂的算法设计与分析打下一定的基础。第 5章介绍了组织数据的两个常用方法：排序和数据结构，主要强调递归在组织数据中的应用，帮助读者进一步熟悉采用递归求解问题的过程。
第 6章到第 11章则分别介绍了分治算法、图搜索、贪心、动态规划、最大流和随机算法。通过各种有趣的问题，向读者展示转化的基本技巧，以便更好地帮助读者建立采用算法思维去解决问题的习惯。第 12章介绍了算法复杂度，帮助读者明确哪类问题“可解”，而哪类问题目前“不可解”。
本书由程振波总体设计和规划。第 2到第 12章由程振波编写，第 1章由程振波、李曲和王春平编写。全书由程振波统稿。
如何使用本书
本书的内容框架是笔者在浙江工业大学“算法设计与分析”课程的讲义，内容的编排则参考了 MIT的算法课程 6 006。①因此，本书从内容安排来说非常适合学时为 48或者 32学时的算法课程。对于教师而言，可以直接按照本书的章节安排教学计划。为了便于教师安排教学，具体的教学建议如下：
① MIT将“算法设计与分析”课程分解成了两门课。一门是 6 006，该课程主要是算法的入门课程，可以面向各个专业开设。另一门则是 6 046，这是一门面向有一定算法基础的学生开设的算法课程。
III
教学内容学习要点及教学内容课时安排
第 1章引言 掌握算法的定义。了解算法的来源，理解现实生活中解决问题的办法与算法之间的关系；掌握衡量算法的属性，尤其是正确性和时间效率对算法的意义。 2
掌握算法效率的基本概念。理解直接计算某个输入规模的时间来衡量算法效率的不足；了解渐进分析法以及多项式时间复杂度与指数时间复杂度的区别。
了解求解问题可能存在效率不同的算法。掌握求解一维高点问题的简单算法及改进算法。
掌握哈希表的基本概念。
第 2章渐进分析与 Python计算模型 掌握运行算法的简化模型。了解单处理器随机访问机器模型的结构，以及运行在该机器模型上常见指令的执行时间。 2
掌握算法渐进分析的概念。熟悉三种渐进函数的定义，以及常见函数的渐进表示。
熟练掌握基本函数的渐进分析。熟悉 Python的判断、循环语句写法，熟练掌握 Python的基本数据结构的使用。掌握较为复杂的函数的时间复杂度分析，如求最大值、二分搜索等。
第 3章问题求解与代码优化 基本掌握使用 Python求解较为复杂的问题。 了解文档比较问题及其算法。 2
了解单词拼写问题及其实现算法。
了解稳定匹配问题及其实现算法。
第 4章递归算法与递归函数 熟悉递归的组成结构。熟练掌握递归算法的两个基本组成，以及它们各自的作用。 4或 6
掌握递归算法执行的过程。了解递归算法在机器模型中的运行过程。
熟练掌握常见问题的递归求解方法。熟悉回文、全排列和汉诺塔问题的递归算法。
熟练掌握求解标准递归函数 T (n) = aT (n/b) + f(n)的方法。掌握替换法和主分析法求解递归函数的过程，理解主分析法的三类条件及其对应的解。
续表
教学内容 学习要点及教学内容 课时安排
第 5章 排序与树结构 熟悉插入排序、选择排序和合并排序算法。能熟练 4 写出这三个排序算法的实现代码以及它们各自的
时间复杂度。 掌握二叉搜索树的基本数据操作。能从使用场景的
角度理解二叉树与数组、链表等数据结构的不同。
掌握基于二叉搜索树常见的数据操作，比如插入、
删除和查找等。
熟练掌握堆结构的应用场景和数据操作。熟悉建堆
算法及其时间复杂度分析，了解基于堆的排序和合
并 k个有序序列等应用。
第 6章 分治算法 掌握分治算法求解问题的三个基本步骤。 6
掌握利用分治法求解一些典型问题，如序列最大差
值区间、统计逆序数、空间点最小距离和序列中第
k小的数等问题。
熟悉如何将问题进行分解，以及合并子问题解的常
用技巧。掌握分治算法的时间复杂度分析。
第 7章 图搜索算法 熟悉图的两种常见表示方法，熟练掌握如何在计算 4
机中存储图。了解图在计算机应用领域常见的应用
场景。
熟练掌握图上宽度优先搜索算法及其算法复杂度
分析，了解利用宽度优先搜索解决计算问题的建模
过程。
熟练掌握图上深度优先搜索算法及其算法复杂度
分析，了解利用深度优先搜索解决计算问题的建模
过程。
第 8章 贪心算法 了解贪心算法求解优化问题的过程。 4
熟练掌握利用贪心算法求解典型的计算问题，如硬
币找零、间隔任务规划等问题。了解利用替换法证
明贪心策略是否能获得全局最优解的过程。
熟练掌握贪心算法在两个典型图搜索中的应用，即
单源最短路径和最小生成树。理解单源最短路径和
最小生成树算法中，利用合理的数据结构优化算法
复杂度的技巧。
教学内容 学习要点及教学内容 课时安排
第 9章动态规划算法 理解动态规划求解优化问题的典型步骤，以及动态规划算法求解计算问题的时间复杂度分析。 6
熟练掌握利用动态规划算法求解一维、二维等典型优化问题，如斐波那契数、拾捡硬币、连续子序列的最大值、矩阵的括号、 0-1背包问题等。
对于简单问题能画出其动态规划表，并能从中得到问题的解。
第 10章最大流算法 掌握最大流问题的定义，了解流量、容量以及它们之间的关系。 2
掌握通过增广路径求最大流问题的 Ford-Fulkerson和 Edmond-Karp算法，理解这两个算法之间的异同。
了解将计算问题转化为最大流问题的基本过程。掌握通过最大流算法求解二向图最大匹配和文件传输中的不重合边等问题的方法。
第 11章随机算法 了解两种典型的随机算法：蒙特卡洛和拉斯维加斯算法，以及它们之间的异同。 2
熟练掌握利用随机算法求解典型的计算问题，如矩阵乘积结果验证、快速排序、选择第 k小的数和最小割验证等。
了解随机快速排序算法复杂度分析过程。
第 12章算法复杂度 了解如何根据问题求解的难易程度对计算问题进行基本分类。 2
理解 P问题、 NP问题和 NPC问题的定义。
了解几个典型的 NPC问题，理解为什么证明 P是否等于 NP是计算机领域最为重要的问题之一。
对学生而言，先阅读书中各章节内容，然后运行书中代码以便检验对算法的理解程度。特别是，学生还应该独立重复出书中各个问题的算法，这个过程就好比学习围棋的选手进行复盘一样。如果仅仅是了解算法原理，而没有通过写代码来实现算法，将不利于读者培养独立解决问题的能力。
此外，除了课后习题外，我们还建议学生在 leetcode ①上刷题。 leetcode上的题目
① https://leetcode com/
不是国际计算机学会（ ACM）的竞赛题目，而是各大 IT企业的面试题目。通过解题不仅能提高学生算法设计的能力，也对编程能力有极大提高。
阅读本书需要学生能按照教程（ http://www python org/）配置 Python环境，知道如何写一个简单的包括循环的函数。因此，该课程安排在学生上过一门程序语言课程之后较为合适。
致谢
在本书编写过程中，许多浙江工业大学的同学阅读了初稿，尤其感谢李轶、陈明明、严凡等同学给出的许多建议。我们的许多同事也对本书提出了诸多宝贵建议，他们是吕慧强、钱能和黄德才老师。本书还受到浙江工业大学校级重点教材资助，特此感谢。对在本书出版过程中付出辛勤劳动的清华大学出版社的编辑致以特别的谢意。最后，作者程振波要对他的妻子王玉秀、女儿程静萱致以特别的谢意，感谢她们给予的爱和支持，让他能心无旁骛地完成书稿。
程振波李曲王春平
2017年 6月
第 1章引言 1
1 1算法的定义 1
1 1 1算法的属性 2
1 1 2效率的定义 3
1 2算法设计与分析举例 5
1 2 1寻找局部高点 -1D 5
1 2 2图书管理 8
1 3小结 10 课后习题 11
第 2章渐进分析与 Python计算模型 13
2 1引言 13
2 2计算模型 13
2 3算法的渐进分析 14
2 4 Python计算模型 17
2 4 1控制流语句 17
2 4 2数据结构 19
2 5算法分析实例 21
2 5 1求最大值 22
2 5 2二分搜索 22
2 5 3子集和问题 23
2 6小结 24 课后习题 25
第 3章问题求解与代码优化 27
3 1引言 27
3 2文档比较 27
3 2 1问题提出 27
3 2 2算法设计 28
3 2 3算法优化 31
3 3拼写矫正 33
3 3 1问题提出 33
3 3 2算法设计 33
3 4稳定匹配问题 36
3 4 1问题提出 36
3 4 2算法设计 38
3 5小结 40 课后习题 41
第 4章递归算法与递归函数 42
4 1引言 42
4 2递归的组成结构 42
4 2 1如何筹集巨款 42
4 2 2上线与下线 44
4 3递归算法的执行 45
4 3 1跟踪函数的执行 47
4 4利用递归算法求解问题 51
4 4 1回文判断 51
4 4 2全排列 53
4 4 3汉诺塔问题 54
4 4 4雪花曲线 57
4 5递归函数的求解 58
4 5 1替换法 59
4 5 2主分析法 60
4 6小结 62 课后习题 63
第 5章排序与树结构 64
5 1引言 64
5 2递归与排序 65
5 2 1选择排序 65
5 2 2插入排序 67
5 2 3合并排序 69
5 3二叉搜索树 72
5 3 1 BST的实现 74
5 3 2插入新结点 75
5 3 3 BST上查找 77
5 3 4二叉树修剪 78
IX
5 4堆 81
5 4 1堆化操作 81
5 4 2构造堆 83
5 4 3堆排序 85
5 4 4合并 k个有序序列 86
5 5小结 87 课后习题 88
第 6章分治算法 90
6 1引言 90
6 2股票的买卖 91
6 2 1问题描述 91
6 2 2算法设计 91
6 3统计逆序 94
6 3 1问题描述 94
6 3 2算法设计 94
6 4空间最小距离点对 97
6 4 1问题描述 97
6 4 2算法设计 98
6 5寻找第 k小的数 103
6 5 1问题描述 103
6 5 2算法设计 103
6 6大整数乘法 107
6 6 1问题描述 107
6 6 2算法设计 108
6 7小结 109 课后习题 109
第 7章图搜索算法 111
7 1引言 111
7 2图搜索的应用 112
7 3图的表示 113
7 4宽度优先搜索 114
7 4 1宽度优先搜索算法 114
7 4 2 BFS算法分析 117
7 4 3 BFS算法应用举例 117
7 5深度优先搜索 121
7 5 1深度优先搜索算法 121
7 5 2 DFS算法分析 124
7 5 3 DFS应用举例 124
7 6小结 126 课后习题 126
第 8章贪心算法 128
8 1引言 128
8 2硬币找零 128
8 2 1问题描述 128
8 2 2问题求解 129
8 2 3最优解证明 130
8 3间隔任务规划 130
8 3 1问题描述 130
8 3 2问题求解 131
8 3 3最优解证明 133
8 4单源最矩路径问题 134
8 4 1 Dijkstra问题 135
8 4 2算法的正确性 136
8 4 3算法的性能优化 137
8 5最小生成树 139
8 5 1 Prim算法 140
8 5 2算法实现 142
8 6小结 145 课后习题 145
第 9章动态规划算法 147
9 1引言 147
9 2再遇斐波那契数 147
9 3一维动态规划 151
9 3 1拾捡硬币 152
9 3 2连续子序列和的最大值 155
9 3 3疯狂的 8 157
9 3 4文本排版 161
9 3 5完全信息的 21点 165
9 4二维动态规划 169
9 4 1矩阵的括号 169
9 4 2字符串编辑距离 173
9 4 3 0-1背包问题 176
XI
9 5小结 179 课后习题 180
第 10章最大流算法应用 182
10 1引言 182
10 2最大流算法 182
10 2 1 Ford-Fulkerson算法 186
10 2 2 Edmond-Karp算法 187
10 3最大流算法的应用 189
10 3 1二向图最大匹配问题 189
10 3 2文件传输中的不重合边问题 191
10 4小结 193 课后习题 193
第 11章随机算法 195
11 1引言 195
11 2矩阵乘积结果验证 196
11 3快速排序 198
11 3 1根据支点数划分输入序列 199
11 3 2选择支点数 200
11 3 3随机快速排序 202
11 4选择第 k小的数 203
11 5寻找最小割边 206
11 6小结 209 课后习题 209
第 12章算法复杂度 210
12 1引言 210
12 2问题的分类 210
12 2 1易解与难解 210
12 2 2无解的问题 211
12 2 3难解问题的证明 213
12 3 NPC问题应用 214
12 3 1决策问题 214
12 3 2问题的化约 215
12 3 3 NP问题 215
12 3 4 NPC问题 216
12 4 P等于 NP吗 218
12 5小结 219 课后习题 219 索引 221 代码列表 222 参考文献 226
如果将要处理的数据、问题看作是食材，那么算法就是将食材“转化”成各种令人垂诞美食的过程。中国菜肴到处都是充满想象力的转化，将原本普通的食材（大豆和糯米等）转化为营养和风味都令人叹为观止的食物（豆腐、酒酿和酱料等等）。《算法设计与分析（Python）》的主线就是转化，它不仅有问题的转化，也有方法的转化。通过问题的转化将问题“化繁为简”，通过方法的转化以便融会贯通各种算法设计的技巧。
算法设计与分析是计算机专业非常重要的一门基础课程，它不仅是诸多计算机专业课程的基础，也是诸多信息科技类公司在招聘员工时，笔试与面试重点考核的内容。算法设计与分析已经有了诸多经典的著作，然而笔者在教学过程发现，已有的算法设计与分析教材往往并不适合初学算法课程的同学。主要是这些著作往往需要较多的程序设计与数据结构的背景知识。《算法设计与分析（Python）》的内容编排并未要求过多的程序设计或者数学基础，只需要有一定程序设计基础即可，具体而言就是能正确写出一个从1加到100 的函数即可。尤其是，已有的算法著作在分析算法复杂度时，为了结果的严谨往往忽视了数学分析后的直观解释。
《算法设计与分析（Python）》摈弃了算法分析过程中繁琐的数学证明，而主要通过图示等手段给出算法分析结果的直观解释。此外，已有的教材描述算法的语言要么是伪代码，要么是C，C++ 或者Java这类高级程序语言。采用伪代码描述算法可以获得更为精简的描述，然而缺少可执行的结果会降低初学者对算法结果的直观印象。而使用C，C++ 或者Java这类高级程序语言描述算法，会降低算法描述的简洁性，还会增加初学者调试出正确结果的难度。为此，《算法设计与分析（Python）》的算法采用Python 描述。Python 是复杂度介于伪代码和C，C++ 之间的一类语言，其语法简单直观，如果有一定程序设计基础的学生可以在1 小时内入门。《算法设计与分析（Python）》可作为计算机专业大一、大二或者学习过程序设计的非计算机专业学生的算法设计与分析教材。
如果将要处理的数据、问题看作是食材，那么算法就是将食材“转化”成各种令人垂诞美食的过程。中国菜肴到处都是充满想象力的转化，将原本普通的食材（大豆和糯米等）转化为营养和风味都令人叹为观止的食物（豆腐、酒酿和酱料等等）。《算法设计与分析（Python）》的主线就是转化，它不仅有问题的转化，也有方法的转化。通过问题的转化将问题“化繁为简”，通过方法的转化以便融会贯通各种算法设计的技巧。
算法设计与分析是计算机专业非常重要的一门基础课程，它不仅是诸多计算机专业课程的基础，也是诸多信息科技类公司在招聘员工时，笔试与面试重点考核的内容。算法设计与分析已经有了诸多经典的著作，然而笔者在教学过程发现，已有的算法设计与分析教材往往并不适合初学算法课程的同学。主要是这些著作往往需要较多的程序设计与数据结构的背景知识。《算法设计与分析（Python）》的内容编排并未要求过多的程序设计或者数学基础，只需要有一定程序设计基础即可，具体而言就是能正确写出一个从1加到100 的函数即可。尤其是，已有的算法著作在分析算法复杂度时，为了结果的严谨往往忽视了数学分析后的直观解释。
《算法设计与分析（Python）》摈弃了算法分析过程中繁琐的数学证明，而主要通过图示等手段给出算法分析结果的直观解释。此外，已有的教材描述算法的语言要么是伪代码，要么是C，C++ 或者Java这类高级程序语言。采用伪代码描述算法可以获得更为精简的描述，然而缺少可执行的结果会降低初学者对算法结果的直观印象。而使用C，C++ 或者Java这类高级程序语言描述算法，会降低算法描述的简洁性，还会增加初学者调试出正确结果的难度。为此，《算法设计与分析（Python）》的算法采用Python 描述。Python 是复杂度介于伪代码和C，C++ 之间的一类语言，其语法简单直观，如果有一定程序设计基础的学生可以在1 小时内入门。《算法设计与分析（Python）》可作为计算机专业大一、大二或者学习过程序设计的非计算机专业学生的算法设计与分析教材。
在线授课视频：https://www.bilibili.com/video/av87870598/
https://www.bilibili.com/video/av88007850/
https://www.bilibili.com/video/av88087700/
https://www.bilibili.com/video/av88097616/
https://www.bilibili.com/video/av88328036
https://www.bilibili.com/video/av88329229
