[알고리즘] 분할 정복을 이용한 거듭제곱

분할 정복

 

[알고리즘 소개]

거듭제곱을 빠른 속도로 구하는 알고리즘

 

 

[코딩 방법 / 재귀]

1. $n^r$을  $n^{\frac{r}{2}}$ 두 개로 분할 후 서로 곱함
2. r이 홀수였다면 추가로 n을 곱하고 return
3. r == 0인 경우 1을 return

[코딩 방법 / 반복문]

1. base = 1, temp = n으로 시작
2. r > 0까지 반복
3. r이 홀수라면 base에 temp를 곱함
4. temp는 모든 반복마다 제곱
5. r은 모든 반복마다 2로 나눔

[시간 복잡도]

$O(logn)$

 

 

[공부용 링크]

mygumi.tistory.com/319