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

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

a를 n번 곱하는 거듭제곱을 계산할 때,
가장 직관적인 방법은 a를 n번 곱해주는 것이다. 이때 시간복잡도는 O(n)이다.
반면 분할 정복을 사용하면 시간복잡도는 O(log(n))이다.
n이 커질수록 기존 방법에 비해 필요한 연산 횟수가 지수적으로 감소하는 것이다.

분할 정복을 구현하는 방법은 반복문과 재귀문이 있다.

반복문

def iterative_power(a, n):
	result = 1
    while n>0:
    #n이 홀수인 경우 결과에 a를 곱하고 n을 하나 감소
    if n%2 == 1:
    	result *= a
        n -= 1
    # a를 제곱하고 n을 반으로 줄임
    a *= a
    n //= 2
return result

a^n을 계산하는 과정에서, 지수인 n을 차례대로 절반씩 줄여나가는 방법으로 이해했다.

재귀문

def recursive_power(a, n):
	if n == 1:
    	return a
    else:
    	half = recursive_power(a, n//2)
        if n%2==0:
        	return half*half
        else:
        	return half*half*a

recursive_power(2,4)면 (2,4)->(2,2)->(2,1)=2->(2,2)계산->(2,4)계산
이런 단계인가 ... 매우 귀찮군
그냥 반복문이 효율적일 것 같다
실제로 반복문이 더 빠르다고 한다