[Algorithms] 빅오 표기법

빅오 표기법에서 `n`은 입력의 개수를 나타낸다. `n이 무한으로 접근할 때 무슨 일이 일어날까?`

이미지 출처 - https://medium.com/better-programming/understanding-big-o-notation-c3245b8112dc

O(1)

`O(1)`은 입력 공간에 대해 변하지 않으며, 그래서 이를 상수 시간이라고 한다. 배열에 있는 항목을 인덱스를 사용해 접근하는 경우가 `O(1)`의 예이다. 

 

O(n)

`O(n)`은 선형 시간이고 최악의 경우에 n번의 연산을 수행해야 하는 알고리즘에 적용된다. 

// NOTE: O(n) 알고리즘
function bigO1(n) {
    for (let i = 0; i < n; i++) {
        console.log(i);
    }
}

// NOTE: O(n^2) 알고리즘(Quadratic)
function bigO2(n) {
    for (let i = 0; i < n; i++) {
        console.log(i);
    	for(let j = i; j < n; j++) {
            console.log(j);
        }
    }
}

 

O(log n)

`O(log n)`의 시간 복잡도의 효율은 큰 입력이 있을 경우에 분명하다.(높은 효율의 알고리즘)

// NOTE: O(log n)의 알고리즘
function bigO3(n) {
    for (let i = 2; i <= n; i = i*2) {
        console.log(i);
    }
}

 

빅오 표기법 규칙

알고리즘의 시간 복잡도를 `f(n)`이라고 한다면 `n`은 입력의 개수를 나타낸다. 알고리즘 분석의 목표는 f(n)을 계산함으로써 알고리즘의 효율성을 이해하는 것이다. 근데 f(n)을 계산하는 것은 어렵기 때문에 빅오 표기법은 개발자들이 f(n)에 관해 계산하는데 도움이 되는 기본적인 규칙을 제공한다. 

 

계수 법칙

입력 크기와 연관되지 않는 상수를 모두 무시하면 되는 법칙이다.  빅오에서 입력 크기가 클 때 계수를 무시할 수 있다. 

상수 k > 0, f(n)이 O(g(n))이면, kf(n)은 O(g(n))이다

1000f(n)과 f(n)이 모두 동일한 O(f(n))이라는 말이다.  예를 보자.

// NOTE: 시간 복잡도 O(n)
function bigOn(n) {
    let count = 0;
    for(let i=0; i<n; i++){
        count += 1;
    }
    return count;
}

위 코드는 `f(n) = n`이다. count에 숫자를 n번 더하기 때문이다. 따라서 시간 복잡도는 `O(n)`이다.  아래 예제도 보자.

// NOTE: 시간 복잡도 O(n)
function bigOn(n) {
    let count = 0;
    for(let i=0; i < n*5; i++){
        count += 1;
    }
    return count;
}

위 코드는 `f(n) = 5n`이다. 0부터 5n까지 실행하기 때문이다. 하지만 두 코드의 시간 복잡도는 동일한 `O(n)`이다. 왜냐하면, n이 무한대에 가까워질 때 4개의 연산이 추가적으로 존재한다고 해서 달라지는 것이 없기 때문이다. 빅오 표기법에서 모든 상수는 무시해도 된다.

// NOTE: 시간 복잡도 O(n)
function bigOn(n) {
    let count = 0;
    for(let i=0; i < n*5; i++){
        count += 1;
    }
    count+=3;
    return count;
}

위 코드는 `f(n) = n+1`이지만, 여전히 `O(n)`이다. 추가된 연산이 입력 n에 영향을 받지 않기 때문이다.

 

합의 법칙

시간 복잡도를 더할 수 있다는 법칙이다. 다만, 합의 법칙을 적용한 다음 계수 법칙을 적용해야 한다.

f(n)이 O(h(n))이고 g(n)이 O(p(n))이라면, f(n) + g(n)은 O(h(n) +p(n))이다.

아래 예제 또한 각 루프의 시간 복잡도가 개별적으로 계산된 다음 더해져야 한다.

// NOTE: O(n) = n
function bigOn(n) {
    for (let i=0; i=n; i++) {
        count += 1;
    }
	for (let i=0; i < n*5; i++) {
        count += 1;
    }
    return count;
}

첫 번째 루프는 `f(n) = n`이고 두 번째 루프는 `f(n) = 5n`이다. 이를 더하면, `f(n) = 6n`이다. 하지만 계수 법칙을 적용해서 `f(n) = n`이므로 `O(n) = n`이 된다. 

 

곱의 법칙

f(n)이 O(h(n))이고 g(n)이 O(p(n))이면, f(n)g(n)은 O(h(n)p(n))이다.

바로 예제를 보자.

function bigOn(n) {
    for(let i=0; i=n; i++) {
        count += 1;
    	for(let i=0; i < n*5; i++) {
            count += 1;
        }
    }
    return count;
}

위 코드는 `f(n)=5n*n`이다. 내부 루프에 의해 5n번 실행되고, 내부 루프가 외부 루프에 의해 n번 실행되기 때문이다. 따라서 결과는 `5n^2`번 연산이 일어나고 계수 법칙을 적용하면 `O(n)=n^2`이 된다.

 

다항 법칙

f(n)이 k차 다항식이면, f(n)은 O(n^k)이다.

아래는 2차 시간 복잡도를 지닌 for 루프 예다.

function bigOn(n) {
    for(let i=0; i=n*n; i++) {
        count += 1;
    }
    return count;
}

위 코드는 `f(n)=n^2`이다. 왜냐하면 `count += 1`의 구문이 `n*n`회 실행되기 때문이다.