19장 공간 제약 다루기

알고리즘의 효율성 척도에는 알고리즘이 얼마나 많은 메모리를 소모하는가, 즉 공간 복잡도 또한 있다. 메모리 제한이 있다면 공간 복잡도가 중요한 요인이다.

빠르면서도 메모리 효율적인 알고리즘이 이상적이지만, 둘 다 만족시킬 수 없는 상황이 있을 것이고 결국 둘 중 하나를 선택해야만 한다. 상황마다 속도가 중요한지, 메모리가 중요한지를 따져 우선순위를 매겨야 한다.

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개인 새로운 배열을 생성한다. 즉, 원래 배열 이외에 메모리를 더 소모한다.

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

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

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

버전	시간 복잡도	공간 복잡도
버전1	O(N)	O(N)
버전2	O(N)	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;
}

// 버전2, 시간 복잡도 O(N), 공간 복잡도 O(N)
function hasDuplicateValue(array) {
  let existingValues = new Map();
  for(let i = 0; i < array.length; i++) {
    if(!existingValues.has(array[i]) {
       existingValues.set(array[i], true);
  	} else {
      return true;
    }
  }
  return false
}

버전1은 중첩 반복문을 돌며 시간 복잡도가 O(N²)이지만 추가적인 메모리 소모가 없으므로 공간 복잡도가 O(1)이다.

버전 2는 해시 테이블을 사용해 중복을 확인하며, 시간 복잡도와 공간 복잡도 모두 최악의 경우 O(N)이다.

버전	시간 복잡도	공간 복잡도
버전1	O(N²)	O(1)
버전2	O(N)	O(N)

애플리케이션이 빨라야 한다면 시간 복잡도가 효율적인 버전2가, 속도는 상관없지만 메모리를 절약해야 한다면 버전1이 더 나은 선택일 수 있다.

// 버전3, 시간 복잡도 O(N logN), 공간 복잡도 O(logN)
function hasDuplicateValue(array) {
  array.sort((a, b) => a < b ? -1 : 1);
  
  for(let i = 0; i < array.length - 1; i++) {
    if(array[i] === array[i + 1]) {
      return true;
    }
  }
  return false;
}

버전3은 먼저 배열을 정렬하고, 배열 내 각 값을 다음 인덱스 값과 비교한다. 같은 값이 있다면 중복 값이 있는 것이고, 마지막까지 순회했는데 없다면 중복값이 없는 것이다.

가장 빠른 정렬 알고리즘이 O(N logN)이므로, 버전3의 시간 복잡도 역시 O(N logN)이라고 가정할 수 있다. 퀵 정렬 구현 대부분은 O(logN) 공간을 소모한다.

버전	시간 복잡도	공간 복잡도
버전1	O(N²)	O(1)
버전2	O(N)	O(N)
버전3	O(N logN)	O(logN)

시간 복잡도의 관점에서는 버전1 < 버전3 < 버전2이고, 공간 복잡도의 관점에서는 버전2 < 버전2 < 버전1 이다. 시간과 공간 모두를 고려해야 할 때 버전3을 선택할 수 있다.

근본적으로 각 상황마다 최소 허용 속도와 메모리 한도를 알아야 한다.

19.3 재귀에 숨겨진 비용

function recurse(n) {
  if(n < 0) { return; }
  
  console.log(n);
  recurse(n - 1);
}

숫자 n을 받아 0까지 거꾸로 세며 각 숫자를 출력하는 함수다.

이 함수는 새로운 자료 구조를 만들진 않지만, 함수를 호출스택에 N개 만큼 저장해야 한다. 즉 재귀 함수가 최대 O(N)의 공간을 차지한다.

즉, 재귀 함수는 재귀 호출 횟수만큼 단위 공간을 차지한다.

실제로 위 함수에 큰 숫자를 전달하면 맥시멈 콜 스택 에러가 난다. 컴퓨터는 일정 항목 이상의 호출 스택을 감당하지 못한다.

하지만 while문을 사용한다면 큰 숫자를 전달했을 때 오래 걸릴 수는 있지만 적어도 중간에 멈추진 않는다.

퀵 정렬의 공간 복잡도가 O(logN)인 이유도 이때문이다. 퀵 정렬은 재귀 호출을 O(logN)번 수행하므로, 정점에서 호출 스택 크기가 log(N)이기 때문이다.

재귀를 사용하면 하향식 사고방식을 적용할 수 있지만 대용량 데이터나 높은 숫자를 처리해야 한다면 재귀가 알맞지 않을 수 있다.

19.4 마무리

이제 알고리즘을 다른 알고리즘과 비교하고 정보에 입각해 현재 애플리케이션에 사용할 방식을 결정할 수 있는 분석 능력을 갖췄다.