时间

讲解如何用统计步数衡量程序效率，介绍增长阶 Θ 记号与对数级快速幂运算。

衡量时间效率

为了衡量程序运行得有多快，我们必须设计出一种合理的衡量方式。用秒表来测量耗时是行不通的：每次后台运行着不同的程序、存在随机波动、太阳耀斑等等，计时结果都会变化。而且新计算机通常更快，旧的计时数据也就不再适用。

更好的办法是统计一个过程执行了多少步。把注意力集中在过程上，我们就能摆脱对特定计算机的依赖。

统计步数

下面这些过程我们视为占用「一步」：

以下过程都只占一步：

基本算术运算
定义变量
定义过程
条件表达式（conditional）？
用户定义的过程调用

示例：统计步数

(define (square x) (* x x)) ; 占一步
(square 4) ; 占 2 步（一次过程调用，一次乘法）
(square (+ 2 3)) ; 3 步

然而，最有趣的问题出现在我们比较两个过程、询问哪个更快的时候。为了做出这种比较，我们必须对每个过程问出下面的问题：

随着实参规模的增大，这个过程运行需要多少步？

换句话说，如果我们把过程所需步数画成图（以输入为横轴），那张图的形状是什么样的？

示例：函数运行时间

对于 square，我们说这是一个常数时间过程——(square 2) 和 (square 2000) 所需步数相同。因此，随着输入规模增大，步数保持不变。
对于 last（找出句子中最后一个词的过程），我们说这是一个线性时间过程——随着我们用越来越大的输入调用 last，步数线性增长。

为了把这一点形式化，我们必须学习一个称为增长阶（Orders of Growth）的数学概念。

增长阶

增长阶描述函数之间的关系。给定两个函数 $f(n)$ 和 $g(n)$ ，当我们说 $f = \Theta(g)$ 时，意思是：存在两个数 $a$ 和 $b$ ，使得对于足够大的 $n$ ，有 $ag(n) \le f(n) \le bg(n)$ 。

示例

当 $f(n) = n$ 、 $g(n) = 329n$ 时， $f = \Theta(g)$ 。
当 $f(n) = 4n^2$ 、 $g(n) = 2n^2+n$ 时， $f = \Theta(g)$ 。
当 $f(n) = .0004n^3$ 、 $g(n) = 1000n^2+30000n$ 时， $f$ 不等于 $\Theta(g)$ 。

基于这些例子，我们有以下规则：

我们可以忽略常数因子。
我们可以忽略低阶项，例如在 $2n^2+n$ 中，我们只关心 $n^2$ 。

回到过程上来，我们可以正式地说：square 是 $\Theta(1)$ ，last 是 $\Theta(n)$ 。

示例：幂运算

考虑计算 $b^n$ （b 的 n 次幂）最直接的方法：把 b 自身乘 n 次。代码如下：

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

它相对于变量 n 是线性时间运行。我们知道这一点基于两个观察：

如果 n 是 2，我们做 2 次递归调用；如果 n 是 10，我们就做 10 次递归调用。
每次递归调用中，所做的工作都是 $\Theta(1)$ 。

我们能做得更好吗？事实证明，有一种更聪明的幂运算算法，它利用了连续平方（successive squaring）的思想：

假设我们要计算 $b^8$ 。通常，我们会做 $b \times b \times b \times b \times b \times b \times b \times b$ ，这需要 8 次乘法。相反，我们可以只用 3 次完成：这种方法对于指数是 2 的幂时很有效。如果使用下面的规则，我们也可以在一般指数运算中利用连续平方：

上述技巧给了我们这个过程：

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (even? n)
  (= (remainder n 2) 0))

对偶数情况取平方，让我们得以减少递归调用的次数。事实上，仔细想想：每隔一次递归调用，我们就把 n 减半。这种把问题规模减半的模式，意味着递归调用的次数相对于 n 是对数级的。因此 fast-expt $= \Theta(\log(n))$ 。（如果这个解释看不懂，请查看延伸阅读中的 1.2.4。）

练习

下面是一些关于求函数运行时间的短练习，不计成绩。

bar 的运行时间是多少？

define (bar n)
  (if (zero? (remainder n 7))
      'Bzzst
      (bar (- n 1)) ))

sort 的运行时间是多少？

(define (sort s)
  (if (empty? s)
      '()
      (insert (sort (bf s)) (first s)) ))

(define (insert sorted-sofar n)
  (if (empty? sorted-sofar)
      (se n)
      (if (< n (first sorted-sofar))
          (se n sorted-sofar)
          (se (first sorted-sofar) (insert (bf sorted-sofar) n)) )))