SICP

Orders of Growth

For instance, with the linear recursive process for computing factorial described in section 1.2.1 the number of steps grows proportionally to the input n. Thus, the steps required for this process grows as Θ(n). We also saw that the space required grows as Θ(n). For the iterative factorial, the number of steps is still Θ(n) but the space is Θ(1)—that is, constant.
if we count process steps as machine operations we are making the assumption that the number of machine operations needed to perform, say, a multiplication is independent of the size of the numbers to be multiplied, which is false if the numbers are sufficiently large. Similar remarks hold for the estimates of space. Like the design and description of a process, the analysis of a process can be carried out at various levels of abstraction.
线性递归，时间成长是 Θ(n)，空间成长也是 Θ(n)
线性迭代，时间成长是 Θ(n)，空间成长则是 Θ(1)
无论是空间还是时间的估计，分析的都是在一个抽象层面的，不是具体到具体的基本数，就比如预估乘法这个操作，是不考虑被乘数过大的情况，而是抽象为，乘法操作。

Exponentiation

求幂
求幂是一种典型的 Θ(n) 优化为 Θ(logn) 的场景
线性递归版本
requires Θ(n) steps and Θ(n) space

  1. function expt(b, n) {     
  2.   return n === 0            
  3.     ? 1            
  4.     : b * expt(b, n - 1); 
  5. }

线性迭代版本
This version requires Θ(n) steps and Θ(1) space.

  1. function expt(b, n) {
  2.     return expt_iter(b, n, 1);
  3. }
  4. function expt_iter(b, counter, product) {
  5.     return counter === 0
  6.            ? product
  7.            : expt_iter(b, counter - 1, b * product);
  8. }

image.png
所以可以优化为：

  1. function is_even(n) {
  2.     return n % 2 === 0;
  3. }
  5. function fast_expt(b, n) {
  6.     return n === 0
  7.            ? 1
  8.            : is_even(n)
  9.            ? square(fast_expt(b, n / 2))
  10.            : b * fast_expt(b, n - 1);
  11. }