| 2020-01-31 最近点对与凸包问题（DC） 最近点对问题 在前面的章节里，我们分别讨论了最近点对和凸包问题，但采用的都是列举其所有情况的暴力解法，效率非常低。这节的内容，我们会用到两种更为高效的方法。 既然这章都在讲分治法，在解决最近点对问题的时候自然也离不开将这些散点进行分组。所以这里我们用一条垂直分界线 L，将散点分成两部分，SL 和 SR。 最近点对 其中，SL 包含 ⌈n/2⌉ 个点，而 SR 包含 ⌊n/2⌋ 个点。 接下来，我们要分别计算出左右两部分的最近点对距离 dL 和 dR。 最近点对 然后我 ...
| 2020-01-30 二叉树的遍历 引入 前面讲到了二叉搜索树以及它的一些基本操作（插入，搜索，删除），可是我们要怎样知道这些操作是被正确执行的呢？这就需要借助遍历来间接“打印”出树的结构。 和图的遍历一样，我们也需要逐个访问每一个节点，但跟图不同的是，二叉树的遍历是从根节点开始的，而非任意节点。根据二叉树的特点，每颗二叉树都是由三部分组成：根节点，左子树和右子树。而根节点的左右子树也是由这三部分组成，所以二叉树的遍历问题也是可以用分治来解决的，即遍历一颗二叉树 = 访问根节点 + 遍历根节点的左子树 + 遍历 ...
| 2020-01-27 快速排序 Lomuto 划分 前面我们学习了分治的思想，将一个大问题划分为若干个小问题，然后逐个解决小问题，最后将小问题的解合并成大问题的解。这一节的内容，我们还会用到这种方法来解决排序问题，但这次我们更强调“分”。 在对一个无序的数组进行排序的过程中，我们总是想要将小的元素放在数组的左侧，而将大的元素放在数组的右侧。Lomuto 划分就是一种将数组分为两部分的算法，其中较小部分的所有元素均小于某个中间值，较大部分均大于等于某个中间值，我们把这个中间值叫做中轴（pivot）。 中轴 ...
| 2020-01-25 归并排序 分治 分治（divide and conquer）是算法里面的一种经典思想。与减治的通过缩小问题规模来解决问题而有所不同的是，分治采用的是，将一个大问题分成若干个小问题，然后逐一解决小问题，最后将小问题的解合并为原来大问题的解。听起来很抽象？没关系，下面的一个例子你马上就能明白。 小的时候我们一定都玩过类似乐高的玩具，当你花了几天的时间拼出一件作品时，你一定是满满的成就感吧。其实，我们在整个拼接的过程中都用到了分治的思想。要想拼出一栋房子，我们肯定不会一个零件一个零件地拼，而 ...
| 2020-01-23 插值查找 查字典 如果要在字典里查找 “algorithm” 这个单词，我们肯定不会傻傻地像二分法那样从中间开始查找。相反，我们会从字母 A 开始查找，然后再根据第二个字母在字母表中的位置，找到相应的位置继续查找，这样反复这个过程，直到查到这个单词。 在这一节的内容里，我们会实现类似于查字典的算法。 插值查找 插值查找（interpolation search）是二分查找的改良版。假设有这样一个数组 [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]，我们可 ...
| 2020-01-20 二分查找与二叉树 有序表的查找 我们已经讨论过在一个数组中找到相应元素的算法，我们采用的是最简单，最直接的顺序搜索的方式，即从第一个元素开始，从左往右依次搜索，直到查找到该元素或查找失败。对于复杂度而言，我们也讨论过它的平均复杂度为 Θ(n)。那么还有没有更快的算法呢？这一节我们就来讨论一下吧～ 如果一个数组本身是有序的，查找一个元素就类似于在前面提到的猜数问题，只是这里查找的元素变成了要猜的数。如果我们从数组的中间位置开始查找，在每轮查找过后，我们只需要在剩下一半的数组中再继续查找，这样以此 ...
| 2020-01-19 拓扑排序 定义 在大学里，每当到了期末的时候，你一定会头疼于各种选课给你带来的困扰。其中一项就是先修课，每次你高高兴兴地选了自己心仪的选修课，却发现自己不满足先修课的要求，只好默默地退掉。这一次，我们就来讨论一下这个问题。 选课 假设大学里开设了这些课程：高等数学，线性代数，概率论，数据结构，机器学习和计算机视觉。它们存在这样的先修关系：线性代数的先修课为高等数学；概率论的先修课是线性代数；机器学习的先修课为线性代数、概率论和数据结构；最后计算机视觉的先修课是机器学习。 下面我们需 ...
| 2020-01-17 插入排序 减治 在这一章里面，我们会讨论一种解决问题的新方案。减治（decrease and conquer），全称叫做减而治之，是通过逐步缩小问题规模的方式来解决一个问题。可能你还不是很明白，别急，我们先上一个例子：假设 9 枚金币中有一枚是假的（假币的重量会比真币轻），现在给你一个天平，你需要用最少的次数找出假币，该怎么做呢？ 天平 你可以一枚一枚地称，但最多你可能要称 8 次才能称出来，不是很高效。其实我们可以将这些金币对半分，即 9 枚金币分为 4 枚和 5 枚。因为天平两 ...
| 2020-01-15 暴力搜索 回顾 在图的遍历那一节里面我们知道，不管是深度优先遍历还是广度优先遍历，本质上都是对图中的每一个节点执行一次遍历算法，即穷尽所有的情况。这次要讲到的暴力搜索（exhaustive search）就是专门为了解决这类问题而产生的。除了图的遍历，暴力搜索还以解决组合问题为主。下面我们一起来看看吧～ 背包问题 背包问题是一道典型的组合问题，问题可以这样来描述它：给定一些物品，这些物品都有它自己的重量 wi 和价格 vi ，并且每个物品只能选择一次。现在有一个能装 W 重量的背包，你 ...
| 2020-01-13 最近点对与凸包问题（BF） 最近点对问题 这一节内容，我们来看看两个经典的几何学问题。首先是最近点对问题（closest-pair problem）。问题的描述是在一个二维平面上有一些随机分布的散点，要求我们在这些散点里找到两个点，使得它们的距离最小。 最近点对 有解决这个问题很简单，只需要把所有的情况都列举出来，即每一个点与其他所有节点的距离都计算出来，然后取最小的值。所以，这里我们再次用到了暴力求解的方法。 1def closest_pair_bf(X, Y):2 d = np. ...
