下载掌阅APP，畅读海量书库
立即打开
依据不同的参考标准，“为什么要做算法分析”这个问题有几种答案。参考标准主要有：算法的潜在应用、算法在理论与实践方面与其他算法关联的重要性、分析的难度以及所需结果的精度和准确度。
进行算法分析最直接的原因是发现算法的特点，以便评估其对各种应用的适用性；或者与同一应用的其他算法做比较。通常，我们感兴趣的是时间和空间资源，尤其是时间。简单来说，我们想知道在特定的计算机上，某一算法运行完毕究竟需要多长时间和多大空间。我们尽量使分析的结果独立于特定的运行条件——尽可能得到能够反映算法基本特点的结果，因为这样的结果可用于精确估计各种物理机器的真实资源需求量。
在实际操作中，保证算法与运行条件之间的独立性可能非常困难。因为执行的质量、编译器的性质、机器的结构以及运行环境等对算法的性能有着显著影响。为了确保分析结果是有价值的，我们必须了解这些影响因素。从另一方面来讲，在某些情况下，进行算法分析有利于该算法充分利用编程环境。
除去时间和空间资源，有时一些其他的特性也具有价值，那么分析的重点也会相应改变。例如，通过研究移动设备上的算法，可以确定其对电池寿命的影响；或者通过对数值问题算法的研究来确定所提供答案的准确度。此外，在分析中着眼于多种资源有时是正确的做法。例如，一个占用了大量内存的算法可能比占用少量内存的算法的运行时间少得多。事实上，如此仔细地进行算法分析的主要目的是：在这种情况下，为做出恰当的决策提供准确信息。
算法分析 这个术语用来描述两种截然不同的通用方法，其将对计算机程序性能的研究建立在科学的基础上。下面，我们分别考虑这两种方法。
首先来看第一种方法，其推广者有Aho、Hopcroft和Ullman [2] ，还有Cormen、Leiserson、Rivest和Stein [6] 。该方法能够确定某一算法最劣情况下性能的增长量（“上限”）。用这种方法进行分析的主要目的是确定哪种算法的性能最佳，因为对于相同的问题，匹配下限能够证明任何算法的最坏情况的性能。我们将这种类型的分析称为 算法理论 （theory of algorithms）。这是 计算复杂度 的一种特殊情况，是问题、算法、语言和机器之间关系的一般性研究。算法理论的出现开启了设计时代，并由此针对众多关键问题开发了许多能够不断改善最坏情况性能界限的新算法。然而，为了实现这种算法的实际效用，还需要进行更加详细的分析，也许会用到本书中描述的工具。
接下来我们讨论算法分析的第二种方法，该方法的推广者是Knuth [17][18][19][20][22] 。该方法能够精确表征算法在最优情况、最坏情况和平均情况下的性能，此方法中运用了一种在必要时结果的准确度能够不断提升的算法。用这种方法进行分析的主要目的是：当某一算法运行在特定计算机上时，能够精确地预测该算法的性能特点，以便预测资源利用率、参数设置和比较算法。这种类型的分析方法叫作 科学 （scientific）：通过构建数学模型来描述现实中算法实现的性能，然后利用这些模型进一步延伸已通过实验验证的假设。
我们可以将这两种方法视为算法设计和分析的必要步骤。当面对一个解决新问题的新算法时，我们会对这样的粗略想法感兴趣：新算法的预期表现可能如何，针对同一问题，与其他算法相比可能如何，甚至新算法有无可能是最好的。算法理论可以实现这一点。然而，在这样的分析中通常达不到足够精准。因为算法分析提供的帮助预测具体实现性能或者将两个算法进行正确比较的特定信息很少。正如我们所见，为了能够达到这样的效果，需要关于实现过程的细节、要使用的计算机以及由算法控制的结构的数学属性。算法理论可能被视为发展中更为精细、更为准确的分析过程的第一步；我们更倾向于使用 算法分析 这个术语来指代整个过程，其目的是提供尽可能准确的答案。
算法分析能够帮助我们更深入地理解算法，还能提供明智的改进思路。算法越复杂，分析就越困难。但是，经过算法分析，算法往往变得更简单、更精致。更重要的是，正确分析所要求的细致检查，通常使得算法能在特定计算机上更好、更有效地“实现”。分析要求对算法理解得更全面，这种理解比只是得到能够正常运行的实现方法更加深刻而全面。实际上，当分析结果和实验研究结论一致时，就能确信算法的有效性及分析过程的正确性。
有些算法是值得分析的，因为这些分析能够充实现有的数学工具。这些算法虽然可能只有有限的实际价值，但由于可能与存在实际价值的算法具有相似的属性，理解这样的算法就可能有助于以后理解更重要的算法。其他算法（有些具有很高的实际价值，有些只有很少或者没有实际价值）具备复杂的性能结构，这些结构具有独立的数学意义。动态元素通过算法分析引发的组合性问题带来了既具挑战性又有趣味的数学问题，这些数学问题扩展了经典组合学的范围，有助于揭示计算机程序的特性。
为了更清楚地表达这些思想，接下来我们首先从算法理论的角度出发，然后依循本书展开的科学观点，仔细分析一些经典结果。作为一个证明不同观点的示例，我们研究 排序算法 （sorting algorithms），它按照数字顺序、字母顺序或其他顺序重新排列列表。排序是一个重要的实际问题，这个问题现在仍然被广泛研究，因为它在许多应用中起到核心作用。