算法和数据结构初级|第三课：算法复杂度（上）

作者 谢恩铭 转载请注明出处
公众号「程序员联盟」（微信号：ProgrammerLeague ）
原文：https://www.songma.com/p/14982c42b2d8

内容简介

1. 算法的正确性
2. 算法的复杂度
3. “渐近”度量
4. 第四课预报

1. 算法的正确性

上一课 算法和数据结构-初级 | 第二课：小鸭子们去旅行 中，我们讲了一个有趣的小故事，就是为了引出算法复杂度。

算法复杂度非常重要，要讲的内容也很多，所以我们分为上下两课

当程序员需要处理计算机科学相关的问题时，他们（通常）会编写一个程序。这个程序包含一个实现，也就是说需要把算法使用一种编程语言来实现。

我们知道，算法只是对处理问题的步骤的一种准确形容，它并不依赖于程序员所使用的编程语言或者工作环境。

我们在 算法和数据结构-初级 | 第一课：什么是算法和数据结构 里详情了一个“煮方便面”的食谱，这份食谱尽管简单，但可以说是一个算法。

我们是使用中文来形容这份食谱的，假如我现在把这份食谱翻译成一门外语（比方 英语），但食谱的内容还是不变，只不过换了一种语言来说明罢了。换个英国人来照着这份英文食谱煮方便面，跟我做出来的会是一样的。

那么，当程序员需要把算法使用一种编程语言来实现时，需要做什么呢？

像农夫 Oscar 一样，他必需首先验证他的算法是正确的，也就是说它产生了预期的结果，处理了所涉及的问题。这非常重要（假如算法不正确，那我们根本没有选择和优化它的必要），有时验证算法正确性是非常难的一步。

算法的正确性，英语是 Algorithm Correctness。要证实算法的正确性，有许多方法，我们本课程就不详述了，由于这不是我们的重点。大家有兴趣可以去网上搜索一下。

当然了，算法正确了，并不能保证明现这个算法的程序就没有错误（bug）：
一旦我们有一个正确的算法，我们使用编程语言去实现它（通过编写一个执行它的程序）。但我们可能会写出有很多小错误的程序，这些小错误也许和所用的编程语言有关，它们可能在编写程序的过程中被引入。由于算法中一般不会形容如何管理程序的内存，或者者如何检查段错误（Segmentation Fault），等等，但这些都是程序员实现算法时需要考虑的问题。

2. 算法的复杂度

一旦程序员确信他的算法是正确的，他将尝试评估其效率，比方他会想知道“这个算法快不快”。

有人可能会认为，要知道算法快不快的最佳方式是实现该算法并在电脑上进行测试。

有趣的是，通常情况并非如此。例如，假如两个程序员实现了两种不同的算法，并在各自的电脑上测试程序运行的快慢。那么拥有更快速度的电脑的那个程序员可能会错误地认为他的算法更快，但其实并不肯定。

而且，要实现一个算法并测试，有时候并不容易。且不说有时候根据一个算法要写出代码很难，假如要实现的算法涉及到一枚火箭的发射，难道每次使用一枚真的火箭来发射一下去测试算法快不快吗？我们又不像钢铁侠那么有钱可以任性。

出于这些起因，计算机科学家们发明了一个非常方便而强大的概念，也就是我们接下来要学习的：算法的复杂度。

“复杂度”（Complexity）这个词有点误导人，由于我们这里不是强调“了解起来有困难”（很复杂，很难），而是指效率 。

“复杂度”并不意味着“复杂的程度”。有的算法了解起来很难（很复杂），它的复杂度却可以非常低。

假如我给我的程序一个大小为 N 的输入，那么它将执行的操作的数目的数量级是 N 的一个怎样样的函数（f(N)）呢？

算法的复杂度基于以下事实：处理问题的程序也取决于问题的条件：假如条件改变，程序执行的时间也会变长或者变短。

复杂度可以量化（通过数学公式）起始条件与算法执行的时间之间的关系。

为了“计算操作的数目”，我们必需首先定义什么是操作。对于这个问题，即便是绝顶聪明的科学家可能也无法非常明确地答复。由于选择哪些操作来做计算取决于所考虑的问题（甚至是算法）。

我们必需选择算法经常执行的少量操作，并且将其作为度量算法复杂度的基准。

例如，要制作煎鸡蛋，可以考虑三种基本操作：打破鸡蛋、铲碎正在煎的鸡蛋、煎熟鸡蛋。因而，我们可以计算每份煎鸡蛋的菜谱中的鸡蛋数目，从而理解菜谱（算法）的复杂度（煎鸡蛋是一个众所周知的菜，我们可以预期所有煎鸡蛋的菜谱都具备相同的复杂度：对于 N 个鸡蛋，我们进行 3N 个操作）：增加盐、葱、胡椒或者其余佐料的操作非常快，不需要考虑在菜谱（算法）复杂度之内。

又例如，在上一课农夫 Oscar 的情况下，装小鸭子的大箱子是 N 行 N 列，那么假如 Oscar 采取第一种旧的算法，他须要在池塘和卡车之间进行 N²（N 的平方）趟来回；假如使用第二种新的算法，他却只须要 N 趟来回。

这是复杂度的一种很好的度量方式，由于农夫 Oscar 在池塘和卡车之间来回这个过程是算法的所有操作里其耗时最长的。其余少量操作相对来说不那么耗时，比方 Oscar 从大箱子里挑出一只小鸭子，讯问小鸭子要去哪个池塘，等等。

因而，我们可以说，此算法的总时间几乎主要花在池塘和卡车之间来回这个操作上了，所以它可以作为度量此算法的效率的标准。

假如复杂度的概念对你来说还是有点模糊，请不要担心，之后的实践应该会让你豁然开朗。

3. “渐近”度量

我们可以说：复杂度是算法的渐近行为的度量。

那么，这个比较复杂的词“渐近行为的度量”是什么意思呢？

这意味着“当输入变得非常大”（甚至“趋于无限”）时。这里的“输入”是算法的起始条件的一种量化。在农夫 Oscar 的情况下，这将意味着“当大箱子里有很多行/列小鸭子”时，例如 N 是 250。在计算机科学中，“很多”的含义却略有不同：例如搜索引擎会说“有很多网页”，1 万亿个网页...

“当输入变得非常大”（甚至“趋于无限”）时会有两种结果：

一方面，恒定的时间（常量，constant value）不予考虑。由于“恒定的时间”不依赖于输入。

例如，在农夫 Oscar 开始将小鸭子们带到每一个池塘去之前，他会先打开卡车的后车门。打开卡车后车门的时间被认为是“恒定的”：不管他的大箱子里有 20 行 20 列小鸭子还是有 50 行 50 列小鸭子，开后车门都是花费相同的时间。因为我们要考虑在大箱子的行/列的数目非常大的时候算法的效率，因而与 Oscar 在池塘和卡车之间来回的时间相比，打开卡车后车门的时间可以忽略不计。

另一方面，“常数乘法因子”也不予考虑：复杂度的度量不区分执行 N、2N 或者 250N 个操作的算法。为什么呢？我们考虑以下两种取决于 N 的算法：

第一种算法：

做 N 次（操作A）

第二种算法：

做 N 次（操作B 而后 操作C）

在第一种算法中，我们做 N 次 操作A；在第二种算法中我们做 N 次 操作B，N 次 操作C。假设这两种算法处理了同样的问题（所以都是正确的），并且所有操作都被考虑进复杂度的度量中：那么第一个算法做了 N 个操作，第二个算法做了 2N 个操作。

但我们可以说哪个算法更快吗？当然不行。由于这取决于 A、B、C 这 3 个操作所花费的时间：也行 操作B 和 操作C 都比 操作A 快 4 倍，那么总体来看，操作数为 2N 的算法比操作数为 N 的算法反而更快，由于 1/4 + 1/4 = 1/2（操作B 和 操作C 的耗时是 操作A 的四分之一）。

乘法因子不肯定对算法的效率具备影响，因而在复杂度的测量中不予考虑。

这也使我们能够答复一开始的那个问题：假如两个程序员有两台计算机，一台比另一台平均速度快 5 倍。5 这个常数乘法因子将被忽略，因而两位程序员可以毫无问题地比较算法的复杂度。

所以说，我们忽略了很多东西，这使得我们能有一个相当简单和普遍的概念。这种普遍性使复杂度成为一个有使用的工具，但它也有显著的缺点：在某些非常特殊的情况下，更复杂的算法居然可以使用更少的时间来完成（例如，常数因子在实际中也许能扮演非常关键的角色：假设农夫 Oscar 的卡车后车门卡住了，他竟花了一终日的时间来打开后车门）。

然而，在绝大多数情况下，复杂度仍是算法性能的可靠指标。特别是当两个复杂度之间的差距由于输入的增大而变得越来越大时。一个有 N 个比较耗时的操作的算法也许在 N 是 10 或者 20 的时候比另一个有 N²（N 的平方）个不那么耗时的操作的算法运行时间更长，但对于 N 是 2万 或者 N 是 5 百万的情况，复杂度更低的算法将一定是更快的。

4. 第四课预报

今天的课有点难度，不妨多读几遍。下一课我们继续研究算法的复杂度。一起加油吧！

下一课：算法和数据结构-初级 | 第四课：算法复杂度（下）

365 天，每天坚持写作之 3 / 365，爱上你的每一天！

我是 谢恩铭，在巴黎奋斗的软件工程师。
酷爱生活，喜欢游泳，略懂烹饪。
人生格言：「向着标杆直跑」