比较算法

引言

通常，解决一个计算问题会使用多种不同的算法。因此，对这些替代方案进行比较是很自然的。但如何判断算法 A 比算法 B 更好呢？

重要标准：时间和空间

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

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

执行时间的比较

本课程的后续内容将聚焦于第一个因素，即执行时间。如何比较两个算法的执行时间？

实验评估

你可以实现这两个算法，并在计算机上运行它们，同时测量执行时间。执行时间较短的算法胜出。但有一点至关重要：这种比较必须是公平的。让我们深入理解这一点：

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

分析评估

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

假设存在一台理想计算机，其中基本操作均在常数时间内完成。给定一个特定输入规模 $n$，统计某个算法在处理特定输入时执行的基本操作次数。执行基本操作较少的算法被认为更优。

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

一个上下文切换是指控制权从调用函数转移到被调用函数的过程。

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

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

最好情况分析

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

最坏情况分析

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

平均情况分析

在平均情况分析中，应尝试确定所有可能输入中，该算法执行的基本操作的平均数量。这对初学者来说并不容易。为了计算算法的平均情况运行时间，必须知道所有可能输入在特定规模下的相对频率。可以通过加权平均每个输入对应的基本操作数来计算。但如何准确预测输入分布？如果算法在实际应用中遇到不同的输入分布，那么你的分析就失去了意义。

结论

最好情况分析的价值有限：如果部署该算法后，最好情况输入极少出现，那这个分析就没有实际意义。我们认为最坏情况分析更有用，因为它给出的结果意味着算法 A 的运行时间绝不会超过这个值。除非特别说明，本课程中的分析都将基于最坏情况运行时间。

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

分析一段简单的 C# 程序

假设你面对的不是算法，而是一段 C# 代码。以下是分析该程序背后算法的方法：统计以下程序中执行的基本操作数量。

1using System;
2namespace Chapter_1
3{
4    class SimpleClass
5    {
6        static void Main(string[] args)
7        {
8            int x = 0;
9            x += 1;
10            Console.WriteLine(x);
11            return;
12        }
13    }
14}

第 1 行是编译器指令，应忽略。第 8 行有一个变量赋值，计为一次基本操作。第 9 行涉及变量值的访问、加法运算和赋值，共三次基本操作。第 10 行涉及变量值的访问和输出显示，共两次基本操作。第 11 行是函数返回，计为一次基本操作。整个程序共执行了七次基本操作。该分析也可总结如下表：

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

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

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