거듭제곱을 시간복잡도 o(log n)으로 구하기

• 두 수를 입력받아 거듭제곱을 리턴
• 시간복잡도 O(logN)
• 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴 (long 타입의 표현 범위를 넘어 설수 있으므로)

o(log n)은  업다운 게임과 비슷하다.

- 값을 계속 반으로 나누어 답을 찾는다.

 

아래와 같이 구할 수 있다.

n^10 = n^5 * n^5

n^5 = n^2 * n^2 * n

n^2 = n*n

n = n * 1

 

public long power(int base, int exponent) {

	// 탈출조건(더이상 나눌수 없는 경우)
	if(exponent == 0) return 1; 

	// 절반 나누기 n^10 = n^5 * n^5
	long result = power(base, exponent / 2);

	// 홀수라면 n^2 * n^2 * n
	if(exponent % 2 == 1){ 
		return (result * result * base) % 94906249; 
        // 나누는 값이 더크다면 값을 그대로 리턴한다
	}else{
	// 짝수라면 n^2 * n^2 
	return (result * result) % 94906249;
	}
    
}