1.增长的阶
是用来描述不同的计算过程在消耗计算资源的速率上的差异
- 令n是一个参数，作为问题规模的一个度量
- 令R(n)是一个计算过程在处理规模n的问题时所需要的资源量
我们称R(n)具有θ(f(n))的增长阶，记为：
R(n) = θ(f(n))
如果存在与n无关的整数k1和k2，使得：k1f(n) <= R(n) <= k2f(n)
对于足够大的n，值
R(n)总位于k1f(n)和k2f(n)之间
增长的阶为我们提供了对计算过程行为的一种很粗略的描述，也为预期一个计算过程的行为变化提供了有用的线索
2.求幂
从对一个给定的数计算乘幂的问题入手，这一过程的参数为基数b和一个正整数的指数n，过程计算出b^n，定义如下：
b^n = b * b^(n-1)
b^0 = 1
可以直接转为一个线性的递归计算过程：
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
上面过程需要θ(n)步和θ(n)空间，还可以转为一个等价的线性迭代：
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter sum)
(if (= counter 0)
sum
(expt-iter b
(- counter 1)
(* b sum))))
这一版本需要θ(n)步和θ(1)空间
此外，我们还可以借助于连续求平方去完成一般的乘幂计算：
b^n = (b^(n/2))^2 # n为偶数
b^n = b * b^(n-1) # n为奇数
将上面规则定义为过程：
(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))
这一过程的增长的阶是对数增长的
3.最大公约数（GCD）
两个整数a和b的最大公约数定义为：能除尽这两个数的那个最大的整数
找到两个整数的GCD除了因式分解，还有下面的著名算法：
基本思想：如果r是a除以b的余数，那么a和b的公约数正好是b和r的公约数
即GCD(a, b) = GCD(b, r)
从任意两个正整数开始反复执行这种归约，最终将产生出一个数对，其中第二个数是0，第一个数则为GCD，这一计算方法称为欧几里得算法，写成过程如下：
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
这将产生一个迭代计算过程，其步数依所涉及的数的对数增长
lame定理：如果欧几里得算法需要用k步计算出一对整数的GCD，那么这对数中较小的那个数必然大于或者等于第k个斐波那契数
根据lame定理，可以做出欧几里得算法的增长阶估计：
- n为较小数
- k为计算过程所需步数
- 得出
n >= Fib(k)≈φ^k / √￣5
这样，步数k的增长就是n的对数(底为φ)，算法增长阶为θ(log n)
