1.3　算法分析概述

虽然在1.2节中我们对排序和Mergesort的分析证实了排序问题的固有性难点，但仍然尚未涉及与排序（和Mergesort）相关的许多重要问题。在特定计算机上运行Mergesort算法的实现方法，预计可能需要多长时间？如何将其运行时间与其他运行时间为O(NLogN)的算法（这样的算法有很多）相比较？某些排序算法在平均情况下运行速度很快，但在最劣情况下可能没那么快，如何将其与这样的算法做比较？如何将其与不基于元素间比较的排序算法做对比？要回答这样的问题，则需要更细致的分析。本节我们简要描述进行这样分析的过程。

为了分析算法，首先我们必须明确最具价值的重要资源，以便能够正确而集中地进行细致分析。我们从研究运行时间的角度来描述分析过程，因为运行时间在此处是与之最相关的资源。一个算法所需运行时间的完整分析包括以下步骤。

● 完整地实现算法。

● 确定每个基本操作所需的时间。

● 识别能够用于描述基本操作执行频率的未知量。

● 为程序的输入建立一个实际模型。

● 假设输入模型已经建立，分析其中的未知量。

● 将每个操作的频率乘以操作的时间，然后把所有的乘积相加，计算出总的运行时间。

分析的第一步是为了在特定计算机上严谨地实现算法。如果我们用术语程序（program）一词来描述这样的实现，那么可以说一种算法与多个程序相对应。一个特定的实现不仅能提供具体的研究对象，还能提供有用的经验数据以帮助或检验分析。算法的实现应该设计得能够有效利用资源，而在设计的过程中不应该过早过分地强调效率。事实上，分析主要是为更好地提供知识方面的指导。

下一步是估计构成程序的每个指令所需要的时间。在实际操作中，我们可以非常精确地完成这个过程，但这个过程很大程度上取决于所用机器的系统特性。另一种方法是对少量的输入直接运行程序来“估计”常量的值，或者像习题1.7描述的那样，总体上间接地进行。本书中我们没有详细研究这个过程，而是集中关注分析中“与机器无关”的部分。

事实上，为了确定程序的总体运行时间，必须研究程序的分支结构，以便用未知数学量表示程序构成指令的执行频率。如果这些量的值是已知的，那么我们可以直接将每个程序构成指令的所需时间乘以频率，然后把这些乘积相加，进而得到整个程序的运行时间。许多编程环境有简化这项工作的工具。在分析的第一阶段，我们关注具有大频率值或对应开销较高的量；原则上来讲，分析能通过精简得到足够详尽的答案。当环境允许时，我们经常把算法的“开销”作为“所讨论的量的值”的简称。

下一步是为程序的输入建模，也是为指令频率的数学分析打下基础。未知频率值取决于算法的输入：输入的大小（我们通常称之为N）往往是表示结果的重要参数，但输入数据的顺序或输入数据值通常也影响运行时间。这里的“模型”是指对算法典型输入的准确描述。例如，对排序算法来说，比较方便的做法通常是假设输入数据随机排序且互异，尽管当输入数据非互异时程序也能正常运行。排序算法的另一种可能是假设输入取自范围相对较大的随机数。我们能够证明这两种模型几乎是等价的。大多数情况下，我们使用最简单的“随机”输入模型，因为这种模型通常更切合实际。几种不同模型也可以用于同一算法：一种模型的选用可能使分析变得尽可能简单，而另一种模型可能会更好地反映即将运行的程序的实际情况。

最后一步是假设输入模型已经建立，要分析其中的未知量。对于平均情况分析，我们逐个分析这些量，然后用指令次数乘以相应的平均值，并把乘积相加，进而得到整个程序的运行时间。对于最坏情况分析，得到整个程序的准确结果往往是很困难的，所以我们只能通过将指令次数乘以每个量的最坏情况值，然后把结果相加得到上界。

在许多情况下，这种场景可以成功地提供准确的模型。Knuth的著作——参考资料[17]、[18]、[19]、[20]正是基于这一概念。不幸的是，如此精细的分析所涉及的细节常常令人望而生畏。因此，我们通常寻找能够使用的近似（approximate）模型来估计开销。

使用近似模型的第一个原因是：在现代计算机具有复杂体系结构和操作系统的条件下，确定所有独立操作的开销细节几乎是无法实现的。因此，我们通常在程序的“内部循环”中只研究很少的一些量，推测仅通过分析这些量就能准确地估计成本。有经验的程序员通过定期“验证”相关实现来确定“瓶颈”，这是确定此类量的系统方法。例如，我们往往仅通过记录比较次数来分析基于比较的排序算法，这种方法存在机器无关（machine independent）的严重副作用。通过仔细分析比较算法使用的比较次数，我们能够预测许多不同计算机的性能。相关假设很容易通过实验验证，从原则上来讲，我们可以在适当的情况下完善它们。例如，我们可以改进基于比较的排序模型，使之包含数据移动，而这可能又需要考虑缓存的影响。

习题1.11　在两台不同的计算机上运行实验来验证这样一个假设，即随着问题大小的增加，Mergesort的运行时间除以它使用的比较次数，其结果趋近于一个常数。

近似对数学模型同样有效。使用近似模型的第二个原因是：避免我们推导的用于描述算法性能的数学公式中存在不必要的复杂性。以此为目的研究经典近似方法是本书的重要内容，我们将提供很多例子。除此之外，现代研究对算法分析的一个主要推动来自研究基础数学分析的方法。准确地说，这些方法可以用于准确地预测性能和比较算法，而且从原则上来讲，我们还可以对其进行改进以达到手头应用所需要的精度。这些技术主要涉及复杂的分析，参考资料[10]中充分介绍了相关内容。