比较算法

注意： 如果你已经学习过我们的课程《C++中的数据结构：面试复习》（Data Structures in C++: An Interview Refresher），可以跳过本章，因为该课程也包含了算法复杂度度量的相关内容。

引言

通常，解决一个计算问题会有多种不同的算法。因此，自然地需要对这些算法进行比较。但如何判断算法 A 比算法 B 更好呢？

重要标准：时间和空间

决定算法“优劣”的一个重要因素是解决问题所需的时间。如果算法 A 解决同一问题所用时间少于算法 B，那么算法 A 被认为更优。

另一个重要的比较因素是解决问题所需的内存空间。所需内存更少的算法被认为更优。

比较执行时间

在接下来的内容中，我们将重点讨论第一个因素——执行时间。我们该如何比较两个算法的执行时间？

实验评估

我们可以将两个算法实现后，在计算机上运行并测量其执行时间。执行时间更短的算法胜出。但有一点至关重要：这种比较必须是公平的。让我们来审视一下这个想法存在的问题：

• 一个算法在更大规模输入下可能运行得更久。因此，被比较的算法必须在相同输入规模下测试。但这还不够。由于存在条件语句，对于相同的输入规模，同一个算法的实际运行时间也可能因输入内容不同而变化。这意味着，被比较的算法必须在完全相同的输入上测试。由于某个特定输入可能使一个算法处于不利地位，我们必须对所有可能的输入值进行穷尽测试，而这显然是不可能的。
• 被比较的算法必须先被实现。但如果程序员对其中一个算法的实现更好呢？如果编译器对其中一个算法优化得更多呢？在这一阶段，有太多因素会影响比较的公平性。
• 两个算法的程序必须在完全相同的软硬件环境下运行。尽管听起来有些极端，但我们或许可以为所有研究人员分配一台机器用于测试。即便如此，现代操作系统中的任务调度包含大量随机性。如果“最优”算法恰好遭遇了过多硬件中断，结果也会受到影响。因此，无法保证完全一致的软硬件环境，也就无法实现公平比较。

分析评估

上述问题揭示了实验评估算法难以做到公平的原因。因此，我们不得不采用分析或理论的方法来进行比较。根据之前的讨论，我们需要关注两点：一是对相同输入规模进行比较，二是考虑该规模下的所有可能输入。具体做法如下：

我们假设存在一台理想计算机，其中一些基本操作可以在常数时间内完成。我们设定一个具体的输入规模，例如 n。然后统计某个算法在给定输入下执行的基本操作次数。执行基本操作较少的算法被认为更优。

那么，什么是基本操作呢？你可以将其理解为通常由处理器指令实现的简单操作。这些操作包括变量或数组索引的赋值、读取变量或数组索引的值、比较两个值、算术运算、函数调用等。

哪些操作不被视为基本操作？以函数调用为例：当调用一个函数时，该函数内的所有语句都会被执行。因此，不能将每次函数调用视为单一的基本操作。同样，完整显示一个数组也不是基本操作。

条件语句的执行次数取决于实际输入值。有时代码块会被执行，有时则不会。那么如何处理条件语句？我们可以采用三种策略之一：最好情况分析、平均情况分析和最坏情况分析。

最好情况分析

在最好情况分析中，我们考虑导致基本操作次数最少的特定输入。这给出了该算法在给定输入规模下的执行时间下界。

最坏情况分析

在最坏情况分析中，我们考虑导致基本操作次数最多的特定输入。这给出了该算法在给定输入规模下的执行时间上界。

平均情况分析

在平均情况分析中，我们试图计算所有可能输入规模为 n 的输入下，基本操作的平均执行次数。这并不像初学者想象的那么简单。为了计算算法的平均运行时间，我们必须知道所有可能输入在该规模下的相对出现频率。然后对每种输入对应的执行次数进行加权平均。但如何准确预测输入的分布？如果算法在实际应用中遇到不同的输入分布，我们的分析就失去了意义。

结论

最好情况分析的价值有限，因为一旦部署算法，最好情况输入可能极少出现。我们认为最坏情况分析更有用，因为它给出的结果是无论何种输入，算法 A 所需时间都不会超过该值。除非特别说明，本课程中的分析都将基于最坏情况运行时间。

通过上述方式计算出的算法运行时间也被称为其时间复杂度。另一个常见的术语是算法的空间复杂度。算法的空间复杂度是指算法所需的额外或辅助内存空间，即除原始输入本身之外的内存空间。我们将在本课程后续部分看到如何评估算法空间复杂度的具体例子。

分析一个简单的 C++ 程序

假设我们面对的不是算法，而是一段 C++ 代码。以下是分析该程序背后算法的方法。我们来统计下面这段程序中的基本操作数量：

1#include <iostream>
2using namespace std;
3
4int main() {
5  int x = 0;
6  x += 1;
7  cout << x;
8  return x;
9}

第 1 和第 2 行是编译指令，可忽略。第 5 行有一个变量赋值，计为 1 个基本操作。第 6 行涉及变量访问、加法运算和赋值，共 3 个基本操作。第 7 行涉及变量访问和输出值，共 2 个基本操作。第 8 行涉及变量访问和返回值，共 2 个基本操作。因此，整个程序共有 8 个基本操作。该分析也可总结如下表：

对于上述程序，其时间复杂度可表示为：

$$\text{时间复杂度 } = 1 + 3 + 2 + 2 \Rightarrow 8$$

注意，这个简单示例中没有输入规模的概念，因为该程序没有输入。那些时间复杂度与输入规模无关的算法被称为常数时间算法。