[카테고리:] <span>자료구조와 알고리즘</span>

하노이 타워 알고리즘 성능을 분석합시다.

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)이라고 말할 수 있습니다.