[Algorithms] Big O 공간 복잡도

이전글

Big O 알고리즘 in JS - 1

---

Space Complexity (공간 복잡도)

• Time complextiy
  how can we analyze the runtime of an algorithm as the size of the Inputs increases?
  입력이 커질수록 알고리즘의 실행속도가 얼마나 빠르게 실행되는지에 대해 분석한 것이 시간 복잡도이다.

• Space complexity
  how much additional memory do we need to allocate in order to run the code in our algorithm?
  알고리즘이 입력 크기로 차지하는 공간에 어던 일이 일어나는지 확인한다.
  차지하는 메모리의 양인 공간에 초점을 맞추어야 한다.

---

What about the inputs?

• 기본적으로 넘어가야 하는 것들 :
  하나는 무한대에 가까워질수록 입력 자체의 크기가 커진다는 것이다.
  그래서 N은 성장하게된다. 우리는 그 부분을 무시한다.

• auxiliary space complexity to refer to space required by the algorithm,
  not including space taken up by the inputs.
  보조 공간 복잡도는 입력되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간을 의미한다.

이 포스트에서 중요한 것은 알고리즘 그 자체이다.
그렇기 때문에 n이 커질수록 입력이 커진다는 것을 가정하고,
입력이 차지하는 공간은 상관하지 않고 알고리즘 자체가 어떤 영향을 주는지 확인한다.

Unless otherwise noted, when we talk about space complexity,
technically we’ll be talking about auxiliary space complexity.
별도로 언급하지 않는 한, 해당 글에서 공간 복잡도를 언급했을 때
사실상 보조 공간 복잡도를 말하는 것이다.

📁 Space Complexity in JS

Rules of Thumb

• Most primitives (booleans, numbers, undefined, null) are constant space
  booleans, 숫자, undefined, null 은 자바스크립트에서 모두 불변의 공간이다.
  그렇기 때문에 입력의 크기와는 상관 없이, 숫자가 1이든 1000이든 모두 불변 공간이라고 여긴다.
  booleans 이 사실이든 거짓이든 똑같은 공간을 차지한다.

• String require $O(n)$ space (where n is the string length)
  문자열은 $O(n)$ 공간이 필요하다.
  만약 n이 문자열의 길이이고 50자인 입력이 있다면
  그 문자열은 길이가 1자인 문자열보다 50배 더 많은 공간을 차지하게 된다.

• Reference types are generally $O(n)$, where n is the length (for array) or the number of keys (for objects)
  reference 타입, 배열과 객체도 대부분 $O(n)$이라고 생각한다.
  n은 배열의 길이이거나 객체의 키 갯수일 수 있다.
  정확히는 길이가 아니지만, 만약 배열 길이가 4 이고 또 하나가 2 라면
  긴 배열이 짧은 배열보다 2배 더 많은 공간을 차지한다.

Example $O(1)$ space 📝

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

시간이 아닌 공간에 집중하면 공간을 차지할 것들을 생각해야 한다.

• 우선 배열의 길이와는 상관 없이 total 이라는 변수가 하나있다.
  (let total = 0; ← one number)
• 루프를 반복하면서 두 번째 배정은 i = 0 이다.
  (i = 0 ← another number)

이렇게 차지하는 공간은 끝이다. 이미 공간은 할당되어 있다.
그렇기 때문에 배열에 크기와는 상관 없이, n이 커져도 10만일 수도 있고, 50만일 수도 있다.

두 변수밖에 없기 때문에 입력의 크기가 차지하는 공간과는 아무 상관이 없다.
이 두 변수는 어떠한 상황에도 존재한다.
배열의 길이에 따라서 새로운 변수를 더하는 것도 아니고 total 변수에 더 하는 것이다.
(새로운 변수는 만들지 않는다.)

그렇다면 결국 상수 공간이 있다는 것이며 $O(1)$ 공간이 된다.

Example $O(n)$ space 📝

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

double([1,2,3]) 실행 결과
(3) [2, 4, 6] 0: 2 1: 4 2: 6 length: 3

[1,2,3] 배열을 입력하면 아이템이 3개의 값이 두배로 커져 있는 배열로 돌아온다.
주의할 점은 이것이 새로운 배열이라는 것이다.

우선 새로운 배열을 만들고 (let newArr = [];)
첫 번재 배열 값들을 루프로 접근해서 곱한 후에 (for (let i = 0; i < arr.length; i++))
새로운 배열에 push 하고 새 배열이 돌아온다. (newArr.push(2 * arr[i]);)

double(arr) 의 공간 분석
입력된 배열의 길이가 10이면 새로운 배열에 저장되는 아이템이 열 개가 된다.
입력된 배열의 길이가 70이면 아이템이 70개가 되어 그것을 리턴한다.
그렇기 때문에 차지하는 공간은 입력된 배열의 크기와 비례해서 커지게 된다.
return newArr; ← n numbers

이것을 n+1 이나 n+2 를 쓰는 대신에 최대한 단순하게 $O(n)$으로 단순화할 수 있다.

Example 공간 복잡도 📝

💡 아래 함수에 대한 공간 복잡도를 구하기

function logUPTo(n) {
    for (var i = 1; i <= n; i++) {
        console.log(i);
    }
}

답 : $O(1)$

function logAtMost10(n) {
    for (var i = 1; i <= Math.min(n, 10); i++) {
        console.log(i);
    }
}

답 : $O(1)$

function onlyElementsAtEvenIndex(array) {
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            newArray[i / 2] = array[i];
        }
    }
    return newArray;
}

답 : $O(n)$

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

답 : $O(n)$

🌞 정보 : 공부 기록용 블로그입니다. 오타나 내용 오류가 있을 경우 알려주시면 감사하겠습니다.