거듭제곱 함수

거듭제곱 (Power)

주어진 수나 문자를 주어진 횟수만큼 여러번 곱하는 이항연산을 말한다.

두 가지 순환 알고리즘과 하나의 반복적인 알고리즘을 통한 계산 방법이 있다.

순환

1. 순환적인 팩토리얼 알고리즘과 동일한 방법

정의

소스코드

def power(x, n):
    if n == 0:
        return 1;
    else:
        return x * power(x, n-1)

시간복잡도

---

2. xⁿ = (x²)^n/2 공식을 이용한 방법

정의

소스코드

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

시간복잡도

공식을 이용한 두번째 방법은 순환 호출이 일어날 때 문제의 크기가 절반으로 줄어든다.

그래서 n 값이 0 이 될 때 까지 반복대치를 진행하였을 경우, n 값이 일정하게 감소하는 알고리즘과는 달리 n 번 반복되었다고 할 수 없다.

문제의 크기가 절반으로 줄어든다는 점에 주목하여 n = 2^k, k = log₂n 으로 가정하고 순환을 모두 마쳤을때의 표현을 k 로 하자. 참고로 n 을 2^k 로 가정하는것은 단조증가함수라고 하여 점근적 복잡도를 구현하는데 전혀 지장을 주지 않는다고 한다.

이어서 k 로 나타낸 식을 log₂n 으로 치환하면 O(log₂n) 복잡도를 얻을 수 있다.

반복

소스코드

def slow_power(x, n):
    product = 1
    for i in range(0, n):
        product *= x
    return product

시간복잡도