SICP 연습문제 1.14 ~ 1.15

Exercise 1.14

a. tree illustration

1년 반 여 전에 열심히 공부할 때 그려두었던 파일을 그대로 가져온다. 내가 무슨 정신으로 이걸 그리고 있었던걸까. 마우스질을 무척 열심히 했겠지.

b. the orders of growth 

먼저 space. recursion의 최대 depth가 space이므로, 여기서는 n+5이다. 따라서 O(n), linear

한편 steps는? 꽤 헷갈렸기 때문에 step수를 세는 tree recursive process를 만들어보았다. step은 조건확인, 사칙연산으로 한정시켰다. 이 때, or에서는 applicative order가 아니라 #t가 나오자마자 바로 프로시져가 끝난 다는 것을 (define (p) (p))와 (or #t (p))를 이용해 확인했다.

(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)))
(define (steps-recur amount kinds-of-coins)
  (cond ((= amount 0) 1)
	((< amount 0) 2)
	((= kinds-of-coins 0) 3)
	;;((< kinds-of-coins 3) (steps-approx amount kinds-of-coins))
	(else (+ (steps-recur amount (- kinds-of-coins 1)) (steps-recur (- amount (first-denomination kinds-of-coins)) kinds-of-coins) 7))))
(define (steps-approx amount kinds-of-coins)
  (cond ((= amount 0) 1)
	((< amount 0) 2)
	((= kinds-of-coins 0) 3)
	((= kinds-of-coins 1) (+ 1 (* 10 amount)))
	((= kinds-of-coins 2) (+ (* amount amount) (/ (* 33 amount) 5.0) 10))))

steps-recur는 tree recursion으로 스텝수를 센 것이고, steps-approx는 이를 바탕으로 동전 종류가 2가지일때까지를 다항식으로 나타낸 것이다. 이 패턴을 살펴보면 결국 동전종류가 1개일 때, amount에 대한 1차식이고, k+1종류의 동전으로 바꿀 때는 k종류의 동전으로 바꿀때의 다항식이 amount에 비례하는 양 만큼 더해지(고 나머지 찌꺼기가 좀 더 더해지)므로 m종류의 동전으로 바꿀 때 step 수는 amount의 m차식이되는 것이다.(수학적 귀납법)

big O notation에서는 다항식에선 최고차항만 관심이 있으므로 count-change는 O(amount^kinds-of-coins)의 order of growth를 갖는다고 할 수 있다.

steps-recur에 주석처리된 줄은 계산속도를 빠르게 하기 위해 steps-approx를 사용할 수 있게  한 것이다. 해제하면 계산의 정확도는 아주 약간 떨어지지만, 속도는 훨씬 빨라진다.

Exercise 1.15

a. 5번이다. p를 call할때마다 parameter에 3을나누고 이 값이 0.1보다 작아질때까지 반복되기 때문이다.

b. space: O(log(a)) p가 불리는 횟수가 곧 depth이기 때문이다.
steps: O(log(a)) p는 constant order이고, 총 step수는 p의 order에 p가 불리는 횟수가 곱해진꼴일 것이기 때문이다. 곱해진 상수는 무시하므로 log(a)에 비례한다.

Exercise 1.16

(define (fast-expt b n)
  (define (iter cnt base state)
    (cond ((< cnt 2) (* base state))
	  ((even? cnt) (iter (/ cnt 2) (* base base) state))
	  (else (iter (- cnt 1) base (* state base)))))
  (iter n b 1))