[알고리즘] Big-O 표기법 : 공간복잡도

이전 글에서는, 빅오 표기법의 시간 복잡도에 대해 설명했다.
알고리즘들이 얼마나 빨리 실행되는지, 그 시간을 검사하는 척도가 시간 복잡도(time complexity)이다.
이제는 시간 대신에 공간, 사용되는 메모리를 주목해보자.

공간 복잡도(auxiliary space complexity)

입력을 제외하고, 알고리즘 자체에서 요구되는 공간을 의미한다.

공간 복잡도 특징

• boolean, 숫자형, undefined, null은 js에서 변하지 않는 공간이다. 1과 1000이라고 해도, 차지하는 공간은 같다.
• 문자열은 O(n)공간이 필요하다. 문자열은 문자열의 길이에 따라 차지하는 공간이 달라지기 때문이다.
• 참조 타입, 배열, 객체도 대부분 O(n)공간이 필요하다.

Example.1

function sum(arr){
  let total = 0; // (1)
  for (let i = 0; i < arr.length; i++){ // (2)
    total += arr[i];
  }
  return total;
}

1. total 변수에 한 공간이 할당된다.
2. 시간은 신경쓰지 않고, 이미 할당된 공간만 구한다. (let i = 0;)

arr.length가 아무리 커진다 해도, 숫자형 변수 i와 total의 공간은 변하지 않으므로 입력의 크기가 차지하는 공간과는 아무런 상관이 없다.

즉, O(1)의 공간 복잡도를 가진다.

Example.2

function double(arr){
  let newArr = []; // (1)
  for (let i = 0; i < arr.length; i++){ // (2)
    newArr.push(2 * arr[i]); // (2)
  }
  return newArr;
}

1. newArr 변수에 배열공간이 할당된다.
2. 배열 변수를 사용했기 때문에 arr의 크기(n)에 따라 공간을 더욱 차지하게 된다.

따라서, O(n)의 공간 복잡도를 가진다.