DSPL: M의 N승 구하기

---

Amazon Interview Question: Level(Easy*)

시간 복잡도가 O(LogN)이 되도록 M의 N승을 계산하는 알고리즘을 작성하시오.

---

일반적으로 M의 N승을 계산하기 위해서는 M을 N번 곱해야 한다. 가장 직관적인 코드는 단순 곱셈의 N번 반복이다.

public static int powerWithNormal(int M, int N) {
    int result = 1;
    for(int i=0; i<N; i++)
        result *= M;
    return result;
}

위 알고리즘은 O(LogN) 복잡도를 만족시키지 못한다. 기본적인 아이디어는 다음과 같다.

Case1: power(3, 6)

= 3 * 3 * 3 * 3 * 3 *3  [size = 6]
= 3^2 * 3^2 * 3^2  [size = 3]
= power(3^2, 3)
= ...

즉, power(3, 6)은 power(3^2, 3)과 같다.

Case2: power(3, 7)

= 3 * power(3, 6)

재귀적인 방법으로 위 아이디어를 구현한 코드는 다음과 같다.

public static int powerWithImp(int M, int N) {
    if(N == 0) return 1;
    if(N == 1) return M;
  
    if(N%2==0) 
        return powerWithImp(M*M, N/2);
    else 
        return M * powerWithImp(M*M, N/2);
}

[참고문헌]
1. Programming Interview Questions: CareerCup.com
2. SICP: Structure and Interpretation of Computer Programs, MIT press

Loading ...