알고리즘 성능 평가 [2] : 공간 복잡도(Space Complexity)

 

 

공간 복잡도 (Space Complexity)

시간 복잡도가 알고리즘의 연산횟수, 수행시간을 평가하는데 쓰이는 척도라면,

공간 복잡도는 알고리즘이 메모리를 얼마나 사용하는 지에 관한 척도입니다.

 

알고리즘을 설계할 때는 시간 복잡도와 공간 복잡도 모두 고려한 적절한 알고리즘을 설계 및 사용해야 합니다.

 

다만, 두 마리 토끼를 둘 다 잡을 수 없을 경우엔 공간 복잡도 보다는 시간 복잡도를 더 우선시하는 경향이 있습니다.

하드웨어의 발전 메모리 용량 자체가 커지기도 했고, 병렬 처리와 분산 컴퓨팅 역시 발전했습니다.

요즘 같은 대용량 데이터를 처리해야 하는 시대에는 처리 시간이 짧은 알고리즘이 중요하기 때문입니다.

 

그럼에도, 공간 복잡도는 중요한 개념입니다.

하드웨어가 얼마나 발전했던 간에, 메모리의 한계는 역시나 존재하고,

대용량 데이터를 처리할 때 처리 시간을 최소화 해야 함은 맞지만,

대용량인 만큼 더 많은 공간을 사용하기 때문입니다.

특히나 IoT 환경(임베디드)에서는 메모리가 상당히 타이트한 만큼, 더더욱 공간복잡도를 고려해야 하지요.

 

 

 

고정 크기와 가변 크기

공간 복잡도는 고정 크기(Fixed Size)와 가변 크기(Variable Size)의 합으로 나타냅니다.

 

고정 크기(Fixed Size)는 입력과 무관하게 일정한 메모리 공간을 사용하는 경우입니다.

입력이 얼마나 커지든, 늘 동일한 메모리 양이 필요하지요.

 

반면에 가변 크기(Variable Size)는 입력에 따라 메모리의 사용량이 변하는 경우입니다.

입력이 커질수록 더 많은 메모리가 필요합니다.

 

 

 

빅 - 오(Big - O) 표기법과 공간복잡도

공간복잡도 역시 시간복잡도와 마찬가지로 빅 오(Big-O) 표기법을 주로 사용합니다.

 

O(1)

int value = 1;
System.out.println("Value: " + value);

 

O(1)은 매우 간단합니다. 상수 크기의 변수를 사용할 때지요.

입력의 크기가 어찌 되었든간에 늘 일정하게 추가적인 메모리를 사용하지 않습니다.

 

 

 

버블정렬의 공간복잡도

public static void main(String[] args) {
    int[] arr = {3, 4, 5, 6, 7, 8, 9, 0, 234, 54};
    bubbleSort(arr);
}

static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 1; j < arr.length - i; j++) {
            if (arr[j - 1] > arr[j]) {
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

 

버블정렬의 시간복잡도는 for문이 2중 중첩이기에 O(n^2) 입니다.

다만 for문 내에서 새로운 변수나 배열을 생성하는게 아니므로,

배열 arr의 메모리만 생각하면 될 줄 알고 당연히 O(n) 인줄 알았으나...

 

https://stackoverflow.com/questions/13721890/space-complexity-of-bubble-sort-algorithm

Space complexity of bubble sort algorithm

 

아무래도 공간복잡도의 계산 자체는

'해당 알고리즘을 적용하는 부분에서 새로 만들어지는 요소'에 한정하나 봅니다.

이미 생성된 배열 arr은 공간복잡도 계산에서 제외하고,

bubbleSort를 위해 만든 변수 int temp만 공간복잡도 계산에 포함되므로,

bubbleSort의 공간복잡도는 O(1)이 됩니다.

 

 

 

재귀로 구현된 피보나치 

public static void main(String[] args) {
    System.out.println("Fibonacci: " + fibonacci(10));
}

static int fibonacci(int n) {
    if (n <= 1) return 1;
    return n + fibonacci(n - 1);
}

 

 

반면에 재귀적으로 구현된 피보나치 수열의 경우 어떨까요?

마지막 연산 (n=1)이 끝나기 전까지 모든 n이 메모리에 남아있습니다.

시간복잡도 O(n)인 셈이죠.

 

 

공간복잡도는 for문이 얼마나 중첩되있냐로 쉽게 유추 가능하던 시간복잡도와 달리,

'알고리즘 수행 과정에서 얼마나 많은 메모리가 추가로 할당되느냐'가 핵심입니다.

 

 

 

마치며

시간복잡도와 달리, 공간복잡도는 생각보다 자료가 그리 많지 않아 다소 애먹었습니다.

스택 오버플로우와 처음보는 해외 사이트를 주구장창 뒤지며 작성했네요.