[알고리즘] 거듭제곱 계산 하기, 재귀 함수, python(17)

거듭제곱을 계산하는 함수를 작성하는 것

 

시간 복잡도 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에 담아서 호출하는 게 포인트