比较算法

引言

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

重要标准：时间和空间

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

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

执行时间的比较

在本课程的剩余部分，我们将重点关注第一个因素，即执行时间。我们该如何比较两个算法的执行时间？

实验评估

首先，我们可以实现这两个算法，并在计算机上运行它们，同时测量执行时间。执行时间较短的算法胜出。为了有效比较，这种测试必须公平进行。让我们来审视一下这个方法存在的问题：

• 一个算法在更大规模的输入上可能运行得更久。因此，被比较的算法必须在相同输入规模下测试。但这还不够。由于存在条件语句，即使输入规模相同，同一个算法的实际运行时间也可能因具体输入的不同而变化。这意味着被比较的算法必须在完全相同的输入上测试。然而，对于某个特定输入，一个算法可能处于不利地位。因此，我们必须对所有可能的输入值进行穷尽测试——这显然是不可能的。

• 被比较的算法必须先被实现。但如果程序员对其中一个算法的实现方式更好呢？如果编译器对其中一个算法的优化程度更高呢？在这一阶段，有太多因素可能破坏比较的公平性。

• 两个算法的程序必须在完全相同的软硬件环境下运行。尽管听起来有些极端，但我们或许可以为所有研究人员分配一台专用机器来测试算法。即便如此，现代操作系统中的任务调度也包含大量随机性。如果“最优”算法恰好遭遇了过多硬件中断，结果就会受到影响。因此，无法保证完全一致的软硬件环境，也就无法确保公平比较。

分析评估

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

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

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

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

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

最好情况分析

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

最坏情况分析

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

平均情况分析

在平均情况分析中，我们试图确定所有可能输入中，该算法执行的基本操作的平均数量。这对初学者来说并不容易。要计算算法的平均情况运行时间，我们必须知道所有可能输入在给定规模下的相对出现频率。然后，对每个输入执行的基本操作数进行加权平均。但如何准确预测输入的分布？如果算法在实际应用中遇到不同的输入分布，我们的分析就毫无意义。

结论

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

通过上述方式计算出的算法运行时间也被称为其时间复杂度。另一个常听到的概念是算法的空间复杂度。算法的空间复杂度是指算法所需的额外或辅助内存空间，即除了原始输入本身之外的内存空间。稍后在本课程中，你将看到分析算法空间复杂度的具体例子。

分析一段简单的 Java 程序

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

1class Main {
2    public static void main(String args[]) {
3        int x = 0;
4        x += 1;
5        System.out.println(x);
6    }
7}

接下来，我们分析 main() 函数。第 5 行有一个变量赋值，这是 1 个基本操作。第 6 行涉及变量值的访问、加法运算以及赋值操作，共 3 个基本操作。第 7 行涉及变量值的访问和输出显示，共 2 个基本操作。因此，整个程序共有 6 个基本操作。该分析也可总结如下表：

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

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

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