[알고리즘] 코드잇 - 거듭 제곱 빠르게 계산하기(Python)

실습설명

거듭 제곱을 계산하는 함수 power()를 작성하고 싶습니다. power()는 파라미터로 자연수 x와 자연수 y를 받고 x^y를 리턴합니다. 가장 쉽게 생각할 수 있는 방법은 반복문으로 단순하게 x를 y번 곱해 주는 방법입니다.

def power(x, y):
    total = 1
    
    # x를 y번 곱해 준다
    for i in range(y):
        total *= x
    
    return total

이 알고리즘의 시간 복잡도는 O(y)인데요. O(lg y )로 더빠르게 할 수는 없을까요?

 

주의사항

return x**y는 답이 아닙니다. 우리는 거듭 제곱을 구하는 원리를 파악하여 효율적인 알고리즘을 구현하고 싶은 것입니다.

 

 

답안

def power(x, y):
    if y == 0:
        return 1

    # 계산을 한 번만 하기 위해서 변수에 저장
    subresult = power(x, y // 2)
    
    # 문제를 최대한 똑같은 크기의 문제 두 개로 나눠준다 (짝수, 홀수 경우 따로)
    if y % 2 == 0:
        return subresult * subresult
    else:
        return x * subresult * subresult


# 테스트 코드
print(power(3, 5))
print(power(5, 6))
print(power(7, 9))