[JS 알고리즘&자료구조] 공간 복잡도

앞서 봐왔던 것들처럼 알고리즘이 얼마나 빨리 결과를 도출해내는 지를 보는 것은 '시간 복잡도'를 보는 것이다. 시간 복잡도는 입력 값과 실행 시간 간의 상관 관계를 나타낸다. 

이제는 입력 값이 커질수록 알고리즘이 얼마나 많은 공간, 즉 메모리 차지하는지 살펴보는 '공간 복잡도'에 대하여 얘기해보겠다.

입력 값은 내가 어떤 것을 입력하느냐에 따라 무한대로 커질 수가 있다. 그렇기에 입력 값을 일단 제외하고 알고리즘 자체가 필요로 하는 공간을 '보조 공간 복잡도' 라는 말로 나타낸다. 공간 복잡도에서 중요한 것은 알고리즘 그 자체이다. 알고리즘 자체가 어떤 영향을 끼치는지 한 번 살펴보자. (참고로 공간 복잡도가 결국 보조 공간 복잡도를 나타내는 것이라고 봐도 무방하다)

공간 복잡도의 몇 가지 규칙을 살펴보자

1. Boolean, Number, undefined, null은 모두 불변 공간이다.
   
2. String은 O(n)의 공간을 필요로 한다 : String의 길이가 길어질수록 차지하는 공간이 커지는 것이기 때문
3. 배열과 객체 등도 O(n)의 공간을 필요로 한다.

예시를 하나 보자.

function sum(arr) {
	let total = 0; // 하나의 숫자 공간
    for (let i = 0; i < arr.length; i++) { // 'let i = 0' 또한 하나의 숫자 공간
    	total += arr[i];
    }
	return total;
}

위의 예제를 보면 total과 i에 숫자가 할당이 된다는 것을 볼 수 있다. 걸리는 시간을 제외하고 나면 결국 할당되는 공간은 total과 i만 존재하는데 해당 공간들에는 오로지 숫자만 들어간다. 위의 규칙에서 숫자(Number)는 불변 공간이라고 했다.  그렇기 때문에 해당 알고리즘은 O(1) Space를 차지한다.

또 다른 예시를 보자.

function double(arr) {
  let newArr = []; 
  for (let i = 0; i < arr.length; i++) { 
    newArr.push(2 * arr[i]); // arr의 길이에 따라 무한대로 늘어난다
  }
  return newArr;
}

위의 알고리즘이 차지하는 공간은 들어오는 배열의 크기에 비례하여 무한대로 늘어날 수 있다. 그렇기 때문에 해당 알고리즘은 O(n) Space를 차지한다고 말할 수 있다.