SICP学习笔记 1.2.3 增长的阶

    练习1.14

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
		((or (< amount 0) (= kinds-of-coins 0)) 0)
		(else (+ (cc amount (- kinds-of-coins 1))
				 (cc (- amount (first-denomination kinds-of-coins))
					 kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
		((= kinds-of-coins 2) 5)
		((= kinds-of-coins 3) 10)
		((= kinds-of-coins 4) 25)
		((= kinds-of-coins 5) 50)))

 

 

    图为二叉树，其中由根节点到最底层的叶子的路径为
    (cc 11 5)->(cc 11 4)->(cc 11 3)->(cc 11 2)->(cc 11 1)->(cc 10 1)->(cc 9 1)->(cc 8 1)->(cc 7 1)->(cc 6 1)->(cc 5 1)->(cc 4 1)->(cc 3 1)->(cc 2 1)->(cc 1 1)->(cc 0 1)
    则数的深度为n+5,则空间增长阶为O(n)
  

    设f(n, k)为计算amount分为kinds种货币时需要的步骤，则由图中可知
    f(1, 1)=2
    f(2, 1)=4
    f(3, 1)=6
    ......
    则有f(n, 1) = 2*n，则f(n, 1)步骤增长阶为O(n)

    而f(n, 2) = f(n, 1) + f(n-5, 2)f(n-5, 2), f(n-5, 2) = f(n-5, 1) + f(n-5*2, 2) ......
    设m=n/5(整数)，则有
    f(n, 2) = f(n-5*0, 1) + f(n-5*1, 1) + f(n-5*2, 1) + ...... + f(n-5*m, 1)
              = 2*[(n-5*0) + (n-5*1) + (n-5*2) + ...... + (n-5*m)]
              = 2*[n*m - 5*(0 + 1 + 2 + ...... +m)]
              = 2*[n*m - 5*[m*(m+1)/2]]
              = 2*n*m - 5*(m^2+1)
    则有f(n, 2)步骤增长阶为O(n^2)

    同理推得f(n, 5)步骤增长阶为O(n^5)

 

    练习1.15

 

define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

 

    (sine 12.15) --> (p (sine 4.05))
                      --> (p (p (sine 1.35)))
                      --> (p (p (p (sine 0.45))))
                      --> (p (p (p (p (sine 0.15)))))
                      --> (p (p (p (p (p (sine 0.05))))))
            
    a) 12.15=0.05*3^5，p被使用5次
    b) 设a=x*3^n，其中x小于0.1,则有
    a/3^n=x<0.1
    --> 10a/3^n<1
    --> 10a<3^n
    --> lg(10a)<lg(3^n)
    --> lg(10a)/lg3<n
    则其增长的阶为O(lga)