공간복잡도

공간복잡도는 알고리즘이 실행되는 동안 사용되는 메모리의 양을 입력 크기(n)에 따라 Big-O 표기법으로 표현한 것 입니다.

공간복잡도 = 입력 공간 + 추가 공간

입력 공간: 함수 인자로 받은 배열, 입력데이터 등을 의미합니다.
추가 공간: 알고리즘 내부에서 새로 선언하는 변수나 ,배열, 재귀 호출, 스택 등을 의미합니다.

공간복잡도의 복잡성은 추가 공간 을 얼마나 사용하냐를 중심으로 분석합니다.

공간복잡도 표

chatGPT를 통해 정리한 공간복잡도 표는 다음과 같습니다.

공간복잡도	예시
O(1)	단일 변수, 포인터만 사용
O(n)	배열, 해시맵, Set, 단일 For문을 이용한 저장 등 n개의 저장에 사용
O(log n)	이진 탐색의 재귀 호출 깊이
O(n²)	2차원 배열, 그래프 인접 행렬
O(n!)	순열 저장 시 사용, 최악의 케이스

공간복잡도 알아보기

O(1)

O(1)은 시간복잡도에서 처럼 단순히 1개의 변수 혹은 상수로만 처리 될 경우 입니다.

예시

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

total 변수 1개만 사용하였기 때문에 입력 크기와 무관하게 고정된 공간을 사용합니다.

O(n)

입력 크기만큼 새 배열을 생성할 경우 입니다. 입력이 n이면 공간도도 O(n)이게 됩니다.

예시

function copyArray(arr: number[]): number[] {
  return [...arr];
}

새로운 배열을 생성하여 입력하고 리턴하기에 입력크기 n만큼 공간을 차지하는 모습을 볼 수 있습니다.

O(log n)

입력이 줄어드는 과정(이진 탐색 등)에서 로그 깊이만큼 공간을 사용하기에 O(log n)이라는 복잡도를 가지게됩니다.

예시

function binarySearch(arr: number[], k: number): boolean {
  const sortArr = arr.sort((a, b) => a - b);

  let low = 0;
  let high = sortArr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === k) return true;
    if (arr[mid] < k) low = mid + 1;
    else high = mid - 1;
  }

  return false;
}

시간복잡도에서 사용한 이진 탐색 예시입니다. low, high라는 O(1)의 값 외에 mid라는 값을 저장합니다. 그리고 해당 mid값은 탐색이 진행됨에 따라 log n 번 만큼 생성되게 됩니다. 이는 곧 O(log n)의 복잡도를 가진다고 볼 수 있습니다.

O(n²)

2차원 배열이나 그래프 인접 행렬 등 2차원 구조를 저장할 경우 O(n²)라고 볼 수 있습니다.

예시

function newArray(num: number): number[][] {
  const newNums: number[][] = [];
  for (let i = 0; i < num; i++) {
    newNums[i] = []; // ← 초기화 먼저
    for (let j = 0; j < num; j++) {
      newNums[i].push(j);
    }
  }
  return newNums;
}

위와 같이 n번 순회하는 for문 속 새로운 n번만큼 순회하여 2차원 배열을 생성하는 코드는 n * n 만큼 공간을 차지하기에 O(n²) 라고 볼 수 있습니다.

O(n!)

팩토리얼을 의미하기도 하는 n!은 입력 n개로 만들 수 있는 모든 순열/배열 순서 조합을 생성하거나 저장할 때 사용하는 공간입니다.
가령 5라는 입력값이 있다면 5 x 4 x 3 x 2 x 1이 되어 120번의 생성 혹은 저장이라는 어마어마한 수치가 나오게됩니다.

예시

// chatGPT 참고... 추후에 직접 구현해볼 예정.
function permute(arr: number[]): number[][] {
  const result: number[][] = [];
  
  const getPermutation = (path: number[], rest: number[]) => {
    if(rest.length === 0) {
      result.push([...path]);
      return;
    }
    for(let i = 0; i < rest.length; i++) {
      const next = rest[i];
      const nextRest = [...rest.slice(0, i), ...rest.slice(i + 1)];
      getPermutation([...path, next], nextRest);
    }
  }
  
  return result;
}

앞서 시간복잡도에서 gpt와 함께 구현한 순열 구하기 문제입니다.
함수를 재귀적으로 호출함으로써 n! 만큼 반복하게됩니다.

여담

공간복잡도는 앞서 시간복잡도를 한번 익히고 나서 봐서 그런지 생각보다 이해하기 쉬웠습니다. 다만 팩토리얼의 경우 여전히 직접 구현하면 난해함을 겪을꺼 같아 더욱 깊이있는 공부와 수학적?지식도 필요할 것 같습니다.