跳转至

基础算法

基础因人而异，下面罗列的是个人认为相对基础的知识点。只有熟练掌握了以下基础算法，才有可能理解更复杂的算法从而解出更高难度的问题。

贪心

贪心考虑的是局部最优，即每次做决策时都是选当前的局部最优解。当然，如果能举出贪心的反例，即局部最优无法得出全局最优，就可以考虑使用 动态规划 等其他全局性策略来解决问题了。

贪心算法其实并不简单，很多时候需要敢想敢猜并且证明并不容易，但因为这种方法套路不多，就放在第一个基础算法部分展开。对于贪心问题的证明，我总结出了以下证明方法：

  • 交换法：如果交换两个对象会得到更差的结果，那么原来的方案（顺序）就是合理的；
  • 边界法：由于边界也需要满足相同的条件，并且边界的情况往往更少，因此从边界开始考虑（枚举）往往可以证明出贪心的正确性。也可以理解为从更小规模的问题开始考虑。

前缀和与差分

前缀和与差分是两个相辅相成的算法。两者的适用场景如下：

  • 前缀和算法适用于「频繁求子数组之和、不频繁修改数组元素」的场景；
  • 差分算法适用于「频繁增减子数组元素值、不频繁求数组元素」的场景。

更精简地说：

  • 前缀和算法适用于「频繁区间查询、不频繁单点修改」的场景；
  • 差分算法适用于「频繁区间修改、不频繁单点查询」的场景。

前缀和

为了学习差分算法，我们有必要先学习前缀和算法。具体地，对于一个长度为 \(n\) 的数组 \(a\)，我们定义 \(s_i\) 表示：

\[ s_i=\sum_{j=0}^{i}a_j \]

那么当进行区间查询求解数组中下标在闭区间 \([p,q]\) 中的元素和时，只需要 \(s_q-s_{p-1}\) 地 \(O(1)\) 计算出来即可。我们称 \(s\) 为数组 \(a\) 的前缀和数组。为了维护出 \(s\)，我们采用 递推 策略。即：

\[ s_i= \begin{cases} a_0,&i=0\\ s_{i-1}+a_i,&i\ge1 \end{cases} \]

差分

为了实现给数组中下标在闭区间 \([i,j]\) 中的元素 \(s_{i\sim j}\) 同时增加 \(x\) 的操作，我们可以借助前缀和算法的思想。具体地，仍然记原始数组为 \(a\)，前缀和数组为 \(s\)，如果将 \(a_i+x\) 同时 \(a_{j+1}-x\)，那么在维护前缀和数组 \(s\) 时，\(s_{i\sim j}\) 中的每一个元素就都增加了 \(x\) 且 \(s\) 中的其他元素值保持不变。

利用上述思路，我们可以将待操作的数组看做已经维护好的前缀和数组 \(s\)，并利用 \(a_i=s_i-s_{i-1}\) 维护出数组 \(a\)，后续如果需要频繁地给待操作数组 \(s\) 进行区间修改，只需要 \(O(1)\) 地修改 \(a\) 数组的两个边界即可。这里的 \(a\) 数组就叫做差分数组，这种修改思想就被称为差分算法。

综上所述：

  • 前缀和算法高效的前提是数组元素尽可能保持不变。如果需要频繁地变动数组元素，利用前缀和算法进行区间求和就不合适了；
  • 差分算法高效的前提是不需要频繁地索引数组元素，如果需要频繁地索引数组元素，利用差分算法进行区间修改也就不合适了。

Tip

如果需要同时频繁地「区间修改、区间查询」，可以使用进阶数据结构诸如 树状数组 或 线段树 来实现。

二分

二分本质上是对「单调序列」进行加速查询的操作。按照不同思考问题的角度，二分算法又分为二分查找与二分答案，其中二分查找可以理解为由因及果，而二分答案可以理解为由果追因。

二分查找

如果你会按照字母的顺序查字典，那么你一定可以立刻理解二分查找算法。一般地，假设有一个含有 \(n\) 个元素的序列 \(a\)，其属性 \(attr\) 是单调递增的。现在想要查询属性 \(attr\) 取值为 \(tar\) 的元素在序列中的位置 \(idx\)。显然我们可以遍历一边序列 \(a\) 得到结果，但由于属性 \(attr\) 是单调的，在下标范围为 \([l,r]\) 的序列中查找时，只需要不断比较 \(a_{(l+r)/2}\) 和 \(tar\) 的值即可，具体地：

  • 如果 \(a_{(l+r)/2}>tar\)，那么 \(idx\) 一定在 \([l,(l+r)/2]\) 中；
  • 如果 \(a_{(l+r)/2}<tar\)，那么 \(idx\) 一定在 \([(l+r)/2,r]\) 中；
  • 如果 \(a_{(l+r)/2}=tar\)，那么 \(idx\) 就是 \((l+r)/2\)。

这类题目一般都可以归纳为：给定自变量 \(x\)，问在满足某个约束的情况下，\(x\) 的最值是多少。假定 x 的值域为 \([low,high]\)，那么这里的 \(x\) 在 \([low,lim]\) 时是满足（不满足）约束的，在 \([lim,high]\) 是不满足（满足）约束的。这种性质也被称为「二段性」，具备了这种性质，我们直接在 \(x\) 的值域中二分查找 \(lim\) 即可。

二分答案

二分答案其实就是二分查找，只不过你需要敏锐地发现需要「待求解的答案」与「满足约束的状态」满足上文提到的二段性，仅此而已。

递归

递归是编程入门的最后一关，也是打开新世界的钥匙。所谓递归，就是让一个函数自己调用自己从而实现一系列诸如：搜索、分治、回溯等算法。

关于递归函数中调用自己的操作，你可以先不用 care 她到底是怎么执行的，你只需要关心她到底做了什么。比如现在有一个需求，需要封装一个函数 sum(x) 返回 \(\sum_{i=1}^x,\ (x\ge 1)\) 的计算结果。你完全可以写出下面的程序：

1
2
3
4
5
6
7
int sum(int x) {
    int ans = 0;
    for (int i = 1; i <= x; i++) {
        ans += i;
    }
    return ans;
}

但如果使用递归，就可以不用 for 循环，比如下面的程序：

1
2
3
4
5
6
int sum(int x) {
    if (x == 1) {
        return 1;
    }
    return x + sum(x - 1);
}

你不需要关心 sum(x - 1) 到底发生了什么，你只需要知道她算出了 \(\sum_{i=1}^{x-1}\)，那么再加上 \(x\) 就是\(\sum_{i=1}^x\)，是不是很简单？

当然，你一定发现了第三行的 return 语句，这是为了让函数递归调用自己时有一个终点。所有的递归函数都有一个终点，如果递归的终点是可控的，就可以不写 return 语句（比如在遍历图时），但上述程序的终点显然是不可控的，因为程序并不知道什么时候不需要再调用 sum(x - 1)。

推而广之，所有使用递归思想的算法都有同一套逻辑：

1
2
3
4
5
return_type function_name(param) {
    // 1. 递归终点处理逻辑
    // 2. 当前状态处理逻辑
    // 3. 调用自己解决逻辑一致但规模更小的子问题
}

现在可以学习使用递归逻辑的一系列算法了。

搜索

所谓搜索，就是在一个「解空间」中通过递归程序将所有可行解搜索出来的算法。这里的解空间可能有些抽象，我们就以一棵根树（可以简单查阅一下 树 的定义）为例。假设一个问题的解空间就是一棵根树（无环连通图，后用树代称），答案就存在树中的某些结点上。那么我们要做的就是遍历这棵树从而找到所有的可行解。

那么问题来了，怎么遍历？我们知道树有着很多优美的性质，比如以任意一个结点为根都对应了一棵和根树完全一样的结构，而这恰好满足前文所说的「逻辑完全一样但是规模更小」的递归性质。因此遍历一棵树只需要两个逻辑：

  1. 遍历当前结点；
  2. 遍历当前结点的所有子结点。

而这，就可以称作搜索。以上述树的搜索为例，就有下面的伪代码：

1
2
3
4
return_type search(int node_index) {
    // 1. 处理当前结点
    // 2. 遍历所有子结点
}

没有返回值？确实。如果我们单纯的遍历一棵树，是不需要返回值的，因为当前结点的所有子结点都遍历结束后，程序就会开始回溯。相比于上面的 sum(x) 函数，这里的递归终点是已经存在的。

分治

分治是一个很有意思的递归算法，其在上述搜索算法基础之上更进一步。分治算法的核心思想是将原问题转化为多个互不重叠（互斥）的子问题，通过优先求解子问题，来加速原问题的求解 1。例如 归并排序算法 就是分治的经典例子。当然，古有”分而治之，逐个击破“一说，也就是这个思想了。

分治算法可以总结为以下三个步骤：

  1. divide。将原问题问题划分为多个互不重叠的子问题；
  2. conquer。递归处理子问题；
  3. combine。联合子问题的处理结果加速计算原问题的求解。

当然，如果一个问题无法拆分为多个互斥的子问题，分治算法就不适用了，此时可以采用更高效的 动态规划 算法来尝试解决。

回溯

回溯算法在上述分治的基础之上更进一步。其实按理来说，递归函数的出栈就是回溯，但是这里介绍的回溯更多侧重于递归函数回溯后返回给当前问题的结果。举个例子，我们看看校长是怎么惩罚翘课学生的：从最高的校长开始，ta 不 care 你上没上课，ta 只需要向各个学院的院长询问情况即可，而各个院长也不 care 你上没上课，ta 们只需要向所有年级的辅导员询问情况即可，而辅导员也不 care 你上没上课，ta 们只需要向所有的任课老师询问情况即可，任课老师上课点名了，你没来？那你有福了，任课老师和辅导员说你没来上课，辅导员和院长说你没来上课，院长和校长说你没来上课，校长知道了，那你彻底凉了（才怪）。

至此一个现实场景中的回溯策略就淋漓尽致地体现出来了。通过将原问题划分为多个不重叠的子问题，按照相同逻辑处理完子问题后，原问题得到了所有子问题的解，基于这些子问题的解就可以得到原问题的解，这就是回溯的思想。

总结一下。聪明的你一定发现了，搜索、分治和回溯是层层递进的。搜索是正向试探的勇士，不断的寻找可能的结果，分治是懂得偷懒的领导，通过合理分配工作达到最佳办事效率，而回溯则是顾全大局的谋士，基于所有的已知结果做出最终的选择。

排序

很多教程或教材都喜欢把这一块单独拿出来讲，可能因为排序算法是很多算法策略的具体实现。但这里有一些算法并不适合新手学习，如果遇到不怎么懂的排序策略，请先跳转到对应的知识点进行学习，之后再过来学习对应的排序算法会好很多。此处只讨论「快速排序」、「归并排序」和「堆排序」三种较为复杂的排序算法，其余排序算法请自行查阅。

首先讲一个排序衍生出的概念：稳定性。如果一个排序算法，在对所有元素排序后，原来相同关键字的顺序保持不变，则称该排序算法是稳定的，反之如果相同关键字的顺序改变了就称该排序算法是不稳定的。

快速排序

这是一种不稳定的排序算法，核心思想是分治。具体地，以升序为例，如果一个序列是有序的，那么对于该序列中的每一个元素，其左边所有元素都应该比右边所有元素小。基于该先验，我们就有了快速排序算法：

  1. 选择序列中任意一个元素作为基准；
  2. 基于该基准，扫描一遍序列将比基准小的元素排在基准的左边，比基准大的元素排在基准的右边；
  3. 递归左右两边的序列直到序列只有 1 个元素为止。

在计算时间复杂度时，我们可以将分治的逻辑想象成一棵二叉树，对于二叉树的每一层都会有 \(O(n)\) 的遍历开销，而二叉树的层数平均有 \(O(\log n)\) 层，因此排序的时间复杂度就是 \(O(n\log n)\)。当然如果每次选择的基准刚好是所在序列的最值，就会导致二叉树的层数退化到 \(O(n)\)，但一般来说不会这么极端。

归并排序

这是一种稳定的排序算法，核心思想同样是分治且符合标准的三步分治策略。同样以升序为例，如果两个有序序列都是升序或都是降序，那么可以双指针扫描一遍从而 \(O(n)\) 地合并这两个序列为一个有序序列。基于该先验，我们就有了归并排序算法：

  1. 将序列等分为左右两部分；
  2. 分治左右两部分使得左右两部分都是升序或都是降序；
  3. 合并左右两个有序序列。

时间复杂度的计算与快速排序类似，只不过这里的分治递归二叉树一定是 \(O(\log n)\) 层，那么时间复杂度就是稳定的 \(O(n \log n)\)。

堆排序

这是一种不稳定的排序算法。其实就是利用了堆结构及其支持的操作，每次输出堆顶然后维护堆结构即可实现堆排序。因此如果掌握了 堆 这一数据结构，堆排序算法就跃然纸上了：

  1. 将给定的序列维护成堆结构；
  2. 每次输出堆顶并重新维护堆结构即可。

为了计算堆排序算法的时间复杂度，我们分别考虑算法的两步中对应的计算开销：

  1. 对于维护堆结构。可以利用完全二叉树的性质，对于一个大小为 \(n\) 的完全二叉树，其后 \(n/2\) 个元素都一定满足堆的定义，因此只需要对前 \(n/2\) 个元素执行 down() 操作即可，经过简单的错位相减运算可以得出该操作是 \(O(n)\) 的；
  2. 对于输出堆顶并重新维护堆结构。输出是 \(O(1)\) 的，重新维护堆结构其实就是删除完全二叉树的根结点，这里有一个技巧，就是将数组中的最后一个树中元素替换掉数组中的第一个元素（即根结点），然后 down() 这个新的根结点即可实现重新维护出一个堆结构，这样对于 \(n\) 个元素，每次都要 \(O(\log n)\) 地 down() 一次，那么就是 \(O(n\log n)\)。

最终的时间复杂度就是 \(O(n\log n)\)。

  1. Divide-and-conquer algorithm | WIKIPEDIA - (en.wikipedia.org) ↩