시간: 2010.12.7 PM 6:30
<복습>
<복습>
범위: 1.2.3 ~ 1.2.4
발표: 유훈종
<진도>
범위: 1.2.5 ~ 1.2.6
발표: 이준
1.2.3 프로세스가 자라나는 정도
- 연습문제 1.16
- 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번으로 줄였다)
(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))
;; 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)
)
