Big O Notation(빅오 표기법) #5

💡 **[Colt Steele](https://www.udemy.com/user/coltsteele/) 의 JavaScript Algorithms and Data Structures Masterclass의 강의를 참고하여 정리한 글입니다.**

5. Big O의 공간 복잡성

위의 페이지는 알고리즘에 따른 실행 속도 즉, 런타임과 관련하여 비교하였고 이를 시간 복잡도라고 한다. 입력의 크기가 증가함에 따라 달라지는 알고리즘의 런타임을 분석한 것이다.

이번에 배울 공간 복잡도는 바로 입력 데이터가 차지하는 공간에 따른 분석을 말한다.

즉, 입력 데이터가 차지하는 메모리의 양과 관련된 비교이다.

JavaScript 에서의 공간 복잡도에 대한 기본적인 규칙이 존재한다.

JS에서의 공간 복잡도 규칙

1. 가장 기본적인 데이터 타입 (boolean, number, undefined, null) 은 일정한 공간을 차지한다.

즉, 입력의 크기는 중요하지 않고 데이터가 1 이건 1000 이건 일정한 공간을 차지한다는 것이다.

1. String 타입은 O(n) 의 표기법을 지닌다. 문자열의 길이를 n 이 결정하기 때문.
2. 참조형 데이터 타입 즉, array 타입과 object 타입은 일반적으로 O(n) 이다.
   여기서의 n 은 배열의 길이나 키 값의 수를 의미한다.

예제를 통한 비교

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

시간 복잡도

시간복잡도의 관점에서 봤을 때, for 문으로 인한 루프 그리고 해당 for문은 입력값인 arr 의 길이(n)에 따라 변화하므로 O(n) 이라고 할 수 있다.

공간 복잡도

공간복잡도의 초점에서 공간(메모리)를 차지하는 영억은 어디가 해당되는 것인가를 살펴보는 것이 중요하다.

1. 먼저, sumA() 는 total = 0 에서 변수 total에 상수 0을 할당한다.(메모리를 차지한다.)
2. 두번째로 for문 내에 let i = 0 에서 변수 i에 상수 0을 할당한다.(메모리를 차지한다.)

입력인 arr 의 길이에 따라 시간 복잡도는 변화할 수 있겠으나 sumA() 함수 내에 메모리를 할당하여 차지하게 되는 영역은 2가지에 불과하며 return 되는 값 total은 결국 상수(number) 이다.

JS에서의 공간 복잡도 규칙에서 보았듯 number 의 공간복잡도는 일정하다. 즉 O(n) 이다.

다른 함수 sumB()를 살펴보자.

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

시간 복잡도

시간 복잡도의 관점에서 입력되는 값 arr의 길이에 따라 for 문의 루프 길이가 변화게 되고 이는 곧 O(n) 을 의미한다.

공간 복잡도

sumA() 함수의 공간 복잡도와 동일하게 공간(메모리)을 차지하는 영역을 살펴본다.

1. let newArr = []; 에서 배열이 변수 newArr 에 할당된다.
2. for 문 내에서 let i = 0; 으로 변수 i에 0이 할당된다.
3. for 문 내에서 변수 newArr 이 입력 값인 arr 의 길이에 따라 비례하여 반복실행되며 newArr에 push 되어 메모리의 크기가 커진다.

1.~2.를 통해서 +2가 되며, 3. 에서 입력 값인 배열 arr의 길이에 따라 newArr의 공간의 크기가 비례하여 변화하는 것에 따라, n+2 임을 알 수 있다.

즉, 빅오 표현식의 단순화에 따라 O(n) 이다.