算法是利用电脑解决问题的技巧。本书采用轻松的对话手法，帮助读者简单且自然地掌握算法的基本概念，并养成猜的习惯，以后可以主动思考，尝试解决问题。
全书共分12章，内容包括从观察开始、分而治之法、动态规划、贪婪法、修剪与搜索法、树搜索法、问题转换、图算法、计算几何、算法的难题、逼近算法、随机算法等。
本书示例丰富，图文并茂，以易于理解的方式阐释算法，帮助程序员在日常项目开发中更好地发挥算法的能量。
编写这本书的动机是希望帮助读者简单、轻松地掌握算法的基本概念。因此，本书将不尝试收录所有的算法，同时也不把有限的笔墨用来分析算法的复杂度和对算法进行严格证明。
本书在介绍算法之前，常常会刻意地加入一小段对话，目的是希望通过思辨和讨论，自然地引出算法的直观意义。倘若读者从学习中顺便养成思考的习惯，那就更好了。
作者知识面有限，再加上表达能力不足，如果导致书中仍有无法被读者理解之处，在此向读者致歉。假如您在阅读的过程中惊讶地发现算法之美，在此表示深深的敬意。
作者
2017 年 4 月
计算机\算法
接受过计算机软件专业系统学习的人应该都学过“数据结构”“数据结构与算法”一类的课程，这类课程在算法的讲授上或浅或深，多数是以数据结构为核心讲述算法的具体运用和实现的。这类数据结构课程的主要内容是以计算机数据的存储结构为基础，将需要处理的现实世界的信息或者数据之间存在的一种或多种特定关系抽象化为计算机中可以描述的数据元素的集合，再辅以高效的检索算法和索引技术进行处理和加工。这类课程更注重数据结构的部分，虽然理工类大学在这类数据结构的课程中也会涉及算法设计和使用的时间、空间、效率等内容，但是在算法方面都是点到为止。注重理论基础的一些大学除了数据结构课程外，还会开设专门的算法课程，后者讲述的内容以算法的设计、研究以及算法的时间复杂度和空间复杂度的优劣分析等为主题。
算法的核心是对要解决的问题采用的方案准确且完整的描述，是解决问题的一系列连续、清晰的指令，也是用系统方法描述解决问题的策略机制。对于同一类问题，不同的算法在时间、空间和效率上可能差别很大，它们的优劣可以用科学的时间复杂度与空间复杂度来衡量。
本书虽然不能算得上算法理论研究内容的鸿篇巨著，但是可以作为学习数据结构这类课程的进修教材，或者作为学习算法艰深理论课程的入门读本和参考指南。本书包含算法基本概念的脉络和算法设计的朴素思想，阐述了算法设计和分析的任督二脉，让读者在简单、自然的氛围中打通“烧脑”的算法世界。
资深架构师 赵军
2017年3月
推荐序
前 言
1 一切从观察开始
1.1 什么是算法 2
1.2 汉诺塔问题 3
1.3 汉诺塔问题的非递归算法 10
1.4 发现算法的技巧 16
学习效果评测 18
2 分而治之法
2.1 何谓分而治之法 20
2.2 找出最大值 21
2.3 时间复杂度 23
2.4 二维极点问题 25
2.5 快速排序法 30
2.6 快速排序法的时间复杂度 34
2.7 寻找第 k 小值问题 40
2.8 分而治之法的技巧 47
学习效果评测 48
3 动态规划
3.1 何谓动态规划 50
3.2 换零钱 50
3.3 数字金字塔 54
3.4 最长相同子字符串 58
3.5 安排公司聚会 64
3.6 动态规划的技巧 70
学习效果评测 72
4 贪婪法
4.1 何谓贪婪法 75
4.2 最小成本生成树 75
4.3 霍夫曼编码树 83
4.4 贪婪法的陷阱：0-1 背包问题 88
4.5 单位时间工作调度问题 90
4.6 证明贪婪法并介绍Matroid理论 96
4.7 贪婪法的技巧 99
学习效果评测 100
5 修剪与搜索法
5.1 何谓修剪与搜索法 103
5.2 找坏蛋问题 104
5.3 猜数字问题 105
5.4 约瑟夫问题 106
5.5 简化的线性规划问题 113
5.6 修剪与搜索法的技巧 119
学习效果评测 119
6 树搜索法
6.1 何谓树搜索法 122
6.2 树状解空间：n 个皇后问题 123
6.3 回溯法：涂色问题 126
6.4 广度优先搜索法：八数字谜题 128
6.5 加速技巧：旅行商问题 131
6.6 树搜索法的技巧 140
学习效果评测 141
7 问题转换
7.1 何谓问题转换 144
7.2 将相异代表系问题转换成二分图上的匹配问题 145
7.3 将二分图上的匹配问题转换成网络流图问题 147
7.4 将网络流图问题转换成线性规划问题 150
7.5 问题转换的技巧 152
学习效果评测 154
8 图算法
8.1 什么是图 156
8.2 连通分支 157
8.3 Dijkstra 最短路径算法 160
8.4 Bellman-Ford 最短路径算法 168
8.5 双连通分支 175
8.6 图算法的技巧 193
学习效果评测 195
9 计算几何
9.1 何谓计算几何 199
9.2 多边形中的点 200
9.3 天空轮廓 203
9.4 凸包 208
9.5 最近点对 215
9.6 计算几何的技巧 219
学习效果评测 220
10 算法的难题
10.1 什么是 NP-Complete 224
10.2 集合 P 和集合 NP 225
10.3 满足性问题 227
10.4 多项式时间转换 229
10.5 NP 中的难题 230
10.6 NP-Complete 的性质 234
10.7 NP-Complete 的证明技巧 237
学习效果评测 241
11 逼近算法
11.1 什么是逼近算法 244
11.2 最小顶点覆盖问题 244
11.3 装箱问题 247
11.4 平面上的旅行商问题 249
11.5 逼近算法的技巧 252
学习效果评测 252
12 随机算法
12.1 什么是随机算法 256
12.2 随机快速排序法 257
12.3 质数测试 258
12.4 最小割算法 259
12.5 随机算法技巧 265
学习效果评测 265
参考文献
