[자료구조][과제] 하노이의 탑

 

 

 

원판이 3개일 때 총 7번의 시행 횟수가 필요하다.

 

이를 4개, 5개, 6개로 늘려가면 시행 횟수는 각각 15, 31, 63으로 증가한다.

 

이를 점점 늘려보면 7개일 때는 127개, 8개일 때에는 255개로 2ⁿ-1의 순서로 증가하므로

원판의 개수가 n개일 때 원판을 옮기는 횟수는 2ⁿ-1이다.

 

컴퓨터의 시간복잡도로 계산해보면 O(2ⁿ-1), 즉 O(2ⁿ)의 시간복잡도를 가진다.