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개를 추가로 생성했으니 이 함수의 공간 효율성은 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;
}

버전 1은 중첩 루프를 사용하며, 시간 복잡도가 O(N²)이다.

// 버전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
}

버전 2는 빈 해시 테이블을 사용해 중복을 확인하며, 시간 복잡도와 공간 복잡도 모두 최악의 경우 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 < 버전3 < 버전2이고, 공간 복잡도의 관점에서는 버전2 < 버전3 < 버전1 이다. 시간과 공간 모두를 고려해야 할 때 버전3을 선택할 수 있다.

 

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

19.3 재귀에 숨겨진 비용

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

이 함수는 숫자 n을 받아 0까지 거꾸로 세며 각 숫자를 출력한다. 새로운 자료 구조를 만들지는 않지만, 함수를 호출 스택에 N개 만큼 저장해야 한다. 즉, 재귀 함수가 최대 O(N)의 공간을 차지한다.

 

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

 

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

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

function recurse(n) {
	while(n >= 0) {
	  console.log(n);
		n--;
	} 
}

이러한 점을 고려하면 퀴 정렬이 왜 O(logN)인 이유가 있다. 퀵 정렬은 재귀 호출을 O(logN)번 수행하므로, 정점에서 호출 스택 크기가 log(N)이기 때문이다.

 

함수를 재귀로 구현할 수 있을 때는 재귀가 갖는 문제점 대비 이득을 따져봐야 한다.

 

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

 

다시 말하자면 재귀를 부정하는게 아니라 매 상황마다 각 알고리즘의 장단점을 골고루 저울질 해야 한다는 뜻이다.

19.4 마무리

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