공간 복잡도

1. booleans, numbers, undefined, null은 자바스크립트에서 불변공간이다.

그렇기 때문에 입력의 크기와는 상관없이 숫자가 1이든 100000이든 모두 불변의 공간으로 여긴다.

 

2.  문자열은 o(n)의 공간이 필요하다.

3. reference타입, 배열과 객체도 대부분 o(n)이다. n은 배열의 길이나 객체의 키 갯수일 수 있다.

 

예시1)

function sum(arr) {
	let total = 0; // 첫번째 숫자 공간 할당
    for (let i = 0; i < arr.length; i++) { // i = 0; 두번째 숫자 공간 할당
    	total += arr[i];
    }
	return total;
}

이 함수는 배열을 받아 그 배열안에 있는 모든 값을 합하는 함수이다.

 

total과 i 두가지가 할당되는것이고 total의 값이 바뀌지만 이것은 시간복잡도가 아닌 공간 복잡도이므로 해당 값이 10만이든 1만이든 상관없다. 

 

또한 새로운 변수를 만들지 않는다.

 

그렇다면 결국 상수공간이 있다는것이다.

o(1)의 공간을 차지한다.

입력의 크기와는 상관없이 항상 같다.

 

예시2)

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

}

이 함수는 배열을 받아 각 아이템의 값이 2배로 되어 새로운 배열을 리턴한다.

배열의 크기가 늘어나서 무한대에 가까워질수록 공간복잡도가 어떻게 될까?

 

먼저 어떤 상황에도 새로운 배열을 만드는 newArr 선언이 있다.

하지만 처음에 만든 이 빈배열은 전달받은 배열의 길이에 비례해서 길어지는것과 비교하면 중요하지 않다.

길이가 10인 배열을 전달 받게 되면 새로운 배열도 10개가 되고 50개를 전달받으면 50개가 된다.

 

그렇기 때문에 차지하는 공간은 입력된 배열의 크기와 비례해서 커지게 된다.

즉 o(n)의 공간을 차지한다.