고속거듭제곱

계기

Softeer의 슈퍼바이러스 문제에서 거듭제곱을 계속 하는 로직을 구현했지만

시간초과 에러를 만나게 되어서 정리하게 되었다.

---

일반 거듭제곱 알고리즘

 

일반 거듭제곱 알고리즘은 기본적으로 주어진 수 a를 b번 곱하는 것을 의미한다.

즉, ab의 값을 계산하는 것이다. 간단한 방법으로는 반복문을 사용하여 a를 b번 곱하는 것이다.

 

public static long power(long a, long b) {
    long result = 1;
    for (long i = 0; i < b; i++) {
        result *= a;
    }
    return result;
}

이 방법의 시간 복잡도는 O(n)이다. 왜냐하면 반복문이 b번 실행되기 때문이다.

이는 b가 커질수록 매우 비효율적이 될 수 있다.

 

하지만 분할 정복을 사용한 고속 거듭제곱 알고리즘을 사용하면 좀 더 효율적인 코드를 작성할 수 있다.

---

 

고속 거듭제곱 알고리즘

 

원리

 

고속 거듭제곱, 또는 분할 정복 거듭제곱 알고리즘은 거듭제곱을 계산할 때 시간 복잡도를 크게 줄이는 방법이다.

이 알고리즘의 핵심은 거듭제곱의 지수를 분할하여 계산하는 것이다.

 

일반적인 거듭제곱 계산 ab는 a를 b번 곱하는 것을 의미한다.

하지만 고속 거듭제곱 알고리즘은 지수 b를 반으로 나누어 계산한다.

 

 

예를 들어, 지수가 짝수일때 'a'의 10제곱을 계산한다고 가정해보자.

1. 'a'의 10제곱은 'a'의 5제곱을 두 번 곱한 것과 같다
2. 'a'의 5제곱은 홀수 지수이므로, 이를 'a' 곱하기 'a'의 4제곱으로 표현할 수 있다.
3. 'a'의 4제곱은 짝수 지수이므로, 이를 'a'의 2제곱을 두 번 곱한 것과 같다.
4. 이제 'a'의 2제곱을 계산하고, 그 결과를 제곱한 다음 'a'와 곱하여 최종 결과를 얻는다.

이제 이 모든 계산을 병합하면 다음과 같다.

• 'a'의 10제곱 = ('a'의 5제곱) x ('a'의 5제곱)
• 'a'의 5제곱 = 'a' x ('a'의 4제곱)
• 'a'의 4제곱 = ('a'의 2제곱) x ('a'의 2제곱)
• 'a'의 2제곱 = ('a'의 1제곱) x ('a'의 1제곱)
• 'a'의 1제곱 = 'a'

그러면 지수가 홀수일때 'a'의 9제곱을 계산한다고 가정해 보자.

1. a'의 9제곱은 'a' 곱하기 'a'의 8제곱으로 표현할 수 있다.
   왜냐하면 9는 홀수이고, 홀수 지수의 거듭제곱은 그 수 자체를 한 번 곱하고 나머지를 짝수 지수로 계산하기 때문이다.
2. 'a'의 8제곱은 짝수 지수이므로, 이를 'a'의 4제곱을 두 번 곱한 것과 같다
3. 'a'의 4제곱을 계산하기 위해, 다시 'a'의 2제곱을 두 번 곱한다.
4. 'a'의 2제곱은 다시 'a'의 1제곱을 두 번 곱한 것과 같다
5. 마지막으로, 'a'의 1제곱은 'a' 자체이다.

이제 이 모든 계산을 병합하면 다음과 같다.

• 'a'의 9제곱 = 'a' x ('a'의 8제곱)
• 'a'의 8제곱 = ('a'의 4제곱) x ('a'의 4제곱)
• 'a'의 4제곱 = ('a'의 2제곱) x ('a'의 2제곱)
• 'a'의 2제곱 = ('a'의 1제곱) x ('a'의 1제곱)
• 'a'의 1제곱 = 'a'

이 과정을 반복하면서, 지수가 큰 경우에도 빠르게 거듭제곱을 계산할 수 있게 된다.

---

 

구현

public static long fastPower(long a, long b) {
    long result = 1L;
    while (b > 0) {
        if (b % 2 == 1) {
            result *= a;
        }
        a *= a;
        b /= 2;
    }
    return result;
}

이 코드에서는 while 반복문을 사용하여 지수 b가 0이 될 때까지 계속 계산한다.

지수가 홀수일 때는 결과에 a를 곱하고, a와 지수 b를 각각 제곱하고 반으로 줄인다.

---

시간 복잡도

고속 거듭제곱 알고리즘의 시간 복잡도는 O(log⁡ n) 이다.

왜냐하면 지수를 매번 반으로 줄이기 때문에, b의 크기에 대해 로그 시간에 비례하여 작업이 수행된다.

이는 지수가 매우 큰 경우에도 효율적으로 계산할 수 있게 해준다.