[알고리즘]BIG-O 표기법

BIG-O notation 이란?

• 알고리즘의 성능을 분석하기 위해서 사용한다.
• 시간복잡도와 공간복잡도에 대해 이해할 수 있다.
• 빅오는 연산의 수를 따지기 때문에 하드웨어에 영향을 받지 않는다.
  (내 컴퓨터 vs 슈퍼 컴퓨터)
• 산수와 변수의 배정은 상수이다

시간복잡도에서의 BIG O

• 입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식
• 산수와 변수의 배정은 상수이다
• 배열의 첫번째 아이템이나 인덱스를 사용하면 다 똑같은 시간이 걸리고,
  객체를 다루고 데이터에 접근하기 위한 키가 있다면 걸리는 시간은 상수이다.
• 리스트에 있는 데이터를 루프로 처리할 때 0에서 n까지 간다면 n이 커질 수록
  루프가 반복되는 횟수가 늘어난다.
• 중첩루프가 있다면 제곱이 된다.

O(1)

function AddUpTo(num) {
    return num * (num + 1) / 2;
}

var time1 = performance.now();
AddUpTo(1000000000);
var time2 = performance.now();

console.log(`걸린 시간: ${(time2 - time1) / 1000}`); // 0.00009

O(N)

    let total = 0;
    for(let i = 1; i <= num; i++){
        total += i
    }
    return total
}

var t1 = performance.now();
AddUpTo(1000000000);
var t2 = performance.now();
console.log(`걸린 시간: ${(t2 - t1) / 1000}`) // 0.901

공간복잡도에서의 BIG O

• boolean, nunber, undefined, null은 모두 불변의 공간
• string은 O(n)의 공간을 필요로 한다.
• 배열과 객체 또한 O(n)의 공간을 필요로 한다.

O(1)

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

O(n)

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)
• 메소드
  • Object.keys - O(N)
  • Object.values - O(N)
  • Object.entries - O(N)
  • hasOwnProperty - O(N)

배열의 성능평가

• 데이터가 정렬되어 있어서 연산속도가 느리다.
• 접근하는 시간은 상수, 객체와 같다.
• 입력과 제거는 어디에 입력을 할지 어디에 제거를 할지에 달려있다.
• 메소드
  • push - O(1)
  • pop - O(1)
  • shift - O(n)
  • unShift - O(n)
    등등..