python/알고리즘
[알고리즘] 거듭제곱 계산 하기, 재귀 함수, python(17)
incastle
2019. 4. 14. 22:26
거듭제곱을 계산하는 함수를 작성하는 것
시간 복잡도 n으로 계산을 하면 굉장히 쉽다.
def power(x, y):
if y == 0:
return (1)
else:
return(power(x,y-1)*x)
하지만 시간 복잡도를 logN으로 줄이고 싶다면 이야기는 달라진다.
def power(x, y):
if y == 0:
return 1
# 계산을 한 번만 하기 위해서 변수에 저장
semi_result = power(x, y // 2)
# 문제를 최대한 똑같은 크기의 문제 두 개로 나눠준다 (짝수, 홀수 경우 따로)
if y % 2 == 0:
return semi_result * semi_result
else:
return x * semi_result * semi_result
3^4은
(3^2) * (3^2)이다.
3^2을 기억해두고 다시 계산하지 않고 호출한다면 재귀 함수를 줄일 수 있다.
이를 semi_result에 담아서 호출하는 게 포인트