n의 거듭제곱 구하기 (큰 수의 큰 제곱수 구하기)

n의 제곱을 구할 때 for문을 이용하여 n번 제곱하면 시간복잡도가 O(n)이다.

(아래의 코드는 5를 1000제곱 했을 때의 계산을 구하고자 하는데, 이럴 경우 for문으로 1000번을 돌려야 한다.)

int n = 5, k = 1000;
long long result = 1;
for(int i = 0; i < k; i++) result *= n;

k가 작은 수라면 문제가 없지만 k가 1000도 아닌 100,000,000처럼 큰 수이면 어떻게 될까? 그럴 때에는 아무리 O(n)이라도 시간이 꽤 오래 걸릴 것이다. 이럴 때 연산 시간을 O(logn)까지 줄이는 방법이 있다.

 

재귀함수 등 여러가지 방법이 있으나 이번에는 지수 계산을 이용한 방법으로 해결해보았다.

 

간단한 예시로 2를 10번 제곱한다고 생각해보자. for문을 돌리면 10번을 돌려야 한다.

그러나 아래와 같이 지수계산을 이용한다면 총 3번만에 답을 구할 수 있다.

(실제로 코드 상으로는 k가 10일때부터 while문이 돌아가기 때문에 코드가 4번이 돌아간다.)

$${{2}^{10}}\\
= ({2^5})^2\\
= {(({2^2})^2)^2}2^2\\
= {(({(2)^2})^2)^2}2^2\\$$

코드는 아래와 같다. (n과 k가 모두 크다는 가정을 했기에 long long type을 사용했다.)

코드(C++)

long long pow(long long n, long long k) {
    long long res = 1;
    while (k > 0) {
        if (k % 2 == 1) res *= n;
        
        n *= n;
        k >>= 1;
    }
    return res;
}