(22.08.20)거듭제곱의 분할정복

거듭 제곱을 구할 때 우리는 보통
$$a^n = a*a*a*   \cdots   *a$$를 떠올린다.

 

 

 

즉, a를 n번 무식하게 곱하는 것이다.

 

하지만 이것을 컴퓨터가 연산한다면, 시간복잡도가 어떻게 될까?

 

int main(void) {
    int a, n;
    cin >> a >> n;
    //a^n을 선형 시간 복잡도로 곱한다.
    long long result = 1;
    for (int i = 0; i < n; ++i) 
        result *= a;
    
    cout << result;

}

$$ O(n) $$

선형의 시간 복잡도를 갖게 되는 것이다.

 

그럼 더 효율적인 방법이 있을까?

분할정복 전략(divide and conquer strategy)을 사용하면 된다.

 

$$  a^n = \begin{cases} & a^{n/2} * a^{n/2} &(even) \\ &  a^{n-1/2} * a^{n-1/2} * a &(odd)\end{cases} $$

위의 점화식을 Bottom-up 방식으로 Dyamic programming 하면된다.

typedef long long ll;


int main(void) {
    ll a, n;
    cin >> a >> n;
    ll result = 1;
    while (n > 0) {
        //n이 홀수일 경우 즉, 이진수의 가장 아래 자리수가 1인 경우
        if (n % 2 == 1)
            result = (a * result);
        a = (a * a);
        //이 비트 연산은 수슬 이진수 자릿수를 1개씩 내리는 연산
        n >>= 1;
    }

    cout << result;
}

예를들어 6의 5제곱을 한다고 생각하면,

 

while 반복문이 진행됨에 따라 a = a * a 이기 때문에,

0:  a = 6

1:  a = 6^2

2:  a = 6^4

3:  a = 6^8

 

2^i 만큼 거듭제곱의 수가 늘어난다. (i는 반복 횟수)

만약 반복문에서 n이 홀수라면, 이진수의 가장 아래 자리에 1이 남게되므로, 결과에 곱해주고

 

a에 다시 a를 곱한뒤에 n >>= 1  비트 연산을 통해 이진수의 자리를 1개씩 낮춘다(2로 나눈것과 같다.)

 

따라서, 남은 연산의 수를 2로 나눠가면서 계산할 수 있다.

$$ 6^5 = 6^4 * 6^1 $$ 

이 경우 기존의 방식의 5번이 아닌 3번의 반복문만 거치면 되고,

 

n = 7일 경우

$$ 6^7 = 6^4 * 6^2 * 6^1 $$

이 경우에는 7번이 아니라 역시 3번의 반복문만 거치면 된다.

 

따라서 분할정복을 이용한 거듭제곱의 시간 복잡도는

$$ O(log\;n) $$

으로 로그 시간이다.

 

 

관련 문제 백준 1629번: https://www.acmicpc.net/problem/1629