빅오 표기법(Big O notation)

빅오 표기법이란?

알고리즘의 효율성을 파악하기 위한 표기법으로써

알고리즘의 가장 최악의 경우를 고려하여 표기한다.

이 때 중요하게 보아야 하는 것은 지수이며, 계수는 무시한다. 상수의 경우 1로 표기한다.

ex) f(5955) -> O(1)

ex) f(2n) -> O(n)

ex) f(3n²) -> O(n²)

---

시간 복잡도 (Time Complexity)

• 시간복잡도는 알고리즘이 실행되는 동안 소요되는 시간을 측정하는 방법이다.
• 하지만 절대적인 시간을 측정하게 된다면 알고리즘을 실행하는 컴퓨터 하드웨어의 성능에 따라 차이가 생기므로
  연산량으로 시간복잡도를 측정한다.
• 시간복잡도는 보통 BigO 표기법으로 표기하며,
• 알고리즘의 최악의 경우를 상정하여 시간복잡도를 측정한다.

function addUpTo(n) {
    let total = 0;
    for (i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

 

위 코드의 시간 복잡도: O(n)

O(n)인 이유: n을 입력하면 1부터 n까지 연산해야하는 코드이므로 O(n)의 시간복잡도를 가진다.

 

---

 

function addUpTo(n) {
    return (n * (n + 1)/2);
}

위 코드의 시간 복잡도: O(1)

O(1)인 이유: n이 아무리 크더라도 상수값의 연산을 하므로 O(1)

(곱하기, 더하기, 나누기의 세가지 연산밖에 없으므로 간추려서 1이라고 한다.) 

 

---

 

function printAllpairs(n) {
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j ++) {
            console.log(i, j);
        }
    }
}

위 코드의 시간 복잡도: O(n²)

O(n²)인 이유: 반복문이 이중으로 중첩되어 있다. 이 경우 n마다 n번만큼 연산이 반복된다.

예를들어 위 코드의 파라미터 n에 3을 넣으면 총 9개의 console.log(i, j)가 찍히게 된다.

 

---

공간 복잡도 (Space Complexity)

공간복잡도는 알고리즘이 실행되는 동안 필요로 하는 메모리 공간을 측정하는 방법이다.

주로 알고리즘이 실행되는 동안 사용되는 추가적인 공간(변수, 배열, 데이터구조) 등을 고려하며,

파라미터의 n은 무시하고 오로지 알고리즘에 필요한 추가 공간만을 고려한다.

공간복잡도 또한 빅오 표기법으로 표기할 수 있다.

 

 

자바스크립트의 공간복잡도

• 불리언, 숫자, undefined, null은 상수 공간(constant space) / 간단히 하면 1개의 공간을 차지한다.
• 배열, 객체등은 O(n)의 공간을 차지한다.

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

위 코드의 공간 복잡도: O(n)

O(n)인 이유: newArr는 배열이며, arr의 크기와 비례하게 증가하므로 O(N)의 공간복잡도를 가진다.

 

---

 

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

const b = sum([1, 2, 3, 4, 5])

// O(1) 공간
console.log(b);

위 코드의 공간 복잡도: O(1)

O(1)인 이유: 파라미터로 배열을 받는 것과는 별개로, 내부에서는 배열을 저장하지 않고 숫자형이라는 상수형 공간만 사용하고 있다.