算法(4th ed)(170):基础——算法分析 6.6

阅读数:23 2019 年 11 月 9 日 15:02

算法(4th ed)(170):基础——算法分析 6.6

(倍率实验)

下面这种方法可以简单有效地预测任意程序的性能并判断它们的运行时间大致的增长数量级。

  • 开发一个输入生成器来产生实际情况下的各种可能的输入(例如 DoublingTest 中的 timeTrial() 方法能够生成随机整数)。
  • 运行下方的 DoublingRatio 程序,它是 DoublingTest 的修改版本,能够计算每次实验和上一次的运行时间的比值。
  • 反复运行直到该比值趋近于极限 2b

这个实验对于比值没有极限的算法无效,但它仍然适用于许多程序,我们可以得出以下结论。

  • 它们的运行时间的增长数量级约为 Nb
  • 要预测一个程序的运行时间,将上次观察得到的运行时间乘以 2b 并将 N 加倍,如此反复。如果你希望预测的输入规模不是 N 乘以 2 的幂,可以相应地调整这个比例(请见练习 1.4.9)。

如下所示,ThreeSum 的比例约为 8,因此我们可以预测程序对于 N=16 000、32 000 和 64 000 的运行时间将分别为 408.8、3270.4 和 26 163.2 秒,也就是处理 8000 个整数所需的时间(51.1 秒)连续乘以 8 即可。

算法(4th ed)(170):基础——算法分析 6.6

该测试基本类似于 1.4.2.3 节所描述的过程(运行实验,绘出对数图像得到运行时间为 aNb 的猜想,从直线的斜率得到 b 的值,然后算出 a),但它更容易使用。事实上,可以手工通过 DoublingRatio 准确地预测程序的性能。在比例趋近于极限时,只需要不断乘以该比例即可得到更大规模的问题的运行时间。这里,增长数量级的近似模型是一个幂次法则,指数为该比例的以 2 为底的对数。

为什么这个比例会趋向于一个常数?简单的数学计算显示我们讨论过的所有常见的增长数量级函数(指数级别除外)均会出现这种情况:

命题 C。(倍率定理)如果 T(N)aNblgN,那么 T(2N)/T(N)2b
证明
T(2N)/T(N)=a(2N)blg(2N)/aNblgN&=2b(1+lg2/lgN)&2b

一般来说,数学模型中的对数项是不能忽略的,但在倍率假设中它在预测性能的公式中的作用并不那么重要。

在有性能压力的情况下应该考虑对编写过的所有程序进行倍率实验——这是一种估计运行时间的增长数量级的简单方法,或许它能够发现一些性能问题,比如你的程序并没有想象的那样高效。一般来说,我们可以用以下方式对程序的运行时间的增长数量级作出假设并预测它的性能。

评论

发布