比较算法

引言

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

重要标准：时间和空间

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

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

执行时间的比较

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

实验评估

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

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

分析评估

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

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

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

当控制权从调用函数转移到被调用函数时，我们称之为 上下文切换。

哪些操作不被视为基本操作？虽然上下文切换是基本操作，但函数调用本身并不总是单一的基本操作。函数调用的成本被认为是函数体中所有基本操作的总和。同样，完整显示一个数组也不是基本操作。

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

最好情况分析

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

最坏情况分析

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

平均情况分析

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

结论

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

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

分析一段简单的 JavaScript 程序

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

1x = 0;
2x += 1;
3console.log(x);

在上述代码中，第 1 行有一个变量赋值，即 1 个基本操作。第 2 行涉及变量值的访问、加法运算和赋值，共 3 个基本操作。第 3 行涉及变量值的访问和输出显示，共 2 个基本操作。因此，整个程序共有 6 个基本操作。该分析也可总结如下表：

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

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

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