比较算法

简介

解决同一个计算问题通常存在多种不同的算法。因此，自然需要对这些不同方案进行比较。但我们如何判断算法 A 是否优于算法 B 呢？

重要标准：时间和空间

衡量一个算法“优劣”的一个重要因素是它解决问题所需的时间。如果算法 A 比算法 B 花费更少的时间来解决相同的问题，那么算法 A 就被认为是更好的。

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

比较执行时间

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

实验评估

我们可以尝试将两个算法实现后，在计算机上运行，并测量它们的执行时间，执行时间更短的算法胜出。但这种比较必须公平进行。让我们分析一下这种方法可能存在的问题：

• 算法在处理更大规模输入时可能需要更长时间。因此，被比较的算法必须在相同的输入规模下测试。但这还不够。由于条件语句的存在，即使输入规模相同，同一算法的运行时间也可能因具体输入内容而异。这意味着算法必须在完全相同的输入数据上进行测试。然而，某个特定输入可能对其中一个算法不利，因此我们必须在所有可能的输入上进行全面测试，而这在现实中是不可能实现的。
• 在比较前必须先实现这两个算法。如果程序员对其中一个算法实现了更高效的代码，或者编译器对某个算法进行了更多优化，都会影响结果。这些因素都可能导致评估失去公平性。
• 两个算法的程序必须在完全相同的硬件和软件环境下运行。即便我们设想让所有研究人员都使用同一台机器进行测试，现代操作系统的任务调度本身就包含大量随机性。如果“更优”算法对应的程序恰好遭遇大量硬件中断，其表现就会受影响。因此，无法保证每次测试环境完全一致，也就难以确保公平比较。

理论分析（解析评估）

上述问题表明，通过实验方式公平地评估算法几乎是不可能的。因此，我们必须转而采用理论上的分析方法。从前文讨论中我们得出两个关键点：必须在相同输入规模下比较算法，并考虑该规模下所有可能的输入。具体做法如下：

我们假设存在一台理想化的计算机，其上每条基本操作的执行时间都是固定的常量。给定一个输入规模（例如 n），我们统计算法在某一输入下执行的基本操作数量。基本操作总数较少的算法被认为更优。

那么，什么是基本操作？基本操作是指那些通常由处理器指令直接实现的简单操作，包括：变量或数组元素的赋值、读取变量或数组元素的值、两个值之间的比较、算术运算、函数调用等。

哪些操作不被视为基本操作？以函数调用为例，当函数被调用时，函数内部的所有语句都会被执行，因此不能把一次函数调用视为单一的基本操作。同理，输出整个数组也不是一个基本操作。

条件语句的执行次数取决于具体的输入值——有时某段代码会执行，有时不会。那么我们该如何计算这类语句的操作数？可以采用三种策略之一：最佳情况分析、平均情况分析和最坏情况分析。

最佳情况分析

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

最坏情况分析

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

平均情况分析

在平均情况分析中，我们试图计算所有可能输入下基本操作数的平均值。这并不像听起来那么简单。要计算算法的平均运行时间，我们必须知道所有可能输入的出现频率，然后根据每种输入对应的操作数计算加权平均值。但在实际应用中，我们很难准确预测输入的分布情况。一旦实际输入分布与假设不符，我们的分析就失去了意义。

结论

最佳情况分析的实际价值有限，因为在部署算法后，最佳输入可能极少出现。我们认为最坏情况分析更有用，因为它的结果能提供一个性能保障：无论输入如何，算法 A 的运行时间都不会超过这个上限。除非特别说明，本课程中的分析都将基于最坏情况下的运行时间。

以上述方式计算出的算法运行时间也被称为时间复杂度。你还会经常听到另一个术语：空间复杂度。算法的空间复杂度指的是该算法所需的额外或辅助存储空间，即不包括输入数据本身所占用的内存空间。本课程后续将举例说明如何分析算法的空间复杂度。

分析一个简单的 Java 程序

假设我们不是面对一个抽象的算法，而是拿到一段 Java 代码。下面我们来看如何分析这段程序背后的算法。我们来统计以下程序中包含的基本操作数量：

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

我们分析 main() 函数。第 5 行有一个变量赋值操作，计为 1 个基本操作；第 6 行涉及变量访问、加法运算和赋值操作，共 3 个基本操作；第 7 行涉及变量访问和输出显示，共 2 个基本操作。因此，整个程序共包含 6 个基本操作。下表总结了这一分析过程：

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

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

注意，这个简单示例中没有输入规模的概念，因为程序本身没有接受任何输入。对于那些时间复杂度与输入规模无关的算法，我们称之为常数时间算法。