[Algorithm] 공간 복잡도

yeols·2023년 9월 5일
0

Algorithm

목록 보기
3/16
post-thumbnail

공간 복잡도

이 전까지는 시간과 관련하여 알고리즘들이 얼마나 빠르게 실행하는지에대해 문제를 바라 보았다. 이걸 바로 시간 복잡도라고 한다.

이제는 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지 하는지에 대해서 알아보자.

여전히 Big O표기법을 사용할 수 있지만 이제는 공간, 사용되는 메모리에 주목 하겠다.

공간 복잡도는 입력 되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간을 의미한다.


기본적인 규칙

  • Boolean, Number, undefined, null은 javascript에서 모두 불면의 공간이다.
    입력 크기와 상관없이 숫자가 1이든 1000이든 모두 같은 공간이라고 여긴다.
  • String은 O(n) 공간이 필요하다.
    만약 n이 문자열의 길이라면, 50자가 입력되었다면 1자인 문자열보다 50배 더 많은 공간을 차지하게 된다.
  • reference, array, object도 대부분 O(n)이다.

공간 복잡도 Big O 예시 :

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

let total = 0;이라는 변수는 Number이고
let i = 0;이라는 변수도 Number이다.
공간은 루프와 상관없이 이미 할당 되어 있다.
때문에 배열의 크기와 상관 없이, n이 커져도 공간 복잡도는 고정이다.
그래서 위 함수는 공간 복잡도O(1) 이다.

function double(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i]);
  }
  return newArr;
}

double([1, 2, 3]);

double(arr)함수는 arr에 담긴 값을 2를 곱해서 돌려주는 함수이다.
새로운 배열을 만들고 루프 내에서 새로운 배열에 push하기에 n이 커질수록 공간도 비례해서 커지기 때문에 O(n)이 된다.

profile
흠..

0개의 댓글