Math.pow() 와 **

---

거듭제곱을 구하기 위해 일반적으로 Math.pow() 함수를 사용하거나 거듭제곱 연산자(**) 를 사용한다. 하지만 이 경우 시간 복잡도가 O(n)이기 때문에 거듭제곱을 할 횟수가 늘어날 수록 엄청난 연산수가 필요하게 되고 메모리 활용이 비 효율적이게 된다.

고속 거듭제곱 구하기

---

빠르게 거듭제곱을 할 수 있는 방법으로 분할제곱 방법이 있다. 분할제곱에서 승수가 홀수일 때와 짝수인 경우로 구분해서 빠륵 거듭제곱을 처리할 수 있다.

그 예로 2^8 을 구한다고 하면 8번의 연산이 반복되어야 한다. 하지만 분할제곱의 경우 3번만에 답을 구할 수 있다.

분할제곱 혹은 거듭제곱을 이용할 경우 시간복잡도는 O(LogN)으로 획기적으로 빨라진다. 분할 제곱의 핵심적인 아이디어는 분할 정복법으로 답을 얻어야 하는 결과를 분할하면서 접급해간다.

M 의 N 거듭제곱을 구한다고 했을 때 지수를 반으로 쪼개 가면서 재귀 함수를 호출한다.

• N이 짝수인 경우 : M^(N/2) * M^ (N/2)
• N이 홀수인 경우 : M^(N-1/2) M^ (N-1/2) M