반응형 거듭제곱1 ⚡ 고속 거듭제곱 알고리즘 간단설명! 요약 지수를 2진법으로 바꿈 밑을 제곱해서 올려가며 2진법에서 1일 때만 곱해줌 그냥 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일때) 결과값에 제곱한 결과를 곱해줌. 2022. 10. 6. 이전 1 다음 반응형
