쉽게 배우는 알고리즘-03연습문제

2)

T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1)+1

여기서, T(n-1)은 n-1개의 원반을 옮기는데 필요한 이동 횟수입니다. 1은 n번째 원반을 옮기는 횟수입니다.

따라서, T(n)은 T(n-1)의 두 배에 1을 더한 값과 같습니다.

 

3)

점화식 T(n) = 2^n - 1을 풀면 T(n)은 얼마인지 구할 수 있습니다.

여기서, ^는 거듭제곱을 나타냅니다.

따라서, T(n)은 2^n - 1입니다. (0 표기법 사용)