附录 基准测试
附录 基准测试
本书阐述了多种算法，在其各自章节中，你能够找到这些算法的性能描述。本章中，我们将会描述如何评估算法性能。我们认为，根据经验使用特定的数据来精确解释算法行为是非常重要的。这样能够帮助读者验证结果的正确性，以及理解在使用的过程中，这些假设是否适用。
分析算法的方法有很多种。第2章是一种正式的理论分析方法，介绍了如何分析最坏情况和平均情况下的性能。在某些情况下，我们可以根据经验得到这些理论结果。例如，考虑排序20个数的算法性能。这20个数有2.43×1018种转置，但是我们不可能详尽地计算每一种转置下算法的平均性能。而且，我们不可能对所有转置进行排序，然后计算平均性能。我们必须使用基于统计的方法来正确计算算法的期望性能。
统计基础
在本章中，我们简要地介绍一下评估算法性能的关注点。有兴趣的读者可以参考任意一本统计学教材来获取有关统计学的知识。
为了计算算法的性能，我们构架了一套独立的实验集T。每次实验的输入规模是n。我们也会做一些额外的工作来保证这些实验的等价。这时，我们就可以将算法实现中的变量量化，而不用全部进行所有的实验。这样也许比较合适，例如，计算大量独立的等价实验的开销非常巨大。这个集合执行的结果将会精确到毫秒。当代码使用Java编写时，我们会在执行之前先调用系统的垃圾回收器，虽然不能保证垃圾回收器不会在实验进行当中执行，但是这样做能够减少和算法执行无关的时间花费。而且我们会将最好的和最坏的结果当作异常值抛弃，然后使用下面的公式计算出剩余的T-2次结果的平均值和标准方差。
xi是单独的实验执行时间，而x的T-2次实验的平均值。这里n等于T-2，所以平方根中的坟墓是T-3。计算平均值和标准方差能够帮助我们预测算法的远期性能，表A-1是实际值在[x-k*σ，x+k*σ]区间内的概率，σ是计算出的标准方法。这些概率值组成了算法性能预测的置信区间。
例如，在一个随机实验中，68.27%的时间期望结果都落在[x-σ，x+σ]这个范围内。
得出结果精度不会超过4位数，我们相信精度已经足够，不可能出现重大的误差。当精度超过5位数时，我们会将其截断，或者合理地舍入。例如16.897 986会舍入为16.8980。