공간 복잡도 (Space Complexity)

시간 복잡도와 마찬가지로, 알고리즘의 성능을 평가할 때 사용하는 방법이다.

특히 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법이라고 할 수 있다.

최근 기술이 너무 좋아진 탓에, 시간 복잡도에 비해 중요도가 떨어지는 경향이 있다.

더불어 효율적인 알고리즘을 사용하는 경우에 시간 복잡도와 공간 복잡도는 반비례한다.

좋은 알고리즘을 사용하여 시간 복잡도가 낮을 때는 공간 복잡도가 높아지지만, 반대로 공간 복잡도가 낮은 경우에는 보통 시간 복잡도가 높기 때문이다.

공간 복잡도에 영향을 미치는 요소들

• 변수
• 자료구조(Data Structure)
• 함수 호출(Function Call)
• 할당(Allocation)

//공간 복잡도
const spaceComplexity = (array) => {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i]);
  }
};

위 함수의 경우, 공간 복잡도는 O(1)이다.

i라는 변수에 0을 할당한 것 외에, 공간을 차지하는 것이 없기 때문이다.

그리고 아래의 예제를 보자

const spaceComplexity2 = (array) => {
  let result;
  for (let i = 0; i < array.length; i++) {
    result += array[i];
  }
};

해당 예제의 경우에도 마찬가지로 공간 복잡도는 O(1)이다.

중간에 반복문에서 result에 여러 번 할당이 이루어지지만, for문 안에서만 할당되는 지역변수이기 때문이다.

결과적으로, input이 얼마나 큰지는 공간 복잡도에서 중요하지 않다.

const spaceComplexity3 = (n) => {
  let array = [];
  for (let i = 0; i < n; i++) {
    array[i] = i;
  }
  return array;
};

하지만 위의 예제의 경우, 반복문이 n만큼 도는 동안 공간이 하나씩 추가된다.

재귀함수와 함께, 이런 경우의 공간 복잡도는 O(n)이 된다.

공간 복잡도를 줄이는 방법

프로그램에 필요한 공간은 크게 고정공간과 가변공간으로 나뉜다.

시간 복잡도를 무시하고, 공간 복자도의 효율을 높이고자 한다면 가변공간을 사용하는 알고리즘이 효율적일 것이다.

참고 자료

[Algorithm] 시간 복잡도, 공간 복잡도

[자료구조] 시간복잡도 with Javascript