거듭제곱
X^n을 계산하는 알고리즘을 순환 방식과 반복 방식으로 작성할 수 있다.
먼저 결론을 말하면, 거듭 제곱은 앞선 팩토리얼과 달리 순환적인 방법이 더 효율적인 예제이다.
! 팩토리얼의 경우 순환, 반복 두 경우의 시간복잡도가 같았지만, 공간복잡도가 순환방식에서 더 컸기 때문에 반복 구현이 더 효율적임을 이전 포스팅에서 알아보았다.
https://he-kate1130.tistory.com/26
[자료구조] 2. 순환 - 팩토리얼
팩토리얼 중등 교육과정을 겪어본 사람이라면 모두가 아는 팩토리얼!! 오늘은 팩토리얼을 계산하는 함수를 순환을 통해 구현해보자. 순환 알고리즘 앞선 포스팅에서도 말했지만, 순환 알고리즘
he-kate1130.tistory.com
구현
반복
순환
성능
시간복잡도를 통해 성능을 비교하면 다음과 같다
| 반복 | 순환 |
| O(n) | O(log n) |
따라서 거듭제곱을 계산하기 위해서는 순환 방식이 유리하다
'Data structures > Chapter 2. Recursion' 카테고리의 다른 글
| [자료구조] 4. 순환 - 피보나치 수열 (1) | 2023.10.23 |
|---|---|
| [자료구조] 2. 순환 - 팩토리얼 (1) | 2023.10.22 |
| [자료구조] 1. 순환 (0) | 2023.10.22 |
