科学的研究方法

  • 细致地观察真实世界的特点，精确的测量
  • 根据观察结果提出假设模型
  • 根据模型预测未来的事件
  • 继续观察并核实预测的准确性
  • 如此反复，直到确认预测和观察一致

观察

计时与分析

我们需要测量程序运行的时间。首先，确定输入数据的规模(例如1M个整数)；然后，在程序中或外部记录程序开始时间和结束时间，两者相减即可获得程序运行时间。增加输入的规模，得到新的运行时间。以输入规模为横轴，运行时间为纵轴，即可得到两者关系的粗略图像，从而推断算法的增长数量级。

数学模型

原则上我们可以构造一个数学模型，来描述任意程序的运行时间。一个程序运行的总时间和两点有关：

  1. 执行每条语句的耗时
  2. 执行每条语句的频率

前者取决于计算机、编译器、操作系统等，后者取决于程序本身和输入。

近似运行时间

一般来说，我们只需要关注运行频率最高的那些语句，比如内循环里的那些。例如书中ThreeSum算法里，if语句的执行次数为:

N(N-1)(N-2)/6 = N^3/6 - N^2 / 2 + N/3

一般我们只保留多项式的首项(最高阶的一项)，因为它们的增长速度要远远快于其他项。我们用~来忽略较小的项:

~N^3/6

用a来表示常数系数，即:

~aN^3

定义：~f(N)表示所有当n趋近于无穷时，~f(N)/f(N)趋近于1的函数。g(N)~f(N)表示g(N)/f(N)随着N的增大而趋近于1。

设T(N)为ThreeSum处理N个整数的运行时间，根据前文的数学模型有T(N)~aN^3。

成本模型

3-sum的成本模型：在研究解决3-sum问题的算法时，我们记录的是数组的访问次数(访问数组元素的次数，无论读写)。

在这个成本模型下，3-sum的暴力算法使用了~N^3/2次数组访问来计算N个整数中和为0的整数三元组的数量。(if执行了~N^3/6次，每次3次数组访问)

总结

对大多数程序，得到其运行时间的数学模型所需的步骤为:

  1. 确定输入模型，定义问题的规模
  2. 识别内循环
  3. 根据内循环中的操作，确定成本模型
  4. 对于给定的输入，判断这些操作的执行频率

例子：

二分查找

输入模型是大小为N的数组a[]，内循环是一个while循环中的所有语句，成本模型是比较操作(比较两个数组元素的值)。

白名单

输入模型是白名单的大小N和由标准输入得到的M个整数，且我们假设M远大于N，内循环是一个while循环中的所有语句，成本模型是比较操作(承自二分查找)。

二分查找所需的比较次数最多为lgN+1。根据以下因素，白名单问题计算所需时间的增长数量级最多为MlgN:

  • 如果N很小，输入、输出可能会成为主要成本
  • 比较的次数取决于输入：在~M和~MlgN之间，取决于标准输入中有多少个整数在白名单内，以及二分查找要多久才能找出它们(一般为~MlgN)
  • Arrays.sort()使用归并排序，其时间增长数量级为NlogN。由于M远大于N，因此Arrays.sort()的成本可以忽略。

增长数量级的分类

常见的增长数量级为：

  • 常数级别 O(1)
  • 对数级别 O(logN)
  • 线性级别 O(N)
  • 线性对数级别 O(NlogN)
  • 平方级别 O(N^2)
  • 立方级别 O(N^3)
  • 指数级别 O(2^N)

倍率实验

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

  • 开发一个输入生成器来产生实际情况下的各种可能的输入(比如随机数)
  • 计算每次实验和上一次的运行时间的比值
  • 反复运行直到该比值趋近于极限2^b

此方法对比值没有极限的算法无效，但它仍然适用于许多程序，我们可以得出以下结论:

  • 它们的运行时间的增长数量级为N^b。
  • 要预测一个程序的运行时间，将上次观察得到的运行时间乘以2^b并将N加倍，如此反复。
倍率定理: 如果T(N)~a(N^b)lgN，那么T(2N)/T(N)~2^b。

在有性能压力的情况下，应该对算法进行倍率实验。我们可以用以下方式对程序的运行时间的增长数量级作出假设，并预测它的性能:

  • 评估它解决大型问题的可行性：得出算法的时间增长数量级后，我们可以预测输入翻倍后所需的运行时间。
  • 评估使用更快计算机产生的价值：一般来说，若新计算机比老的快x倍，那么运行时间也将变为原来的x分之一。若程序本来需要运行几天，更换计算机也许只能将其缩短到一天。请根据实际情况考虑这是否值得。

注意事项

大常数

在首项近似中，一般会忽略低级项中的常数系数，但这可能是错的。若常数很大，是有可能对性能造成影响的。我们要对可能的大常数保持敏感。

非决定性的内循环

内循环是决定性因素的假设不一定是正确的。错误的成本模型可能无法得到真正的内循环，问题的规模N也许大到一定程度。有些程序在内循环之外也有大量指令要考虑。换句话说，成本模型可能还需要改进。

指令时间

每条指令执行所需的时间总是相同的假设并不总是正确的。例如，由于缓存技术，访问大数组的若干并不相邻的元素所需的时间可能会被相邻元素要长。

系统因素

计算机中其他程序也可能抢占资源。原则上来说，此时系统中运行的其他程序应该是可以忽略的或可以控制的。

不分伯仲

在比较两个程序时，常常出现其中一个在某些场景中更快而在另一些场景中更慢。

对输入的强烈依赖

在研究程序运行时间的增长数量级时，我们首先作出的几个假设之一就是运行时间应该与输入无关。当假设不满足的时候，我们可能无法得到一致的结果。

多个问题参量

有可能出现多个影响结果的参量。例如，白名单算法有两个参量：输入规模M、白名单大小N。