[파이썬] 거듭 제곱 빠르게 계산하기

실습 설명

거듭 제곱을 계산하는 함수 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(lgy)로 더 빠르게 할 수는 없을까요?

실습 결과

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))

243
15625
40353607

시간 복잡도

2 의 8승을 계산하기 위해서는 몇 번의 함수 호출이 있을까요?

power(2, 8)
power(2, 4)
power(2, 2)
power(2, 1)

그렇다면 3의 32승을 계산하기 위해서는 몇 번의 함수 호출이 있을까요?

power(3, 32)
power(3, 16)
power(3, 8)
power(3, 4)
power(3, 2)
power(3, 1)

y가 8인 경우 4번 호출되고, y가 32인 경우 6번 호출됩니다. 총  lgy+1번의 호출이 있는 거죠.

O(lgy+1)이기 때문에, 이 알고리즘의 시간 복잡도는 O(lgy)입니다.