4알고리즘 분석
프로그램 실행 결과를 한 번 유심히 살펴봅시다.
• 1층짜리 하노이의 탑: 원반을 한 번 이동
• 2층짜리 하노이의 탑: 원반을 세 번 이동
• 3층짜리 하노이의 탑: 원반을 일곱 번 이동
입력 크기, 즉 탑의 층수가 높을수록 원반을 더 많이 움직여야 한다는 것을 알 수 있습니다. 호기심이 있는 독자라면 4층과 5층으로 n 값을 바꿔서 프로그램을 실행해 보았을 것입니다(4층이면 열다섯 번, 5층이면 서른한 번 이동하라는 출력이 나옵니다).
그렇다면 n층짜리 하노이의 탑을 옮기려면 원반을 몇 번 움직여야 할까요?
n층짜리 하노이의 탑을 옮기려면 원반을 모두 2n-1번 옮겨야 합니다. 마찬가지로 n이 커지면 -1은 큰 의미가 없으므로 O(2n)으로 표현할 수 있습니다. 이는 2를 n번 제곱한 값이므로 n이 커짐에 따라 값이 기하급수적으로 증가합니다.
얼마나 커지는지 궁금하다고요? 놀라지 마세요.
원반 하나를 옮기는 데 1초가 걸린다고 가정하고 잠시도 쉬지 않고 원반을 옮길 때, 20층짜리 하노이의 탑을 옮기려면 열이틀이 넘게 걸립니다. 30층짜리 하노이 탑을 옮기려면 무려 34년간 먹지도 쉬지도 않고 원반만 옮겨야 합니다.
잠깐만요
지금까지 살펴본 계산 복잡도
• O(1): n과 무관하게 일정한 시간이 걸림
• O(n): n과 비례하여 계산 시간이 증가함
• O(n2): n의 제곱에 비례하여 계산 시간이 증가함
• O(2n): 2의 n 제곱에 비례하여 계산 시간이 증가함
위에서 아래로 갈수록 계산 복잡도가 증가합니다. 참고로 12장 끝에 있는 ‘잠깐만요’에서는 각 계산 복잡도를 한눈에 비교할 수 있도록 그래프로 정리해서 다시 설명합니다.