[재귀 알고리즘] Computing Powers & Fast Version

[재귀 알고리즘] Computing Powers & Fast Version

Computing Powers (제곱 계산하기)

제곱 계산을 재귀적으로 프로그래밍 해보고 더 빨리 계산하는 법도 프로그래밍 해 보겠다.

일반적인 방법,

$$ p(x,n) = x^n $$

$$ p(x,n) = \begin{cases} 1 & \quad \text{n=0} \quad \text{(base case)} \\ x*p(x, n-1) & \quad \text{n>0} \quad \text{(recursive step)} \\ \end{cases} $$

double powerRecursive(double x, int n)
{
    // Time Complexity : O(n)
    if (n==0)
        return 1.0;
    else
        return x*powerRecursive(x, n-1); // base Operation
}
 
double powerLoop(double x, int n)
{
    // Time Complexity : O(n)
    double result=1;
    for(int i=0; i<n; ++i)
        result *= x; // base Operation
    return result;
}

재귀로 구현한 함수와 반복문으로 구현한 함수가 있다. 둘 다 n번의 곱셈이 일어나 시간 복잡도는 O(n)으로 같다. 하지만 실행 속도는 반복문이 훨씬 빠르다. 그 이유는 함수 내에서 함수 호출이 일어나게 되면 호출한 함수의 상태를 저장하고 호출된 함수로 가서 진행하게 된다. 호출된 함수가 종료 되면 호출한 함수의 저장된 상태를 불러와서 이어 진행을 하게 된다. 재귀는 함수 내에서 계속적인 함수 호출이 있게 되므로 함수를 저장하고 불러오는 비용이 많이 들게 된다. 이를 Context Switching 비용이 많이 든다고 한다. 따라서 반복문으로 구현하는게 제일 좋지만 반복문 구현이 어려울 경우 재귀로 비교적 간단히 구현하는 것이다.

다시 돌아와서, 제곱의 성질을 이용해서 더 빠르게 결과를 얻을 수도 있는데 아래를 보면,

$$ (x^2)^n  = \Bigg( \dotsm \bigg( \Big( x^2 \Big)^2 \bigg)^2 \dotsm \Bigg)^2 $$

$$ 2^2 = (2^2)^1 = 4 $$

$$ 2^4 = (2^2)^2 = \Big( 2^2 \Big)^2 = 16 $$

$$ 2^8 = (2^2)^3 = \bigg( \Big( 2^2 \Big)^2 \bigg)^2 = 256 $$

즉, 아래와 같은 재귀식으로 나타낼 수 있다.

$$ p(x, n) = x^n $$

$$ p(x, n) = \begin{cases} 1 & \quad n=0 \quad \text{(base case)}\\ x*p(x, (n-1)/2)^2 & \quad \text{if } n>0 \text{ is odd} \text{(recursive step)}\\ p(x, n/2)^2 & \quad \text{if } n>0 \text{ is even} \text{(recursive step)}\\ \end{cases} $$

코드로 나타내면 아래와 같다.

double fastPowerRecursive(double x, int n)
{
    // Time Complexity : O(logn)
    double y;
 
    if (n==0)
        return 1.0;
    else if (n%2 == 1)
    {
        y = fastPowerRecursive(x, (n-1)/2);
        return x*y*y; // base Operation
    }
    else
    {
        y = fastPowerRecursive(x, n/2);
        return y*y; // base Operation
    }
}

홀수일 때는 앞에 x를 꺼내서 짝수와 같게 만들어 준다. 시간 복잡도는 O(logn)으로 위의 제곱 계산법보다 한 단계 줄었다. 한 단계가 적어 보일 수 있지만 연산 횟수가 커질수록 차이가 기하급수적으로 증가하게 될 것이다. O(n)의 알고리즘에서 1,024번의 연산은 O(logN)에서는 10번의 연산으로 줄어들게 된다. logN은 보통 밑이 2인 로그의 밑을 생략하고 쓰기 때문에 연산 횟수가 10이 된 것이다.

전체 코드

#include <iostream>
using namespace std;
 
double powerRecursive(double x, int n)
{
    // Time Complexity : O(n)
    if (n==0)
        return 1.0;
    else
        return x*powerRecursive(x, n-1); // base Operation
}
 
double powerLoop(double x, int n)
{
    // Time Complexity : O(n)
    double result=1;
    for(int i=0; i<n; ++i)
        result *= x; // base Operation
    return result;
}
 
double fastPowerRecursive(double x, int n)
{
    // Time Complexity : O(logn)
    double y;
 
    if (n==0)
        return 1.0;
    else if (n%2 == 1)
    {
        y = fastPowerRecursive(x, (n-1)/2);
        return x*y*y; // base Operation
    }
    else
    {
        y = fastPowerRecursive(x, n/2);
        return y*y; // base Operation
    }
}
 
int main()
{
    int x = 2;
    int n = 10;
 
    cout << powerRecursive(x, n) << endl;
    cout << powerLoop(x, n) << endl;
    cout << fastPowerRecursive(x, n) << endl;
 
    return 0;
}