알고리즘 - 거듭제곱 구하기

거듭제곱 구하기

x의 n 거듭제곱 구하기(억지기법)

def slow_power(x, n):        # 반복으로 $x^n$을 구하는 함수
    result = 1.0
    for i in range(n):
        result = result * x  # 루프: n번 반복
    return result

x의 거듭제곱 구하기(축소정복)

def power(x,n):
    if n == 1:
        return x
    elif (n % 2) == 0:
        return power(x*x, n // 2)
    else:
        return x * power(x*x, (n-1) // 2)

x의 n 거듭제곱 프로그램

import time		# time 모듈 포함
print("    억지기법(2**500) =", slow_power(2.0, 500))
print("축소정복기법(2**500) =", power(2.0, 500))

t1 = time.time()
for i in range(100000) : power(2.0, 500)			# 축소정복 10만회 
t2 = time.time()
for i in range(100000) : slow_power(2.0, 500)	# 억지기법 10만회
t3 = time.time()


print("    억지기법 시간... ", t3-t2)
print("축소정복기법 시간... ", t2-t1)

실행 결과

    억지기법(2**500) = 3.273390607896142e+150  # 2*500 계산결과, 동일함
축소정복기법(2**500) = 3.273390607896142e+150 
         억지기법... 1.6984951496124268
축소정복기법 시간... 0.17752671241760254

• 순환으로 구현되었지만 축소정복기법이 훨씬 빠름

복잡도 분석

• 억지 기법을 이용한 코드 => $O(n)$
• 축소 정복 기법 이용 코드 => $O(log_{2}{(n)})$

정방형 행렬의 거듭 제곱

• 거듭 제곱이 가능하려면, 행과 열의 개수가 같은, 즉 m x m과 같은 정방형(square) 행렬이어야 함

정방형 행렬 M의 n 거듭제곱 구하기

def powerMat(x, n):
    if n == 1:          # 종료조건
        return x
    elif (n % 2) == 0:  # n이 짝수
        return powerMat(multMat(x,x), n // 2)
    else:
        return multMat(x, powerMat(multMat(x,x), (n - 1) // 2))

• 알고리즘의 시간복잡도: $O(m^2log_{2}{(n)})$
• 행렬 크기 무시한다면 $O(log_{2}{(n)})$

억지기법 $O(n)$ 에 비해 훨씬 우월