[Algorithm] 분할 정복을 이용한 a^b

a^b, a 제곱 b 는 일반적으로 다음과 같이 구현할 수 있습니다.

int pow(int a,int b){
    int result = 1;
    for (int i=0;i<b;i++){
        result *= a;
    }
    return result;
}

a^b 의 의미 그대로 a 를 b 번 곱하여 원하는 결과를 얻을 수 있습니다.

직관적이기는 하나, O(b) 의 시간복잡도로 개선의 여지가 있습니다.

 

이를 분할 정복, Divide And Conquer 을 통해서 구현가능합니다.

int powDAC(int a, int b){
    if (b==0) return 1;
    else if (b==1) return a;
    else if (b%2==0) {
        int temp = powDAC(a,b/2);
        return temp*temp;
    }
    else return a*powDAC(a,b-1);
}

여기서 주의해야 할 점은 b 가 짝수일 경우입니다.

현재 한 번의 함수 호출로 temp 에 저장한 후 이를 제곱해주었습니다.

만약 아래와 같이 두 번의 함수 호출이 일어난다면 시간복잡도의 이점이 사라지게 됩니다.

 else if (b%2==0) { 
        return powDAC(a,b/2)*powDAC(a,b/2);
    }