1.12는 후에 시간이 있을 때 하기로 했고,

1.13은 귀납법으로 하면 쉽게 문제가 풀리기에 생략하였습닙다.

이 문제는 tree를 그려보고 order of growth를 구하는 문제입니다.

tree를 직접 그릴려고 하였지만 귀찮아서 간단히 그리고 확인만 하였습니다.

대신 인터넷에서 확인하였습니다.

여기서 문제는 order of growth를 구하는 것이었습니다.

기억 공간(space)는 Θ(n)이 나왔습니다.

왜냐하면 해당 tree의 가장 깊은 길이는 n을 모두 1cent로 하였을 때입니다.

이거이 n에 비례하기에 Θ(n)입니다.

하지만 거치는 단계 수(time)은 잘 모르겠습니다.

저는 이렇게 생각했습니다.

'1 cent의 가지는 2n이다.

그리고 나머지 5cent, 10cent, 25cent, 50cent에 곱해져 차감이 되면

나머지 것들도 2(n-k)로 될 것이다.

(k : 남은 동전 종류로 구해진 값)

이런 나머지 것들이 n에 비례하기에 이들의 합 역시 n에 비례할 것이다.

따라서 Θ(n)이 아닐까??'

인터넷을 보니 저와 비슷한 생각을 한 사람도 있습니다.

(해당 글)

하지만 다른 곳에서는 Θ(n^5)라고 얘기하고 있습니다.

1. Exercise 1.14

2. 'sicp???解 (1.14)'

2번의 중국 문서의 경우 그 이유를 설명한 듯싶으나 중국말이라 도저히 모르겠습니다.

(영어로 번역했지만 잘 모르겠네요.;;;)

그래서 실험을 해보았습니다.

Lisp는 제가 잘 모르는터라 C로 옮겨 적었습니다.

그리고 n을 100부터 1000까지 100씩 증가시켜서 결과를 보았습니다.

밑의 내용은 해당 네티즌이 적은 글을 제가 읽고 이해한 글입니다.

(관련글 : 'sicp???解 (1.14)')

space는 제치고 time에 대해 적겠습니다.

해당 코드는 밑에 덧글에 달았습니다.

'http://nosyu.pe.kr/1242#9390682'

n은 amount. 즉, 구해야 할 돈입니다.

m은 first-denomination으로 구해진 값입니다.

kinds-of-coins 즉, 동전 종류의 값입니다.

여기서는 m_1은 1 cent, m_2는 5 cent를 나타내겠지요.

먼저 위의 그림에서 (11, 1)을 보시면

n을 m_1 즉, 1(cent)로 나눈 후 그 총 개수가 3배를 해야하기 때문입니다.

다음으로 (11, 2)를 보시면 (11, 1)과 (6, 2)를 계산해야합니다.

그리고 (6, 2)는 (6, 1)과 (1, 2)를, (1, 2)는 (1, 1)과 (-4, 2)를 계산해야합니다.

따라서 (11, 2)는 (11, 1), (6, 1), (1, 1)의 계산회수를 더하면 됩니다.

(뒤에 있는 (-4, 2)는 상수이므로 제외하겠습니다.)

위에서 kinds-of-coins가 1일때를 구했으므로 계산하면 다음과 같습니다.

T(11, 2) = T(11, 1) + T(6, 1) + T(1, 1)

이를 n으로 확장시키면 다음과 같습니다.

따라서 T(n, 2) = Θ(n²)입니다.

T(n, 3)의 경우도 마찬가지로 하면 Θ(n³)이 되고,

따라서 T(n, 5)이면 Θ(n^5)가 되는 것입니다.

이 문제를 푸는 방법은 역시 Tree를 제대로 그려 그 패턴을 확인하는 것이었습니다.

제가 그린 Tree는 위의 것과 달랐기에 이 패턴을 찾지 못했습니다.

그리고 패턴을 찾는 실력이 제가 너무 낮다는 것도 알 수 있었습니다.OTL...

참조

Structure and Interpretation of Computer Programs 2/E - Page 56

다른 블로거의 블로그(본문에 링크하였습니다.)

MIT iCampus Chapter 4 Slid 4.2.4 설명

http://babelfish.altavista.com/babelfish/tr

http://www.chinaitpower.com/A200507/2005-07-27/174664.html

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.