简介

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

重要标准：时间和空间

衡量一个算法“优劣”的一个重要因素是它解决问题所需的时间。如果算法 A 比算法 B 更快地解决了相同的问题，则认为算法 A 更优。

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

比较执行时间

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

实验性评估

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

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

理论分析评估

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

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

那么，什么是基本操作？可以理解为通常由处理器指令直接实现的简单操作，包括：

• 对变量或数组元素进行赋值；
• 读取变量或数组元素的值；
• 比较两个数值；
• 执行算术运算；
• 函数调用引起的上下文切换。

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

哪些操作不属于基本操作？虽然上下文切换被视为基本操作，但函数调用整体并不总是单一的基本操作。函数调用的代价应视为其函数体内所有基本操作的总和。同理，输出整个数组的操作也不是基本操作。

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

最佳情况分析

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

最坏情况分析

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

平均情况分析

在平均情况分析中，我们试图计算所有可能输入下基本操作数量的平均值。这并不像听起来那么简单。为了计算算法的平均运行时间，我们必须知道所有可能输入的相对出现频率，并据此计算加权平均值。但我们如何准确预测实际输入的分布？如果算法在实际应用中遇到的输入分布与假设不同，那么我们的分析就失去了意义。

结论

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

以上方式计算出的算法运行时间也被称为其时间复杂度。你还会经常听到另一个术语：算法的空间复杂度。空间复杂度指的是算法执行过程中所需的额外或辅助存储空间，不包括输入数据本身所占的空间。我们将在后续看到评估算法空间复杂度的具体示例。

分析一个简单的 Python 程序

假设我们不是面对一个抽象算法，而是给出了一段 Python 代码。我们可以通过以下方式分析该程序背后的算法。请看下面这段程序中包含多少个基本操作：

1x = 0
2x += 1
3print(x)

第 1 行是一个变量赋值操作，计为 1 个基本操作；
第 2 行涉及变量访问、加法运算和赋值操作，共 3 个基本操作；
第 3 行涉及变量访问和输出显示，共 2 个基本操作。

综上所述，该程序总共包含 6 个基本操作。下表总结了这一分析过程：

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

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

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