[Algorithm] 알고리즘 공간복잡도에 대하여

    공간복잡도란?

    공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나로, 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다. 하지만 최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 충분하다못해 넘치기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌습니다. 시간복잡도의 경우 알고리즘을 잘못 구성하였을 경우 결과값이 나오지 않거나 현저하게 느린속도가 나오기에 최근에는 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성합니다.

     

    [Algorithm] 알고리즘 시간복잡도에 대하여

     

    공간복잡도 계산법 (빅-오)

    int a = 10;
    

    일반적으로 공간이 하나씩 생성되는것을 1이라고 표현합니다. 위의 공간복잡도는 O(1)입니다.

     

    int get_factorial(int n)
    {
        int i = 0;
        int result = 1;
        
        for(i = 1; i <= n; i++)
        {
            result = result * i;
        }
        return result;
    }
    

    반복문이 N번만큼 반복하여도 for문 안에서의 지역변수이므로 위의 공간복잡도는 O(1)입니다. n의 값에 상관없이 함수를 호출하고 i와 result의 변수만 사용됩니다. 다른것은 전혀 영향을 주지 못합니다. 여기서 공간복잡도는 O(1)입니다.

    int get_factorial(int n)
    {
        if(n > 1) return n * factorial(n - 1);
        else return 1;
    }
    

    위처럼 재귀함수일 경우에는 이야기가 달라집니다. 위의 예제를 보시면 함수의 인자값 n에 따라 공간복잡도가 달라집니다. 함수 내부에서 n이 1이하일때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 위의 공간 복잡도는 O(n)입니다.

     

    공간복잡도를 줄이는 방법

    공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 동적할당을 한다면 얼마만큼의 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미칩니다.

    ​프로그램에 필요한 공간은 크게 두가지로 나눌 수 있습니다.

    1. 고정 공간
    2. 가변 공간

     

    시간적인 측면을 무시하고 공간복잡도만을 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는것이 효율적입니다. 또 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다. 특히 재귀 함수같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하기 때문에 ​만약 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로  짜는게 더 효율적이라고 볼 수 있습니다.

    댓글

    Designed by JB FACTORY