6.1.1 하노이 타워 성능 분석

하노이 타워 알고리즘 성능을 분석해 보기로 해요. n개 돌을 옮기는 데 걸리는 시간을 T(n)이라고 합시다.

하노이 타워 알고리즘의 수행 시간 T(n)은 T(n-1) 2번과 Move 1번으로 진행합니다.

T(n) = 2*T(n-1) + 1 = 2 *T(n-2) + 2 +1 = 2^2*T(n-3) +4+2+1 = … = 2^n -1

따라서 하노이 타워 알고리즘 수행 시간은 O(2^n)이라고 말할 수 있습니다.

하노이 타워 알고리즘

다음은 속도를 측정하기 위해 수정한 코드입니다.

▷ 실행 결과

결과를 보면 돌의 개수가 3개 늘었을 때 걸린 시간은 8배 이상 차이가 나는 것을 확인할 수 있습니다.