이 문제는 연습문제 2.68에서 설계한

인코딩 프로시저의 자람 차수(order of growth)를 구하는 문제입니다.

하지만 어떤 tree가 들어오느냐에 따라

자람 차수가 너무 달라지기에 답을 구하기 어려웠습니다.

책에서도 이 문제의 일반해(general solution)을 구하기 어렵다고 적혀있습니다.

그럼 연습문제 2.71와 같은 tree의 경우를 따져보았습니다.

가장 많이 쓰는 글자는 무조건 1bit이기에 Θ(1)입니다.

그리고 가장 적게 쓰는 글자는 (n-1)bit이기에 Θ(n)입니다.

일반해를 제치니 너무 쉬워지네요.;;;

지금까지 tree를 많이 살펴보았습니다.

하지만 전 자료구조를 배우지 않았기에

'과연 여기서 배우는 tree가 도움이 될까?' 고민입니다.

특히 우리학교 커리큘럼의 경우 C 언오로 쓴 자료구조론이 교재이더군요.

그런데 여기서 쓰는 tree는 Scheme로 만들고 있으니...

이론은 같으니 큰 도움은 아니더라도 익숙하겠지요.^^;;

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 220

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

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