Space Complexity - 공간 복잡도

두 가지 요소 - 보조 공간과 입력 공간

 

보조 공간 : 알고리즘이 실행을 위해 사용하는 임시 공간

입력 공간 : 입력의 크기를 고려하여 실행 시 필요한 공간

 

공간 복잡성을 평가하기 위해 보조 공간만 사용되는 시나리오가 있지만 이 글에서는 전체 공간(보조 및 입력)을 사용할 것이다.

 

공간 복잡도는 메모리 또는 데이터 저장의 사용을 평가하기 위해 고려하는 사항이다.

알고리즘은 몇 가지 작업을 수행하기 위해 메모리를 사용해야 한다.

 

• 프로그램 명령어 저장 (컴파일러 => 런타임)
• 실행 (예: 함수 호출, 점프 문)
• 데이터 저장(예: 상수 및 변수 값)

여기서 저장된 변수 데이터는 주요 고려 사항이다.

시간 복잡도와 마찬가지로 공간 복잡도는 일반적으로 빅오 표기법으로 표시된다.

 

예시 1)

function add(n1, n2) {
  const sum = n1 + n2;
  return sum;
}

add 함수는 n1, n2, sum 총 3개의 변수를 위한 메모리를 요구한다.

이때의 메모리는 입력 공간과 관련이 있다.

 

또한 이 함수는 함수 호출과 반환문을 위한 메모리도 요구하는데,

이때의 메모리는 보조 공간과 관련이 있다.

 

입력하는 값과 상관없이,
메모리는 항상 같은 공간을 필요로한다.

 

이때의 공간 복잡도는 O(1)이다.

 

예시 2)

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

이 예시의 경우에는 arr의 길이에 비례하여 필요한 메모리 공간이 달라지게 된다.

 

때문에 공간 복잡도는 O(n)이다.