比较算法

引言

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

重要标准：时间和空间

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

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

执行时间的比较

在本课程的后续内容中，我们将重点关注第一个因素——执行时间。我们该如何比较两个算法的执行时间？

实验评估

我们可以实现这两个算法，并在计算机上运行它们，同时测量执行时间。执行时间较短的算法胜出。但有一点是确定的：这种比较必须公平。让我们来审视一下这个想法中存在的问题：

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

分析评估

上述问题揭示了实现算法公平实验评估的困难。因此，我们不得不采用分析或理论的方法来进行比较。根据之前的讨论，我们有两个关键原则：必须在相同输入规模下比较算法，并考虑该规模下的所有可能输入。具体做法如下：

我们假设存在一台理想化的计算机，其中一些基本操作可以在常数时间内完成。我们设定一个具体的输入规模，例如 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$$

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