분할 정복 - 거듭 제곱 최적화

A^2 = A * A 인 것은 알고 있다.

A^4 = A * A * A * A 도 알고 있다.

A^8 = A * A * A * A * A * A * A * A 인것도 당연하다.

 

그러나 이런 방법으로 알고리즘을 짠다면 시간이 더욱 걸릴 것이다.

그렇기에 연산을 줄여야 한다.

 

A^4 = (A^2)^2 처럼 표현하여 연산을 3번에서 2번으로 줄일 수 있다.

A^8 = ((A^2)^2)^2 또한 연산을 7번에서 3번으로 줄일 수 있다.

 

이 방법을 사용한다면 시간이 확 줄어들 것이다.

 

만약 A^6 과 같은 경우에는 어떻게 할까?

A^6 = A * (A^2)^2 처럼 쓸 수 있을 것이다. 지수가 홀수가 되버리면 따로 A를 빼주는 방법이다.

 

기존의 방법은 O(n)의 시간복잡도를 가졌다면 최적화를 한 경우에는 O(log n)으로 연산이 많아질수록 확 줄어들게 된다.

 

int power(int a, int n) {
    if (n == 1)
        return a;
    int temp = power(a, n/2);
    if (n%2==0)
        return temp*temp;
    else
        return a*temp*temp;
}

위는 분할정복을 활용하여 거듭제곱을 구현한 코드다.

 

.... 어려웡 ㅠ