Python으로 알고리즘 공부 09. 정수의 제곱 계산

제곱 계산

• 제곱 계산은 ​의 형식을 형태이다.

• 본 포스팅에서는 b가 자연수인 경우 제곱 계산을 다루므로 ​으로 표기하겠다.

• 파이썬에서 제곱 계산은 pow(a, n) 함수를 사용하거나, a**n 연산을 사용하면 된다.

• 이제 power함수를 구현해보자.

1. n번 곱하기

def power(a, n):
    ret = 1
    for i in range(n):
        ret *= a
    return ret
    
print(power(5, 5))
print(power(5, 21))

• 1에다가 a를 n번 곱한다.

• 시간복잡도는 O(N)

2. ​의 power 함수

def power(a, n):
    ret = 1
    while n > 0:
        if n % 2 != 0:
            ret *= a
        a *= a
        n //= 2        
    
    return ret
    
print(power(5, 5))
print(power(5, 21))

• ​ 임을 활용하여 계산하는 방법이다.

• n을 제곱해나가면서 계산하므로 시간복잡도는 O(logN)이다.