Big-O Notation - 공간 복잡도

이번 포스팅에서는 공간 복잡도에 대해 이야기해보도록 하겠습니다.

---

1. 공간 복잡도란?

공간 복잡도는 해당 문제를 해결하기위해 얼마나 많은 공간(메모리)을 필요로 하느냐를 나타내는 척도입니다.
공간 복잡도 또한 시간복잡도와 같이 빅 오 표기법으로 표현 할 수 있습니다.
빅 오로 공간복잡도를 표현할 때 핵심 질문은

 "데이터 원소가 N개 일 때 알고리즘은 메모리 단위를 얼마나 소모할까?"입니다.

아래의 코드를 한 번 보겠습니다.

 

function makeUpperCase(array) {
    let newArray = [];
    for (let i = 0; i < array.length; i++) {
        newArray[i] = array[i].toUpperCase()
    }
    return newArray;
}

 

위의 코드는 크기 $ N $ 인 배열을 입력받아 크기 $ N $ 의 새로운 배열을 생성하여 복사하고 반환하고 있습니다.
총 $ N $ 개의 메모리를 추가로 사용하였으므로 $ O(N) $ 이 되게 됩니다.

 

메모리 효율 관점에서 위의 코드를 튜닝해 보겠습니다.

 

function makeUpperCase(array) {
    for (let i = 0; i < array.length; i++) {
        array[i] = array[i].toUpperCase()
    }
    return array
}

 

새로운 메모리를 할당하지 않고 입력받은 메모리를 그대로 사용하여 추가메모리가 없으므로 $ O(1) $ 상수 복잡도가 나오게 됩니다.

 

공간 복잡도를 얘기할 때 주의할 점은

 설명하는 인원에 따라 알고리즘을 시작하기 이전 입력값으로 제공하는 데이터( 보조공간, auxiliary space )를 공간복잡도에 포함시키느냐 마느냐에 이견이 있습니다.
때문에 공간복잡도 설명된 자료를 분석할 때는 원래 입력을 포함하는지를 확인해야 합니다.

---

 

2. 재귀에 숨겨진 공간 복잡도

 

 간단한 재귀함수를 하나 보겠습니다.

 

function recurse(n) {
    if(n < 0) return;

    console.log(n)
    recurse(n - 1)
}

 

별도 자료구조를 사용하지 않으니 해당 함수 호출이 공간을 추가로 차지하지 않을까요?
이 때는 함수의 호출방식을 확인할 필요가 있습니다.
함수 내에서 함수를 호출할 때마다 우리는 해당 호출 사실을 호출 스택이란 공간에 저장을 합니다
recurse(100)을 호출한다면 recurse(-1)을 호출 할 때까지 호출 스택의 101개의 단위공간을 차지하게 되는 것입니다.
다시 말하면 "재귀 함수는 재귀 호출 횟수만큼의 단위 공간을 차지한다"라고 표현할 수 있습니다.
따라서 재귀 함수 사용 시 최대 재귀 호출 횟수와 주어진 환경을 고려하여 사용할 수 있도록 합니다.

 

---

마치며

알고리즘 문제 풀이에서 공간 복잡도보다는 시간복잡도에 맞춰서 풀게 되는데요.
공간의 활용이 실무 환경에서 IOT관련 장비 등 하드웨어 성능이 제한된 환경에서는 꽤나 까다로운 문제를 발생시키고는 합니다.
알고리즘에서 시간과 공간은 일반적으로 트레이드오프(trade-off)한 관계를 가지고 있는 경우가 많습니다.
때문에 주어진 환경에 맞춰 알맞은 알고리즘의 선택이 중요합니다.