猫史档案馆

我为什么要写

 

我们在论坛或其他地方时常看到有人这么说：

算法除了竞赛没什么用，不学也不要紧。

以及

别学了，算法是没用的。

真的如此吗?

 

OI中有一句话：程序设计=算法+数据结构。

我认为这句话可以推广到更广泛的地方，从计算机科学到信息技术，这两者都是必须且核心的。

暂且抛开《算法导论》中对算法的定义不谈（按照那个严格的定义，数据结构也属于算法），我们从OI和IT、计科等方面常说的算法谈起。

 

 

概说

 

 

算法和数据结构有一个共同的目标：高效、正确地解决问题。这两者都是为了这个目标而出现的，只是角度不同。

 

就我个人认为，数据结构 不严谨地 可以看成是两种用途。第一种用于建立模型，处理问题，比如 R-B Tree 等；第二种用于辅助算法的实现，如一些线性表。

 

算法，通俗的讲，则是对求解一类问题的方法的阐述、优劣和正确性的证明。你要如何去解决，为什么这是正确的，它好在哪里。比如动态规划算法，它涵盖了分割问题、逐步转移的思想；再比如随机化算法，是一种不要求完全精确但效率很高的一种方法。

 

 

算法是什么及用途，以什么为基础

 

 

前面说过，暂时不讨论算导和OI中对算法的准确概念。我用通俗的语言来介绍一下。

 

算法要能够解决一类问题，或提供一种方法，一个结论并且如何去用这个结论等。

 

部分算法是对一个模型（数据结构）上进行的操作；有的算法直接考虑用计算机解决数学问题，这在一些多项式算法、线代算法、组合数学和统计学相关的算法中出现；还有的算法侧重于介绍一类解决问题的方法或思想。大多数算法能用某些数据结构来抽象其运行过程（但有些的确有点牵强）。

 

算法需要保证是正确或近似正确的。通常我们会有一些数学证明或者分析过程来证明其正确性。

一个算法必须有其复杂度的分析，包括空间复杂度和时间复杂度。我们用函数 T(n) 来表示运行所需的时间的解析式。对于函数 T 的增涨，我们有渐进记号 O（渐进上界），Ω（渐进下界）和 Θ（渐进紧确），因此也称为渐进复杂度。

 

正确性证明和渐进复杂度是评判一个算法的核心之一，数学明显是这两者的基础。

 

 

 

数据结构及其用途，与算法的联系

 

 

我并不给出数据结构的严格定义。我们通过几个例子来看看数据结构有什么用，以及它与算法的联系。

 

先来看这么一个问题：

初始给定一串序列，支持两种操作：将某区间每一个数加上 k；求出某区间每一个数的和。需要支持在线回答。

 

我们粗看的时候，当然是每个修改都线性时间一个一个增加，需要回答的时候就线性时间一个一个求和。

但是很多时候这并不能满足效率的要求。我们必须寻求更快的方法。

 

一种常见的方法是线段树，即构建一个完全二叉树，每个节点对应区间；需要修改、求和时，计算一条路径上的贡献和修改标记即可。

 

另一种速度稍慢，但是空间开销更小的做法，即常说的分块。我们将序列分为根号 n 块，如果询问涵盖了整个块，直接标记；剩下的再单个累加。需要回答区间查和的时候，也是整块的累加，零散的再一个一个去求和。这样时空复杂度达到了平衡。

 

上述都是在序列操作的两种数据结构，一个是线段树，一个是分块。看我们也看到，线段树具有分治思想；而分块有大段维护，小段朴素的思想。它们为什么不能是算法呢？

 

这是数据结构的一个用途，即对数据按照结构适当处理以改善解决问题的时间和空间复杂度。

 

数据结构有无其他用途？别急，接着往下看。

 

我们知道，动态规划是一种用于求解最优化问题的算法。那么我们能否抽象地描述动态规划，来显现出其求解过程（而非正确性证明）呢？当然也是珂以的。事实上，动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的状态，图中的边对应状态之间的转移，转移的选取就是动态规划中的决策。因此，事实上，动态规划的决策过程，经过提取之后就是在图这个数据结构上的操作。

 

再比如，递归本身是一种处理问题的思想，其所有都珂以由数学方法推出。但其实现的结构同样可以表示为一棵树，每一个结点对应每一次处理。递归的过程就是对树的遍历。所以也可以说，递归思想将问题构建成树并遍历求解。

 

因此数据结构有另一个用途：建立模型解决问题。

 

这个用途除了上述之外，著名的图就是另一个栗子。在这种数据结构中，它对数据建立模型，使其一般化并高效处理。而随之而来的是图算法，它们用于解决图上的问题。这就是图论。

 

因此，数据结构同样绝非计算机科学所独有。例如图，本身就是离散数学和拓扑数学的重要研究对象。

 

 

 

总结一下

 

两者都以数学为基础。算法侧重于对一方法、结论或思想的阐述、证明、分析；数据结构侧重于建立模型或恰当处理数据。它们最终都是为了高效、正确地解决问题。

 

 

 

算法和数据结构的举例，
他们在实际应用中的重要用途

 

 

排序

 

排序是一个算法的基础。它在处理一切问题的时候都是必须的。

一个没有学过算法的程序员写的排序算法的复杂度会比一个精通算法的人差得多，因此其程序也不太可能比后者优秀。（当然不会 log 级别的排序不太珂能。）

 

映射

 

映射就不是所有人都会的了，但它的用去同样非常普遍。

离散化是一种结合排序的映射方法，它能有效缩小数据规模；哈希则是类似的，但并不需要借助排序，用途也更广。

映射应用非常广泛，大多数程序员都会。但是能够精通的人并不是特别多。

 

二分法

 

二分法用于寻找具有单调性的区间内的解。

我们经常遇到一些涉及函数求解的问题。当没有求根公式的时候，二分法是一个很好的迭代方法。

如果应用中，待求解的量和限制条件具有明显的单调性，二分法还可以用于快速寻找双最值问题，即将问题巧妙的转化为函数求解，二分判定一个解能否满足问题。

 

动态规划

 

动态规划博大精深，这里当然不可能有篇幅去介绍。但我粗略的讲解一下。

通过前面的介绍想必大家对动态规划已经有所了解。它用于有效地求解一类最优化问题。这类例子很多，例如前面写过另一篇dp教程中的几个例子。

 

单调队列

 

单调队列是一种特殊的数据结构，应用广泛。

单调队列内部元素具有单调性，在原序列中的位置也严格单调递增。

 

线性规划

 

将线性规划应用到动态规划上来。如果两个决策和相关量映射到坐标系上，能具有斜率单调，则可以结合单调队列将复杂度降低次数，即斜率优化动态规划。

同时，线性规划算法还是计算机和数学中实际应用极其广泛的，是所有程序员或 OIer（甚至高中生，但是没有要求用程序实现）的必修内容。

 

 

前四者的结合？

 

对于一些复杂的问题，我们使用单调队列维护斜率凸壳，同时附加一个 val 值，这样，转移次数越多最终结果越大。以此来二分判定一个值，从而求出一类问题。

这是前四者的结合，是为wqs二分。

多数程序员对此处并不精通甚至不了解。但是，如果某一位能够精通此方面，会比前者在至少这四块掌握更深，并能写出更优秀的代码。

 

线段树

 

试想这么一个问题：

你需要维护一段序列。有一些操作，涉及区间乘法、区间加法、区间查和、单点求值。在线询问。

这个问题有很强的实用性。解决此问题在很多程序中非常关键，且其应用范围也非常广泛。可以说，如果你想要写程序来应用于某一方面，大多数需要解决这个问题。这就需要线段树。

 

接着思考一个延伸的问题：

如果一开始是多个相同的区间，每次在某一个区间内操作。等所有操作结束后，我们将这些区间相加，同时维护最大值。

这个问题在很多方面都有广泛的应用。举个栗子，当你需要让不同的用户分别操作，然后再每一组和起来的时候就要用到。

 

再思考：

如果该应用要求用户能够查询历史操作，这该怎么办？

对于第一个问题，我们需要使用线段树合并，而第二个问题，我们可以构建可持久化线段树。

 

下面来看看线段树的另一些应用。

假设在一个坐标系内，你需要求若干矩形的面积。你该如何办？

这需要将矩形排序、去重，完成离散化，然后用线段树来维护。

这个问题有大量的实际例子，是为扫描线问题。

 

 

分块

 

分块在上文已经提及，即大段维护、小段朴素。

 

分块还有很多应用，例如查询区间众数等。区间众数可以应用于统计学。这就是计算机通过数学来解决实际问题的一个例子。

 

下面来看一看分块还能分什么：

假设你需要维护一段序列的区间平方和，没有修改操作。这怎么办？

我们可以将询问强制离线，按照左端点所在的块作为第一关键字、右端点作为第二关键字排序，然后使用一个移动区间，每次计算贡献即可。这就是对询问进行离线，即莫队算法。

 

 

平衡树

 

 

平衡树是计算机科学和信息技术中非常重要的一种数据结构，就我所知用途仅次于排序等最基础的算法。

 

我们看一个例子：

维护一段序列。需要支持：
插入一个数；
删除一个数；
求一个数的排名；
求排名为 x 的数；
求这段序列中小于 x 的最大的数；
求这段序列中大于 x 的最小的数；
询问在线。

 

这就需要我们的平衡树。在这个例子中，我们只需要先构建一棵二叉搜索树，然后随即赋予权值并使它满足堆性质即可，因此这是一个笛卡尔树，这种平衡树称为Treap（Tree+heap）。

 

但假如我们要能够让某一个区间翻转呢？

这需要另一个适用范围更广的平衡树，即伸展树（Splay）。

 

其他的平衡树还有很多，例如R-B Tree（红黑树），替罪羊树，B树等等。

 

平衡树对数据的处理能够实现的问题几乎是所有程序中必备的。因此，一个程序员至少会掌握Trreap和R-B Tree，而OIers更偏向Treap,Splay和一些可持久化平衡树（因为竞赛中写其他的平衡树时间不够）。

 

 

字符串算法

 

 

字符串算法我会的不多，因此不详细展开。但是字符串算法或许是各位能够想到的第一个算法的应用。文字匹配、查询关键字以及对文字的理解、处理都需要靠字符串算法。

我并不知道大多数程序员会不会像SAM这类的字符串算法，但至少我是没有学会过。（我想有些程序员或许很有可能不会，但他们一些简单的字符串算法还是会的）

 

 

 

另一个例子：科学计算与人工智能

 

 

科学计算是计算机非常重要的一项应用。珂能大家对它了解不多，但我在学习计算机科学的理论知识的时候计算机的第一个应用确实是它。

 

我在读《宇宙的琴弦》的时候，发现书中的作者和其他一些物理学家和数学家都在使用计算机帮他们核对手算的结果，有些时候甚至直接让计算机来算。同时，在航空航天等领域，计算机更是发挥了举足轻重的作用。

 

我们前面讲过的求函数的解、求区间众数就是两个例子。下面再举一些。

求函数的最值就是一个典型的应用。我们有一个随机数算法能够近似的解决它，即模拟退火。该算法我在之前就讲过了，这里不重复介绍。

 

 

那么剩下的就留给我们的人工智能吧

 

其实我一开始并没有直接去找人工智能的资料，我先搜了“机器学习”。咱们问一问百度：

机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。
它是人工智能核心，是使计算机具有智能的根本途径。

我们看到了在介绍算法时许多提到过的东西，当然也有我们没看到的。

 

概率论它的基础是什么？没错，就是离散数学。

关于离散数学的计算机实现，我们有诸多算法。能够使用这些算法，其有效程度比一般的人写程序解决要高得多得多。

 

但是我们还需要一个有力的工具来实现机器学习的大部分内容。我们如何快速的运算？如何快速的求出一系列关系？如何有效解决一些多项式计算？

没错，多项式算法！

 

很多人认为，乘法只需要简单的一个运算符。但是如果数据很大呢？我想大多数会想到直接高精度，有些人会说“Python不是可以直接实现的吗”，但是这并不正确。我们需要两个强大的算法，即快速傅里叶变换（FFT）和快速数论变换（NTT）。这是处理大型数据的第一步（当然，我指的是对数据的直接处理，这里不太需要借助平衡树等数据结构，否则那些才是最基础的）。

 

接下来，我们要运用NTT来解决一些实际问题。

除法是乘法的逆运算。为此，我们有适用于不同方面的两个算法：多项式求逆、多项式（带余）除法。

函数是分析、处理数据的一个非常重要的模型和工具。对于一些很大的数据，我们借助NTT和一些微积分的知识，有多项式对指开根、正反三角函数（对数函数，指数函数，多项式开根，三角函数，反三角函数）。

我们如何让电脑能够做一些其他的求解呢？借助NTT和一些代数、分析学知识，我们有多项式插值、多项式快速插值、多项式多点求值的算法。

 

我们如何让计算机能够对一些图形和图像进行处理？这就需要计算几何相关算法。计算几何包括凸包、旋转卡壳、半平面交等，在多个领域内都有非常重要的应用，自然也是人工智能的基础。

 

同样，随机化算法也非常重要，除了前面提到的模拟退火，我们还有随机化贪心等。

 

对于人工智能的一些算法的设计，我们通常需要借助迭代法。

 

计算机在人工智能方面必然要做出决策。除了前面提到的动态规划，我们还有博弈论相关算法。有些问题需要构建决策树来解决问题。在这些方面，字符串算法也显示出了它的用途。它可以用于语言的理解。

对于计算机关于概率方面的计算，我们有很多的算法、公式等等，例如数据的分析，概率的计算，数学期望等。很多时候没法直接求出来，因此这时候也需要动态规划算法。这类问题在人工智能方面的应用应该是协助计算机做出决策。

 

 

 

最后的例子：图论

 

 

计算机处理问题，还有一些非常重要的模型。图就是一个例子。

我们通过建图，能够解决非常多的实际问题。

网络流是应用非常广泛的一类算法，其中包括了二分图。它能够对大部分的流量分配问题、人员匹配问题做出恰当的解决。

图的连通性也是非常重要的，有很多应用。关于连通性各位可以去找找我之前的教程，思考其用途，这里不再说了。

我们通过建图、迭代、模拟、随机化算法能够对大多数的实际问题建立模型，并预测、分析。者在人工智能方面也是非常基础、必备的。同时，计算机的诸多学习相关的算法，也一般离不开上面提到的内容和多项式算法、一些离散数学和概率的算法。

 

 

 

最后的最后

 

 

在实际应用中，当然需要结合各种算法和数据结构，而不仅仅是某项或某一些。这也是难点之一。能否恰当地运用算法合数据结构，很大程度上决定了程序的优劣、写出的代码的有效程度。

我们看到，多数程序员的算法水平不如一个正规的OIer。而OIers普遍的问题是，认为算法和数据结构并没有实际用途，这是大错特错的。从某种程度上说，一个程序员的算法水平高低对于他能否称为精英人士有着非常大的影响。

 

 

一张我自己的图

 

 

最后附上一份在我Luogu个人首页上的一份大纲的截图，以供参考。