4일차 - 1.2.3 ~ 1.2.4 - 요약

1.2.3 프로세스가 자라나는 정도

• Order of growth, 자람차수 : 입력의 크기에 따라 프로세스가 쓰는 자원양이 자라나는 정도
• Θ(f(n)), theta of f(n) : n 알맞게 큰값, 그에 대해 처리되는 함수 f(n) 이 있을 때 f(n) 의 theta 만큼 단계 또는 기억 공간이 필요하다는 것을 표기
• Θ(1)
• Θ(n), Θ(2n), Θ(100n) 과 같이 단순상수는 큰 영향이 없음 (간추려 말할 수 있다). 즉, 자람 차수는 프로세스가 쓰는 자원 양을 어림잡아 나타내는 것일 뿐이다.
• Θ(n^2) 등등의 형을 띄는 단계로 표현 할 수 있다.
• 로그,logarithmic 자람 차수 Θ(log n) 띄는 알고리즘을 보자.

- 연습문제 1.15

;;EXERCISE 1.15
(define (cube x) (* x x x))

(define (p x) 
  (display "; call p\n")
  (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

• "충분히 작은 각"을 만족하는 상황을 식으로 풀어보면
• -0.1 <= a(1/3)^n <= 0.1
• 위 식을 정리하면 (log 표기를 정확히 어떻게 해야하는지 모르겠네요;;)
• n = log(3, 10 * a)

1.2.4 거듭제곱

같은 수를 여러번 곱하는 (거듭제곱) 문제의 재귀 규칙을 간단히 보면,

• b^n = b * ( b ^ (n - 1) )
• b^0 = 1

이 규칙에 따른 프로시저는 아래와 같이 계산단계, 기억공간 모두 Θ(n)

;; Linear recursion
;; Θ(n), Θ(n)
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

이를 되도는 프로세스로 표현하면 각각 Θ(n), Θ(1) 만큼 사용한다.

;; Linear iteration
;; Θ(n), Θ(1)
(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product)))) 

하지만 단계를 절반씩 잘라나가는 아래 규칙을 참조하면 log n 단계로 줄일 수 있을 것이다.
(8번 곱해야할 과정을 3번으로 줄였다)

• b^2 = b * b
• b^4 = (b^2 * b^2)
• b^8 = (b^4 * b^4)

규칙을 다듬어서 지수 n 이 짝수, 홀수일 경우로 나누어 생각하면 아래의 프로시저를 생각할 수 있다.

;; Logarithmic iteration
(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))

- 연습문제 1.16

;; EXERCISE 1.16
(define (proc-expt b n)
  (define (iter b n a)
    (cond ((= n 0) a)
          ((even? n) (iter (square b) (/ n 2) a))
          (else (iter b (- n 1) (* a b)))))
  (iter b n 1)
)

- 연습문제 1.17

;; EXERCISE 1.17
(define (custom-mult a b)
  (if (= b 0)
      0
      (+ a (custom-mult a (- b 1)))))

(define (double x)
  (* x 2))
(define (halve x)
  (/ x 2))

(define (fast-mult a b)
  (cond ((or (= a 0) (= b 0)) 0)
        ((= b 1) a)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

; (fast-mult 3 5)
; (+ 3 (fast-mult 3 4))
; (+ 3 (double (fast-mult 3 2)))
; (+ 3 (double (double (fast-mult 3 1))))
; (+ 3 (double (double 3)))
; (+ 3 (double 6))
; (+ 3 12)

- 연습문제 1.18

;; EXERCISE 1.18
(define (proc-mult b n)
  (define (iter b n a)
    (cond ((= n 0) a)
          ((even? n) (iter (double b) (halve n) a))
          (else (iter b (- n 1) (+ a b)))))
  (iter b n 0)
)