02. 거듭 제곱 계산 함수 (x ** y)

02. 거듭 제곱 계산 함수 (x ** y)

(1) 시간 복잡도 O(y)-1

def power(x, y):
    total = 1

    # x를 y번 곱해 준다
    for i in range(y):
        total *= x

    return total


# 테스트
print(power(3, 5))
print(power(5, 6))
print(power(7, 9))

# 결과 
# 243
# 15625
# 40353607

(2) 시간 복잡도 O(y)-2

def power(x, y):
    if y == 1:
        return x
    elif y>1:
        x = x * power(x,y-1)
    return x


# 테스트
print(power(3, 5))
print(power(5, 6))
print(power(7, 9))

# 결과 
# 243
# 15625
# 40353607

(3) 시간 복잡도 O(lg y)

def power(x, y):
    if y == 0:
        return 1

    # 계산을 한 번만 하기 위해서 변수에 저장
    subresult = power(x, y // 2)

    # 문제를 최대한 똑같은 크기의 문제 두 개로 나눠준다 (짝수, 홀수 경우 따로)
    if y % 2 == 0:
        return subresult * subresult
    else:
        return x * subresult * subresult


# 테스트
print(power(3, 5))
print(power(5, 6))
print(power(7, 9))

# 결과 
# 243
# 15625
# 40353607

<참고>
# y가 8인 경우 함수가 4번 호출되고, y가 32인 경우 6번 호출
 power(2, 8)
 power(2, 4)
 power(2, 2)
 power(2, 1)