빅오 표기법

• 알고리즘의 “효율성”을 평가하기 위한 분석법.

• 시간 복잡도(실행시간)와 공간 복잡도(실행공간)로 이루어진다.

공간복잡도는 주로 코드가 저장되어진 메모리를 뜻하며, 시간복잡도는 계산횟수(operation time)를 뜻한다.

​ 예를 들어 A라는 함수를 호출하면 인자의 제곱만큼 연산이 발생한다고 하자. 이 때, 매번 인자가 바뀔 때 마다 '289번', '8281번' 등으로 지칭할 수도 있지만 조금 더 편하게 인자의 제곱만큼 연산이 발생한다고 설명할 수도 있다. 이러한 표기법을 Big-O 표기법이라 하며, 위의 예시를 Big-O 표기법으로 표현하면 아래와 같다.

여기서 N은 매우 큰 숫자를 의미한다.
N이 999,999,999,999,999,... 이라고 했을 때, 이렇게 큰 숫자에서 n과 2n, n/2 등은 크게 차이가 없다. 그러므로 O(n)이라고 했을 때, 해당 함수는 n만큼이 아니라 n에 비례한다. 로 생각하면 Xn, n + @, n / 2 등을 모두 O(n)으로 표기한다는 것을 쉽게 이해할 수 있다.

간단한 코드를 통한 예시

// O(1)
function a() {
    return a;
}

// O(n)
function b(n) {
    for(let i = 0; i < n; i++) {
        //
    }
}

// O(n^2)
function c(n) {
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            //
        }
    }
}