하노이 타워 알고리즘의 시간복잡도

하노이 타워에서 원판 이동의 최소 횟수 및 그 순서를 찾아내는 코드는 아래와 같이 간단히 작성된다. (C언어로 작성됨)

void move(int from, int to)
{
    printf("move from %d to %d\n", from, to);
}

void hanoi(int n, int from, int by, int to)
{
    if (n == 1)
        move(from, to);
    else
    {
        hanoi(n - 1, from, to, by);
        move(from, to);
        hanoi(n - 1, by, from, to);
    }
}

위 코드에 따르면, hanoi함수의 시간복잡도 f(n)은 다음과 같이 재귀적으로 풀이된다. (여기서 f(1) = 1 이라 하자)

 

f(n)

= 2f(n - 1) + 1

= 4f(n - 2) + 3

= 8f(n - 3) + 7

= 16f(n - 4) + 15

...

= 2^(n-1)f(n - (n - 1)) + (2^(n-1) - 1)
= 2^n - 1

 

자세한 풀이과정은 https://gunhoflash.tistory.com/72를 참고.