⚡ 고속 거듭제곱 알고리즘 간단설명!

요약

1. 지수를 2진법으로 바꿈
2. 밑을 제곱해서 올려가며 2진법에서 1일 때만 곱해줌
3. 그냥 n번을 곱하면 복잡도 O(n)이나 이 방식은 O(log n)임

 

설명

def fast_pow(a, b):
    ret = 1
    while b:
        if b%2:
            ret *= a
        a *= a
        b >>= 1 # 혹은 b //= 2

    return ret 

print(fast_pow(2, 10))

파이썬 코드

 

• 밑 a와 지수 b를 입력받음
• b는 계속 2로 나눠주고, a는 계속 제곱을 시킴. b를 2로 나눈 값이 1일 때(2진수에서 해당 자리수가 1일때) 결과값에 제곱한 결과를 곱해줌.