하노이 타워 알고리즘 성능을 분석해 보기로 해요. 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)이라고 말할 수 있습니다.
다음은 속도를 측정하기 위해 수정한 코드입니다.
#include <iostream>
#include <string>
#include <time.h>
using namespace std;
void Hanoi(string src, string use, string dest, int n)
{
if(n<=0) //돌이 없을 때
{
return;
}
Hanoi(src,dest,use,n-1); //n-1 개의 돌을 src에서 dest를 이용하여 use로 이동
cout<<"move "<<src<<" -> "<<dest<<endl; //scr에서 dest로 이동
Hanoi(use,src,dest,n-1); //n-1개의 돌을 use에서 src를 이용하여 dest로 이둉
}
int main()
{
clock_t st,et;
//알고리즘을 수행 전 시간을 측정하세요.
st = clock();
Hanoi("a","b","c",5);
//알고리즘을 수행 후 시간을 측정한 후에 수행 전과의 차이를 계산하세요.
et = clock();
cout<<"5 개일 때 걸린 시간:"<<et-st<<endl;
//똑같은 방법으로 수행 시간을 측정하세요.
//이번에는 8개의 돌을 옮기게 할게요.
st = clock();
Hanoi("a","b","c",8);
et = clock();
cout<<"8 개일 때 걸린 시간:"<<et-st<<endl;
return 0;
}
▷ 실행 결과
move a -> c ...중략... move a -> c 5 개일 때 걸린 시간:44 move a -> b ...중략... move b -> c 8 개일 때 걸린 시간:364
결과를 보면 돌의 개수가 3개 늘었을 때 걸린 시간은 8배 이상 차이가 나는 것을 확인할 수 있습니다.