下载掌阅APP，畅读海量书库
立即打开
在本书中，我们讨论的数学技术不仅适用于解决与算法性能相关的问题，还适用于构建从基因组学到统计物理学等各种科学应用的数学模型。因此，我们经常考虑广泛适用的结构和技术。然而，我们的主要目的是研究所需要的数学工具，以便能够在实际应用中对重要算法的资源使用做出准确的说明。
我们专注于分析算法的 平均情况 （average-case）：我们设计一个合理的输入模型，分析一个程序的预期运行时间，程序的输入从这个模型中提取。该方法之所以有效，是因为以下两个主要原因。
平均情况分析在现代应用中重要而有效的第一个原因是，随机性的简单模型通常是非常准确的。以下是排序应用的几个代表性示例。
● 排序是 密码分析 （cryptanalysis）的一个基本过程，密文已经在很大程度上使数据与随机数据不可区分。
● 商业数据处理 （commercial data processing）系统通常需要排序巨大的文件，其中密钥往往是账号或其他标识号，这些号码利用适当范围内的均匀随机数进行良好建模。
● 计算机网络 （computer networks）的实现依赖于再次涉及被随机数模型化的密钥的种类。
● 排序广泛应用于 计算生物学 （computational biology），其中与随机性的显著偏差由科学家进一步研究，以试图了解基本的生物和物理过程。
如这些示例所示，简单的随机模型很有效，不仅能用于分类应用，也可在实践中广泛用于各种基础算法。一般来说，当人们创建大型数据集时，这些数据集通常是基于随机模型任意构建的。随机模型在处理科学数据方面经常也是有效的。爱因斯坦曾反复劝告我们——在这种情况下“上帝不玩色子”，意思是：随机模型是有效的，因为如果发现与随机性相比有明显偏差，我们就已经学到了一些有关自然界的重要东西。
平均情况分析在现代应用中重要而有效的第二个原因是，我们经常可以将随机性赋予一个问题实例，使其对于算法（和分析者）来说，看起来是随机的。这是设计具有可预测性算法的有效方法，也称其为 随机算法 （randomized algorithms）。M.O. Rabin [25] 是该算法的最初提出者之一，此后，许多其他研究人员发展了该算法。Motwani和Raghavan的著作 [23] 深入介绍了这一内容。
因此，我们首先分析随机模型，这通常从计算平均值开始——随机抽取 N 个实例，计算其有价值的量的平均值。现在，t（尽管密切相关）的方法来计算某个量的平均值。在本书中，我们将明确讲解以下两种计算平均值的不同方法。
令
是大小为
N
的可能的输入数据的数量，令
是使算法开销为
k
且大小为
N
的输入数据的数量，所以
。此时，开销为
k
的概率是
，开销的数学期望是
算法的分析依赖于“计数”。大小为 N 的输入数据有多少个？使算法开销为 k 且大小为 N 的输入数据有多少个？这些是计算开销为 k 的概率的步骤，所以这种方法可能是初等概率论中最直接的方法。
令
是算法对所有大小为
N
的输入的总（或累积的）开销。（即
，只是通常不必用这种方法计算
。）此时平均开销是
。算法的分析取决于不太具体的计数问题：在所有输入的基础上，算法的总开销是多少？我们将使用一般工具，让这种方法变得非常有吸引力。
分配方法提供了完整的信息，可以直接用于计算标准差和概率论中其他的矩。正如我们将要看到的那样，在使用累积法时，间接方法（常常更简单）也能用来计算这些矩。在本书中，尽管我们更倾向于采用累积法，而且这也最终促使我们用基本数据结构的组合属性来研究算法分析，但我们还是对两种方法都做了研究。
许多算法是通过递归地求解较小的子问题来解决问题的，因此这些算法服从平均开销或总开销必须满足的递归关系的推导。正如下一节的示例所示，从算法直接推导出递归关系常常是一种自然的处理方式。
无论平均情况的结果是如何得到的，我们都更关注这个结果，因为在随机输入是合理模型的大多数情况下，准确的分析可以帮助我们：
● 针对同一任务比较不同算法；
● 预测具体应用所需的时间和空间；
● 比较将要运行同一算法的不同计算机；
● 调整算法参数以优化性能。
把平均情况的结果与经验数据进行比较，以检验算法的实现、模型和分析。在特定应用中，不论将其置于何种环境下，用平均情况的结果都可以预测算法如何表现，最终正是为了对此获得足够的信心。如果希望评估新机器架构对重要算法性能的影响，也许我们可以在新的架构出现之前通过分析来实现。这种方法的成功在过去几十年中得到了验证：50年前我们第一次分析了本节涉及的排序算法，其分析结果仍然有助于评估这些算法在如今的计算机上的表现。