고속 거듭 제곱 알고리즘

문제를 풀다보면 큰 수의 거듭 제곱 수를 구해야할 때가 있다.

거듭 제곱 수를 구하는 알고리즘은 어렵지 않다

long long power(long long x, long long y) {
    long long ans = 1;
    for(long long i = 1; i <= y; i++)
        ans *= x;
    return ans;
}

하지만 위와 같은 코드는 O(n)의 시간 복잡도를 갖게되어 여러 수의 거듭 제곱이나,

 큰 y를 갖는 경우 사용할 수 없다.

그럼 O( log n ) 의 알고리즘을 알아보자.

이 알고리즘은 함수의 재귀 호출로 동작하고,

​(x​​n ​)​​m​ = ​x​​n*m​ 을 이용한 방식이다.

예를 들어 

65536 = 2​​16​ = (((2​​​​2​)​​2​)​​2​)​​2​ 와 같다.

long long power(long long x, long long y) {
    
    if (!y) return 1;
    
    long long answer = 1;
    if (y % 2) answer *= x;
 
    return answer * power(x*x, y / 2);
}

y의 값이 홀수일 경우 x를 곱해주고, 함수를 다시 재귀호출 하는 간단한 방식이다.

마찬가지로 반복문으로 구현할 수도 있다.

long long power(long long x, long long y) {
    long long answer = 1;
    while (y) {
        if (y % 2)answer *= x;
        x *= x;
        y /= 2;
    }
    return answer;
}

끝