효율적으로 거듭제곱 계산하기

x의 n-거듭제곱인 x^n 을 계산하기

 

 

# 1. 억지기법

def slow_power(x, n):
    result = 1.0
    for i in range(n):
        result *= x
    return result

 

3행의 반복문에 의해 n에 비례하는 시간이 거릴고, 따라서 시간복잡도가 O(n)이다. 

 

 

# 2. 축소 정복을 이용한 거듭제곱

1번 방법대로 x^10을 구하려면, 총 9번의 곱셈이 필요하다. 

하지만 곱셈 한 번으로 x^2를 구하고, 이를 4번 곱하면, 총 5번의 곱셈으로 x^10을 구할 수 있다. 

 

더 복잡하게 한다면, (x^2) * ( (x^2)^2 )^2 와 같은 방식으로, 총 4번의 곱셈으로 x^10을 구할 수 있다. 

 

def power(x, n):
    if n == 0:
        return 1        # 종료 조건
    
    elif n % 2 == 0 :      # n이 짝수일 경우
        return power(x*x, n//2)
    
    else:               # n이 홀수일 경우
        return x * power(x*x, (n-1)//2)

 

 

# 두 방법의 실행 시간 비교

 

1번의 시간 복잡도는 O(N)

2번의 시간 복잡도는 O(logN)