하노이 타워 알고리즘의 시간복잡도
하노이 타워에서 원판 이동의 최소 횟수 및 그 순서를 찾아내는 코드는 아래와 같이 간단히 작성된다. (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 ..
