计算机科学精粹，第二章：复杂度

在几乎所有计算中，过程的排列方式多种多样。选择能够最大限度地减少计算所需时间的排列方式至关重要。

— 艾达·洛芙莱斯

对 26 张洗过的牌进行排序需要多少时间？如果改为 52 张牌，需要的时间是两倍吗？一千副牌需要多长时间？答案取决于用于排序牌的**方法**。

方法是指实现目标的一系列明确指令。始终需要有限系列操作的方法称为**算法**。例如，卡片排序算法是一种始终会指定某些操作来按花色和等级对 26 张牌的牌组进行排序的方法。

操作越少，所需的计算能力就越少。我们喜欢快速解决方案，因此我们会监控算法中的操作数量。许多算法在输入大小增加时需要越来越多的操作。例如，我们的卡片排序算法可能需要很少的操作来对 26 张牌进行排序，但对 52 张牌进行排序时需要四倍的操作！

为了避免在问题规模增大时出现意外情况，我们需要找到算法的**时间复杂度**。在本节中，您将学习如何

• 计算并解释 时间 复杂度
• 使用花哨的**大 O** 表示其增长
• 避开**指数**算法
• 确保您有足够的计算机**内存**。

但首先，我们如何定义时间复杂度？

时间复杂度写成$T(n)$. 它表示算法在处理大小为$n$的输入时执行的操作数。我们也称算法的$T(n)$为其**运行成本**。如果我们的卡片排序算法遵循$T(n)=n^2$, 我们可以预测将牌组大小加倍后对牌组进行排序需要多长时间$\frac{T(2n)}{T(n)}=4$.

抱最好的希望，做好最坏的准备

对几乎已经排序好的牌堆进行排序不是更快吗？

输入大小并不是影响算法所需操作数量的唯一特征。当算法可以对同一$T(n)$值有不同的$n$值时，我们会诉诸于情况

• 最佳情况：当输入对于该大小的任何输入都需要最少的操作数量时。在排序中，当输入已经排序时会发生这种情况。
• 最坏情况：当输入对于该大小的任何输入都需要最多的操作数量时。在许多排序算法中，当输入以相反的顺序给出时会发生这种情况。
• 平均情况：是指对于该大小的典型输入，所需的平均操作数量。对于排序，通常认为随机顺序的输入是典型的。

一般来说，最重要的是最坏情况。从那里，您可以得到一个始终可以依赖的保证基线。如果没有说明情况，则假设最坏情况。接下来，我们将看到如何分析最坏情况场景，动手操作。

2.1 计算时间

我们通过计算算法对大小为$n$的假设输入所需的基数操作数来找到算法的时间复杂度。我们将使用**选择排序**来演示，选择排序是一种使用嵌套循环的排序算法。外部 for 循环更新当前正在排序的位置，内部 for 循环选择要放在当前位置的项目¹

function selection_sort(list)
    for current ← 1 … list.length - 1
        smallest ← current
        for i ← current + 1 … list.length
            if list[i] < list[smallest]
                smallest ← i
        list.swap_items(current, smallest)

让我们看看在假设最坏情况下的情况下，包含$n$个项目的列表会发生什么。外部循环运行$n-1$次，每次运行执行两个操作（一次赋值和一次交换），总共$2n-2$个操作。内部循环首先运行$n-1$次，然后运行$n-2$次，$n-3$次，依此类推。我们知道如何对这些类型的序列求和²

	$\text{内部循环运行次数}=$	$\stackrel{n–1\text{外部循环的总运行次数。}}{\overbrace{n–1\hspace{1em}\hspace{1em}\hspace{1em}+\hspace{1em}\hspace{1em}\hspace{1em}n–2\hspace{1em}+\hspace{1em}\mathrm{\cdots }+2+1}}$
	$=$	${\displaystyle \sum _{i=1}^{n–1}}i={\displaystyle \frac{(n–1)(n)}{2}}={\displaystyle \frac{n^2–n}{2}}.$

在最坏情况下，if 条件始终满足。这意味着内部循环执行一次比较和一次赋值$(n^2-n)/2$次，因此$n^2-n$个操作。总的来说，算法的成本为外部循环$2n-2$个操作，加上内部循环$n^2-n$个操作。因此，我们得到时间复杂度

$$T(n)=n^2+n–2.$$

现在呢？如果我们的列表大小为$n=8$，我们将其加倍，排序时间将乘以

$$\frac{T(16)}{T(8)}=\frac{{16}^2+16–2}{8^2+8–2}\approx 3.86.$$

如果我们再次将其加倍，我们将把时间乘以$3.90$. 不断加倍，您会发现$3.94$, $3.97$, $3.98$. 请注意，这越来越接近 4？这意味着对两百万个项目进行排序所需的时间是排序一百万个项目所需时间的四倍。

2.1.1 理解增长

假设算法的输入大小非常大，并且我们进一步增加它。为了预测执行时间将如何增长，我们不需要知道$T(n)$的所有项。我们可以用其增长最快的项（称为**主导项**）来近似$T(n)$.

索引卡问题：昨天，您打翻了一个索引卡盒。您用了两个小时的选择排序来整理它。今天，您打翻了十个盒子。您需要多少时间才能把卡片放回去？

我们已经看到选择排序遵循$T(n)=n^2+n-2$. 增长最快的项是$n^2$，因此我们可以写成$T(n)\approx n^2$. 假设每个盒子有$n$张卡片，我们发现

$$\frac{T(10n)}{T(n)}\approx \frac{{(10n)}^2}{n^2}=100.$$

您大约需要$(100\times 2)\text{小时}=200$小时！如果我们使用不同的排序方法会怎样？例如，有一种叫做“冒泡排序”的方法，其时间复杂度为$T(n)=0.5n^2+0.5n$. 然后，增长最快的项给出$T(n)\approx 0.5n^2$，因此

$$\frac{T(10n)}{T(n)}\approx \frac{0.5\times {(10n)}^2}{0.5\times n^2}=100.$$

的$0.5$系数会抵消！$n^2-n-2$和$0.5n^2+0.5n$都像$n^2$一样增长，这个概念并不容易理解。函数的增长最快的项是如何忽略所有其他数字并主导增长的？让我们尝试直观地理解这一点。

在图 2.2 中，我们看到的两种时间复杂度与$n^2$在不同的缩放级别上进行了比较。当我们对$n$的更大值绘制它们时，它们的曲线似乎越来越接近。实际上，您可以在$T(n)=\mathrm{\bullet }{n}^2+\mathrm{\bullet }n+\mathrm{\bullet }$的项目符号中插入任何数字，它仍然像$n^2$.

一样增长。请记住，如果增长最快的项相同，曲线越来越接近的这种效果就会起作用。具有线性增长的函数（$n$）的曲线永远不会越来越接近具有二次增长的函数（$n^2$）的曲线，而具有二次增长的函数永远不会越来越接近具有三次增长的函数（$n^3$).

这就是为什么对于非常大的输入，具有二次增长的成本的算法的性能比具有线性成本的算法差很多。但是，它们比具有三次成本的算法好很多。如果您理解了这一点，那么下一节内容将很容易：我们只需学习程序员用来表达这一点的花哨符号。

2.2 大 O 符号

有一种特殊的符号用于表示增长类别：大 O 符号。增长最快的项为$2^n$ 或更弱 的函数为$O(2^n)$; 增长为二次方 或更弱 的函数为$O(n^2)$; 线性增长 或更少 的函数为$O(n)$, 依此类推。该符号用于在最坏情况下表达算法成本函数的主导项，这是表达时间复杂度的标准方法³。

选择排序和冒泡排序都是$O(n^2)$，但我们很快就会发现$O(n\log n)$可以完成相同工作的算法。使用我们的$O(n^2)$算法，输入大小为 10$\times$时，运行成本为 100$\times$. 使用$O(n\log n)$算法，输入大小为 10$\times$时，运行成本仅为$10\log 10\approx 34\mathrm{\times }$.

当$n$为一百万时，$n^2$为一万亿，而$n\log n$仅为几百万。在大型输入上运行二次方算法需要数年，而如果使用$O(n\log n)$算法，则只需要几分钟。这就是为什么在设计处理非常大型输入的系统时需要时间复杂度分析的原因。

在设计计算系统时，重要的是要预测最频繁的操作。然后，您可以比较执行这些操作的不同算法的大 O 成本⁴。此外，大多数算法仅适用于特定输入结构。如果您提前选择算法，就可以相应地构建输入数据。

某些算法始终在固定时间内运行，而与输入大小无关，这些算法是$O(1)$. 例如，检查数字是奇数还是偶数：我们查看其最后一位数字是否是奇数，然后 砰，问题解决了。无论数字有多大。我们将在接下来的章节中看到更多$O(1)$算法。它们很棒，但首先让我们看看哪些算法不那么棒。

2.3 指数

我们说$O(2^n)$算法是 指数时间 的。从增长阶数的图（图 2.3）来看，二次方$n^2$和指数$2^n$看起来并没有太大区别。将图放大后，很明显指数增长会残酷地压制二次方增长

指数时间增长非常快，以至于我们认为这些算法“不可运行”。它们只对少数输入类型运行，如果输入不是非常小，则需要大量的计算能力。优化代码的各个方面或使用超级计算机也无济于事。压倒性的指数增长始终支配着增长，并使这些算法不可行。

为了说明指数增长的爆炸性，让我们进一步放大图并更改数字（图 2.5）。指数被降低了（从$2$到$1.5$），并且其增长被除以了一千。多项式的指数被增加了（从$2$到$3$），并且其增长被乘以了一千。

有些算法甚至比指数时间算法更糟糕。这是 阶乘时间 算法的情况，其时间复杂度为$O(n!)$. 指数和阶乘时间算法很糟糕，但对于最难的计算问题，我们都需要它们：著名的 NP 完全 问题。在下一章中，我们将看到 NP 完全问题的重要示例。现在，请记住这一点：第一个找到 NP 完全问题非指数算法的人将从克雷数学研究所获得一百万美元⁵。

识别您所处理的问题类别非常重要。如果已知它是 NP 完全的，那么尝试找到最优解就是在与不可能作斗争。除非您正在争取那百万美元。

2.4 计算内存

即使我们可以无限快地执行操作，我们的计算能力仍然有限。在执行过程中，算法需要工作存储来跟踪其正在进行的计算。这会消耗 **计算机内存**，而计算机内存是有限的。

衡量算法所需工作存储的指标称为 **空间复杂度**。空间复杂度分析类似于时间复杂度分析。区别在于我们计算的是计算机内存，而不是计算操作。我们观察到空间复杂度在算法输入大小增长时的演变，就像我们对时间复杂度所做的那样。

例如，选择排序只需要工作存储来存储一组固定的变量。变量的数量不依赖于输入大小。因此，我们说选择排序的空间复杂度为$O(1)$：无论输入大小如何，它都需要相同数量的计算机内存作为工作存储。

但是，许多其他算法需要随输入大小增长的工作存储。有时，不可能满足算法的内存需求。您将找不到具有$O(n\log n)$时间复杂度 和$O(1)$空间复杂度的排序算法。计算机内存限制有时会迫使我们进行权衡。如果内存不足，您可能需要使用时间复杂度较低的算法，因为它具有$O(n^2)$时间复杂度，因为它具有$O(1)$空间复杂度。

结论

在本章中，我们了解到算法在消耗计算时间和计算机内存方面可能有不同的贪婪程度。我们已经看到如何使用时间和空间复杂度分析来评估它。我们学习了通过找到 精确$T(n)$函数，即算法执行的操作数量，来计算时间复杂度。

我们已经看到如何使用大 O 符号（$O$）来表达时间复杂度。在本书中，我们将使用此符号对算法进行简单的时间复杂度分析。很多时候，计算$T(n)$对于推断算法的大 O 复杂度并不必要。

我们已经看到了运行指数算法的成本如何以一种使这些算法对于大型输入不可运行的方式爆炸。我们还了解了如何回答以下问题

• 给定不同的算法，它们的运行所需操作量是否存在显著差异？
• 将输入大小乘以一个常数，算法的运行时间会发生什么？
• 当输入大小增长时，算法是否会执行合理数量的操作？
• 如果算法对于给定大小的输入运行速度过慢，优化算法或使用超级计算机会有帮助吗？

---

¹：要理解新的算法，请使用小型示例输入在纸上运行它。

²：在上一章中，我们展示了${\sum }_{i=1}^{n}i=n(n+1)/2$.

³：我们说“大 O”，例如，“该排序算法是大 O-n-平方”。

⁴：有关执行常见任务的大多数算法的大 O 复杂度，请参阅 http://code.energy/bigo

⁵：已经证明，针对 任何 NP 完全问题的非指数算法可以推广到 所有 NP 完全问题。由于我们不知道这种算法是否存在，如果您证明 NP 完全问题无法通过非指数算法解决，您也将获得一百万美元！

---

计算机科学精粹：学习解决计算问题的艺术 由 Wladston Viana Ferreira Filho 撰写，现已在 亚马逊 上架。