[Algorithm] 분할 정복을 이용한 거듭제곱 | 빠른 거듭제곱 | Python

분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다.

 

나무위키에서 인용했다.

 

거듭제곱 또한 분할 정복 알고리즘을 활용하여 빠르게 계산이 가능하다. 임의의 수 C에 대하여 Cⁿ을 구할 때는 C를 n번 곱하므로 시간 복잡도가 O(n)인 반면, 분할 정복을 활용하여 계산하면 O(logn)의 시간 복잡도로 계산이 가능하다. 훨씬 빨라지는 것이다.

 

---

 

분할 정복을 활용하여 거듭제곱을 계산하는 것은 다음과 같은 아이디어로부터 출발한다.

 

$$ C^{n} = \begin{cases} C^{\frac{n}{2}} C^{\frac{n}{2}} \\ C^{\frac{n-1}{2}} C^{\frac{n-1}{2}} C \end{cases} $$

 

임의의 수 C에 대해서 C의 n승은 n이 짝수일 때는 윗줄의 식을, n이 홀수일 때는 아랫줄의 식을 만족한다. 이유는 지수법칙 때문이다.

 

따라서 다음과 같은 함수를 구현 가능하다.

 

def power(C, n):
    result = 1
    while n:
        if n % 2 != 0:
            result *= C
        C *= C
        n //= 2
    return result

 

---

 

이 글을 쓰는 데 도움이 되었던 자료:

 

https://hbj0209.tistory.com/43

[Algorithm] 분할정복을 이용한 거듭제곱