01 具体例子
为了阐述方法，我们先引入一个具体的编程问题：ThreeSum，它是在给定的含有 n 个元素的数组中找出三元组之和等于0的个数。这个问题最简单的一个解法：枚举，代码如下：
02
我们在这里主要关心的是输入数据大小与运行时长的关系。我们循着如下的思路分析两者间的关系：
加倍假设(Doubling hypothesis) 对于大量的程序而言，我们能很快地形成如下假设：假如输入数据的个数加倍，运行时间怎么变化。
经验分析(Empirical analysis)一种简单的实现加倍假设的方法是使输入数据的个数加倍，然后观察对运行时长的影响。如下所示为一个简单的通过加倍输入个数，测试运行时长的程序：DoublingTest.Java.
再回到ThreeSum.java程序中，我们生成一系列随机数，填充到输入数组中，每一个时步都加倍输入元素个数，然后观察到每一次程序所运行的时间都会大致增加8倍，这个就可以让我们下结论说输入数据加倍后运行时间增加了8倍。如下图中左侧视图所示，当输入大小为4K时，运行时长为64T，当输入带下为8K时，运行时长变为原来的8倍：512T.
Log–logplot. 绘制log图也是衡量运行时间的一种方法，因为是log级别的，所以与上面说的经验公式没有本质区别，如下图右所示，取完对数后，输入数据大小与运行时间的对数变为线性关系。
| 留言与评论（共有 0 条评论） |
