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 표기법 사용)
'알고리즘' 카테고리의 다른 글
| 쉽게 배우는 알고리즘-06연습문제 (1) | 2023.10.23 |
|---|---|
| 쉽게 배우는 알고리즘-04연습문제 (0) | 2023.10.23 |
| 쉽게 배우는 알고리즘-02 연습문제 (2) | 2023.10.23 |
| 쉽게 배우는 알고리즘-09동적프로그래밍(~돌놓기) (1) | 2023.10.23 |
| 쉽게 배우는 알고리즘-08집합의 처리 (0) | 2023.10.23 |