2-2 빅오표기법 - 공간복잡도

시간복잡도가아니다

입력값에따라 코드의 실행시간의 증가율을 본 시간복잡도와 다르게

사용되는 공간 즉 메모리를 얼마나 사용하는지를 확인할 수 있다.

 

 

공간복잡도 = 보조 공간 복잡도

불변공간 : (booleans , numbers , undefined, null) -> 입력의 크기와는 상관없이 숫자가 1이든 1000이든 모두 불변 공간

booleans이 true이든 false이든 똑같은 공간을차지한다.

번외가 존재함 

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

ex) n의 문자열의 길이고 50이 입력으로들어온다면  문자열의 길이가 1인 문자열보다 50배 더많은 공간을 차지한다. 

그외에도 레퍼런스타입,배열,객체 또한 o(n)공간이 필요하다. ex) 배열의 길이 객체의 키 갯수.

 

코드를보자

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

 

배열안의 모든 아이템을 합하는 sum()함수가있다.

 

시간이 아닌 공간에 집중해보자

total = 0;

 

let i = 0;

 입력으로 들어온 arr의 크기가  차지하는 공간과는 상관없이 

두가지의 변수가 할당된 것만큼 n이 1000이더라도 100만일수 있고 5000이더라도 10만일수있다

 .

새로운 변수를 만들지않고 상수공간 즉 O(1) 일정한 공간을 차지한다.

 

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

 

배열의 길이에 비례해서 새로운 배열에 저장되는 아이템의 갯수가 늘어남.

배열의 길이가 10이면 10개의 아이템을 배열에 추가함. 

차지하는 공간이 배열의 크기와 비례해서 커진다.

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