알고리즘의 효율성 척도에는 알고리즘이 얼마나 빠른지 시간 복잡도만 있는게 아니라 공간 복잡도 또한 존재한다. 즉, 알고리즘이 얼마나 많은 메모리를 소모하는가가 유용할 수 있다.

메모리 제한이 있다면 공간 복잡도가 중요한 요인이다. 대량의 데이터를 다루거나 메모리가 제한된 작은 장치를 프로그래밍할 때는 정말 중요하다.

19.1 공간 복잡도의 빅 오

시간 복잡도를 표현할 때와 마찬가지로 빅 오 표기법을 사용해 공간 복잡도를 표현한다.

공간 복잡도, 메모리 소모 관점에서 핵심 질문은 **“데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?”**이다

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

이 함수를 공간 복잡도 관점에서 분석하면 원소 N개를 포함하는 새로운 배열을 생성한다. 즉, 원래 배열 이외에 메모리를 더 소모한다.

원소 N개를 추가로 생성했으니 이 함수의 공간 효율성은 O(N)이다.

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

함수를 이렇게 수정하면 새 배열을 생성하지 않고 원래 배열에서 요소들을 수정하고 수정된 배열을 반환한다. 어떤 메모리도 추가로 소모하지 않는다. 즉, 데이터의 개수에 상관없이 추가로 소모하는 메모리 공간이 0으로 상수이므로, O(1)이다.

두 버전 모두 시간 복잡도는 O(N)이지만, 두 번째 버전이 O(1)으로 좀 더 메모리가 효율적이다. 속도를 희생하지 않고 공간 관점에서 효율적이므로 버전2의 승리다.

책마다 다르지만, 이 책은 공간 복잡도를 빅 오 표기법으로 나타낼 때 알고리즘에서 새로 생성한 데이터만 고려한다. 예를 들어 위의 예시에서 입력받은 array가 차지하는 공간은 고려하지 않는다.

알고리즘에서 추가로 소모하는 공간을 보조 공간 auxiliary space이라고 부른다.

19.2 시간과 공간 트레이드오프

다음은 배열을 받아 중복 값이 있는지 확인하고 반환하는 함수다.

// 버전1, 시간 복잡도 O(N²), 공간 복잡도 O(1)
function hasDuplicateValue(array) {
  for(let i = 0; i < array.length; i++) {
    for(let j = 0; j < array.length; j++) {
      if(i !== j && array[i] === array[j]) {
        return true;
      }
    }
  }
  return false;
}