공간 복잡도

😋 공간 복잡도

이전에는 시간 복잡도를 보았다. 하지만 이제는 메모리 즉 공간 복잡도를 살펴보겠다.

😁 O(1) space

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

여기서 공간 복잡도는 2개가 나온다.

1. total=0;
2. i=0
   이렇게 2개가 나온다. 이 숫자가 100, 100000, 1000000000000 인지는 중요하지 않고 공간을 차지한다는 것이 중요하다.
   즉 입력의 크기와는 상관없이 공간 2개를 차지한다는 것이 똑같다.
   이럴경우 O(1)space 라고 표현한다.

😃 O(n) space

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

이 함수는 입력받은 배열의 요소를 2배씩 늘려 리턴해주는 함수이다.
여기서는 배열의 크기에 따라 차지하는 공간의 크기가 커진다.
즉 n개의 배열 요소의 크기게 따라 차지하는 공간의 크기가 n개로 커지는 것이다.
이럴경우 O(n) space 라고 표현한다.