《算法技术手册》函数的增长率

一个广为接受的描述算法的方法是使用执行时间的增长率作为问题样本规模的函数。但是这种方法是抽象地描述一个算法的性能，忽略了细节问题。所以，在使用的时候需要对抽象背后的细节有一个清醒的认识。

程序都必须运行在某个平台上，在这里，平台的广义包括：

·程序运行的计算机，包含了CPU、数据缓存、浮点运算单元以及其他芯片。

·使用的语言、编译器/解释器以及生成代码的优化设置。

·操作系统。

·后台运行的其他进程。

一个基本的假设是：上述组成平台的任何条件的改变，都会改变程序的执行时间，但只是在原有的时间上乘以一个常数因子。在这里，我们简要地讨论一下顺序搜索算法，这个算法会在第5章讲到。顺序搜索算法会顺序搜索列表中的所有n个元素，直到找到想要的值v。现在，我们假设：

·列表中有n个不同的元素。

·将要寻找的元素v在这个列表里面。

编码对性能的影响

假设一个程序需要处理元素周期表，有三个频繁的操作，它们是：a)“第N个元素的原子量是多少？”；b)“x元素的原子数是多少？”；c)“第N个元素的名字是什么?”。一个有趣的挑战是：2008年1月的时候，第117个元素还仍未发现，但是第118个元素已经被发现，叫做Ununoctium。

周期表的第一种编码：两个数组，elementName，存储元素的名字，还有elementWeight，存储元素原子量。

周期表的第二种编码：用一个长度为2626个字符的字符串来表示整个周期表。最开头的62个字符是：

1 H Hydrogen 1.00794

2 He Helium 4.002602

3 Li Lithium 6.941

为了理解编码对于性能的影响，我们做了32次实验，每次实验包含100 000个随机请求（包括无效的）。我们舍弃了最好的和最坏的，留下了30次实验的结果，下面这张表表示了余下30次实验执行时间的平均值（和标准差），用毫秒表示：

就像预期的那样，编码2的性能比编码1的性能差很多，因为采用编码2的时候，每一次请求都要执行一次字符串操作。编码1能够有效地处理原子量查询和元素名称查询，但是元素序号查询需要对整个表进行查找，因为表是元素序号无序的。

这个例子告诉我们，不同的编码会在执行时间上可能产生巨大的差异。同样也告诉设计人员必须根据将要进行的操作选择合理的编码来优化性能。

·列表中每个元素可能为v的概率都是相等的。

通过计算顺序搜索算法平均搜索多少个元素，我们能大致了解这个算法的性能情况。因为我们知道v肯定在这个列表里面，而且每个元素可能为v的概率都是相等的，用数学语言描述就是，对于一个包含有n个元素的列表，平均搜索的元素个数E（n）就是所有次数总共搜索元素个数的和除以搜索次数。

因此，上述假设作为前提的条件下，顺序搜索算法搜索了这个表中的大约一半元素。如果列表的元素个数加倍，那么顺序搜索会大约搜索原来两倍的元素；期望的搜索数目是n的线性函数。也就是说，期望搜索数目可以用c*n来表示，c为常数。这里的c为1/2。关于性能分析的一个基本的观点是，在长时间的运行中，常数c是不重要的，因为最重要的影响性能的因子是问题样本的规模n，随着n越来越大，那么错误率就如：

变得不再重要，实际上，它们的比值接近1说明了：

虽然对于比较小的n来说，预计错误会是致命的。但是在上下文中，我们所谓的顺序搜索算法期望搜索数目的增长率是线性的。所以，在大样本规模情况下，我们可以忽略作为乘数的常数，而主要关注样本的规模。

依据增长率这个抽象的概念选择算法时，我们需要注意以下问题。

常数的问题

这就是为什么我们需要使用超级计算机和定期升级我们的计算机。

n并不总是非常大

在第4章我们将会看到，快速排序执行时间的增长率比插入排序执行时间的增长率要低。但是在小数据集上，插入排序表现得比快速排序要好。

算法的增长率决定了算法在逐渐增长的大数据集上的性能表现。我们在一个更复杂的例子上使用这个基本的原理。

给定一个排序任务，对四个排序算法进行评价。这个任务是对n个随机字符串进行排序。n的取值从1～512，对于每个n的值，我们都将进行50次实验，并且舍弃掉最好和最坏的实验结果，图2-2的图描述了剩下48次实验的平均运行时间（毫秒）。这些结果的差异实在令人惊异。

我们设计一个函数来解释这个结果，这个函数能够预测每个算法在规模为n的数据样本上的性能。我们不太可能精确地知道这个函数的具体形式，我们只能使用商业软件对结果使用统计方法进行回归分析，描绘出一条趋势线。趋势线与实际数据的拟合度设为R2，取值为0～1。R2越趋近于1，表示拟合度越高。例如，R2=0.9948表示，由于数据的随机变化，只有0.52%的几率造成趋势线和数据不拟合。

第四种排序法很明显地是四种算法中最差的，在电子数据表上描绘512个数据点，与数据相符合的趋势线是：

y=0.0053*n2-0.3601*n+39.212

R2=0.9948

我们看到，R2的值如此地接近1，这是一个非常精确的预测。第二种排序法在给定的数据集上提供了最快的性能。它的行为可以用如下的趋势线来描述：

y=0.05765*n*log(n)+7.9653

第二种排序法比第三种排序法的速度快，但最快也可能只比第三种排序法快10%。第一种排序法表现出了两种不同的性能特征。在数据集少于39个字符串的时候，性能表现为：

y=0.0016*n2+0.2939*n+3.1838

R2=0.9761

但是，数据集在40个或者更多时，性能表现为：

y=0.0798*n*log(n)+142.7818

这些表达式中的系数完全取决于这些算法运行的平台。就像之前描述过的那样，这些相同的差异（例如平台）并不重要。n的长期变化趋势支配着这些算法的行为。事实上，图2-2描绘了同一个算法在不同规模的数据集下的表现。直到数据集的规模n变得足够大的时候，算法之间的差异才变得明显。

算法设计人员试图去理解算法之间的性能差异。这些算法的源代码是来自开源的代码库，正因为这些算法的源代码的开源，所以算法设计人员能够从代码入手，分析他们的选择如何影响总的运行时间。第一种排序法反映了在Linux 2.6.9内核下快速排序的性能。当审阅源代码时（源代码可以在任何Linux的代码库中找到）[1]，一个人发现这样的注释：“这个快速排序例程是由Bentley和McIlroy设计的”。Bentley和McIlroy（1993）描述了如何对快速排序进行优化，他们通过在不同的样本规模下采用不同的策略，例如规模小于7的，规模在8～39的以及40或者更大的规模下采取的策略。实验结果表明，这个隐藏的优化手段是非常有效的。