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

하노이 타워

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

#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배 이상 차이가 나는 것을 확인할 수 있습니다.