반응형
[C언어 알고리즘] 3.2.1 하노이 타워 알고리즘 성능 분석
하노이 타워 알고리즘 성능을 분석합시다.
n 개 돌을 옮기는 데 걸리는 수행 시간을 T(n)이라고 합시다.
하노이 타워 알고리즘의 수행 시간 T(n)은 T(n-1) 2번과 Move 1번으로 진행합니다.
T(n) = 2*T(n-1) + 1 = 2 *T(n-2) + 2 +1 = 2^2*T(n-3) +4+2+1 = ... = 2^n -1
따라서 하노이 타워 알고리즘 수행 시간은 O(2^n)이라고 말할 수 있습니다.
![[그림 3.2] 하노이 타워 알고리즘](https://t1.daumcdn.net/cfile/tistory/244AC138583DA9A428)
[그림 3.2] 하노이 타워 알고리즘
반응형
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
| [C언어 알고리즘] 3.3.2 퀵 정렬 알고리즘 구현 (0) | 2016.11.30 |
|---|---|
| [C언어 알고리즘] 3.3.1 퀵 정렬 알고리즘 성능 분석 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.3 퀵 정렬(Quick Sort) 알고리즘 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.2.3 하노이 타워 알고리즘 소스 코드 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.2.2 하노이 타워 알고리즘 구현 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.2 하노이 타워 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.1 탈출 조건 (0) | 2016.11.30 |
| [C언어 알고리즘] 3. 재귀 알고리즘 (0) | 2016.11.30 |
| [C언어 알고리즘] 2.6.3 쉘 정렬 알고리즘 소스 코드 (0) | 2016.11.29 |
| [C언어 알고리즘] 2.6.2 쉘 정렬 알고리즘 구현 (0) | 2016.11.29 |