SICP 연습문제 1.15 친절한 풀이

문제

라디안으로 나타낸 각 x가 있을때 $\sin{x}$의 값을 구한다고 하자. x가 충분히 작으면 $x\approx\sin{x}$이고 그렇지 않으면 아래와 같은 식으로 값을 얻을 수 있다. $\sin{x}=3\sin{\frac{x}{3}}-4\sin^3\frac{x}{3}$ (여기서 충분히 작은 각이란, 0.1rad보다 크지 않은 각을 말한다.) 이 생각을 프로시저로 표현하면 다음과 같다.

(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)))))

a. (sine 12.15)의 값을 구할 때, p프로시저를 몇번이나 불러 쓰는가?
b. (sine a)의 값을 계산한다 치고, sine프로시저가 만들어 내는 프로시저에서 기억공간과 계산단계의 자람차수를 a의 함수로 나타내면?

문제로 부터 얻은 것

프로시저의 자라나는 모습을 보고 복잡도를 계산하는 능력을 상승시킬 수 있습니다.

문제풀이

a. (sine 12.15)의 값을 구할 때, p프로시저를 몇번이나 불러 쓰는가?

프로시저의 진행을 나열해 보겠습니다.

(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))))))

총 5번 p프로시저를 호출하는 것을 볼 수 있습니다.

b. 기억공간과 계산단계의 자람차수를 a의 함수로 나타내면?

이 문제에서는 위의 예시처럼, 프로시저가 sine 프로세스를 실행할때마다 기억공간이 동일한 비율로 늘어나므로,
기억공간의 자람차수_{공간복잡도}와 계산단계의 자람차수_{시간복잡도}가 동일하다고 볼 수 있습니다.
이 프로시저의 시간복잡도는 크게 생각을 하지 않아도 $Θ(\log$₃$a)$라는 것을 눈치챌 수 있습니다.
a의 크기가 3배 증가할때마다 호출하는 sine프로시저의 수가 1개씩 추가되기 때문입니다.
예를들어, (sine 36.45)를 계산하는 것은 (sine 12.15)를 계산하는 것보다 단 1개의 과정이 더 필요할 뿐입니다.
프로시저의 자라나는 모습을 보고 복잡도를 계산하는 능력이 조금 상승한 느낌입니다.

읽어주셔서 감사합니다.