[Javascript] 빅오 표기법 정리 및 예제

알고리즘의 시간 복잡도를 f(n)이라고 표현했을 때, n은 입력의 개수를 나타내고 f(n)time은 필요한 시간을 나타내고 f(n)space는 필요한 공간(추가적인 메모리)을 나타냅니다. 알고리즘 분석의 목표는 f(n)을 계산함으로써 알고리즘의 효율성을 이해하는 것입니다. 하지만 f(n)을 계산하는 것은 어려울 수 있습니다. 이런 계산을 하는데 도움이 되는 빅오 표기법의 기본적인 규칙이 있습니다.

 

 

[계수 법칙]

계수 법칙은 가장 이해하기 쉬운 법칙입니다. 단순히 입력 크기와 연관되지 않은 상수를 전부 무시하면 됩니다. 빅오에서 입력 크기가 클 때 계수를 무시할 수 있습니다.

 

상수 K>0인 경우 f(n)이 O(g(n))이면 kf(n)은 O(g(n))이다.

즉, 5f(n)과 f(n)이 모두 동일한 O(f(n))이라는 빅오 표기법을 지님을 의미 합니다.

 

 

아래 세 개의 함수는 모두 O(n)의 빅오 표기법을 지닙니다. 간단히 말해서 n이 무한대 또는 아주 큰 수에 가까워질 때 연산이 추가적으로 존재한다고 해서 달라지는 것은 없기 때문입니다. n이 충분히 클 때 아래의 코드가 n번 수행될 수 있습니다. 빅오 표기법에서는 모든 상수는 무시하셔도 됩니다.

// 아래의 코드는 f(n)=n입니다.
// count에 숫자를 n번 더하기 때문입니다. 
function a(n) {
    let count = 0;

    for (let i = 0; i < n; i++) {
        count += n;
    }

    return count;
}

// 아래의 코드는 f(n)=5n입니다. 
// 0부터 5n까지 실행하기 때문입니다.
function b(n) {
    let count = 0;

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

    return count;
}

// 아래의 코드는 f(n)=n+1입니다.
// 마지막 연산으로 인해 +1이 추가됐습니다.
function c(n) {
    let count = 0;

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

    count += 3;

    return count;
}

 

 

 

[합의 법칙]

합의 법칙은 쉽게 이해할 수 있습니다. 시간 복잡도를 말 그대로 더할 수 있다는 것입니다. 합의 법칙은 결괏값인 시간 복잡도가 두 개의 다른 시간 복잡도의 합이라면 결괏값인 빅오 표기법 역시 두 개의 다른 빅오 표기법의 합이라는 것을 의미합니다. 합의 법칙을 적용한 다음 계수 법칙을 적용해야 한다는 점을 주의하셔야 합니다.

 

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

 

 

코드에 있는 주석을 보시다시피 하나는 f(n)=n, 다른 하나는 f(n)=5n에 해당합니다. 이로 인해 결괏값은 6n이 됩니다. 하지만, 계수 법칙을 적용하면 최종적인 결과는 O(n)=n이 됩니다.

function a(n) {
    let count = 0;
    
    for (let i = 0; i < n; i++) {
    	// f(n)=n
        count += 1; 
    }

    for (let i = 0; i < 5*n; i++) {
    	// f(n)=5n
        count += 1; 
    }

    return count;
}

 

 

 

[곱의 법칙]

두 개의 다른 시간 복잡도를 곱할 때 빅오 표기법 역시 곱해진다는 것을 의미합니다. 곱의 법칙을 적용한 다음 계수 법칙을 적용해야 한다는 점을 주의하셔야 합니다.

 

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

 

 

아래의 예는 f(n)=5n*n입니다. 내부 루프에 의해 5n번 실행되고 내부 루프가 외부 루프에 의해 n번 실행되기 때문입니다. 따라서 결과는 5n²번 연산이 일어나게 됩니다. 계수 법칙을 적용하면 결과는 O(n)=n² 이 됩니다.

function a(n) {
    let count = 0;
    
    for (let i = 0; i < n; i++) {
    	// n
        count += 1;
        for (let j = 0; j < 5*n; j++) {
            // 5n^2
            count += 1;
        }
    }

    return count;
}

 

 

 

[다항 법칙]

다항 법칙은 다항 시간 복잡도가 동일한 다항 차수를 지닌 빅오 표기법을 지님을 나타냅니다.

 

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

 

 

아래의 코드는 n*n으로 실행되기 때문에 f(n)=n²입니다. 

function a(n) {
    let count = 0;

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

    return count;
}

 

 

 

[연습 문제]

다음 각 함수의 시간 복잡도를 계산해 봅시다.

function example1(n) {
    for (let i=0; i<n*1000; i++) {
        for(let j=0; j<n*20; j++) {
            console.log(i+j);
        }
    }
}

function example2(n) {
    for (let i=0; i<n; i++) {
        for (let j=0; j<n; j++) {
            for (let k=0; k<n; k++) {
                for( let l=0; l<10; l++) {
                    console.log(i+j+k+length);
                }
            }
        }
    }
}

function example3(n) {
    for (let i=0; i<1000; i++) {
        console.log('hi');
    }
}

function example4(n) {
    for (let i=0; i<n*10; i++) {
        console.log(n);
    }
}

function example5(n) {
    for (let i=0; i<n; i*2) {
        console.log(n);
    }
}

function example6(n) {
    while(true) {
        console.log(n);
    }
}

 

문제	정답	풀이
example1	O(n²)	두 개의 중첩 루프가 있어서고, n 앞의 상수는 무시하시면 됩니다.
example2	O(n^3)	네 개의 중첩 루프가 있지만, 마지막 루프는 10까지 밖에 실행되지 않아서 3승까지입니다.
example3	O(1)	상수 복잡도입니다. 함수는 0부터 1000까지 실행되긴 하지만 n과 연관이 없습니다.
example4	O(n)	선형 복잡도입니다. 함수는 0부터 10n까지 실행되고 상수는 빅오에서 무시됩니다.
example5	O(log2n)	로그 복잡도입니다. 주어진 n에 대해 log2n번만 실행됩니다. i가 증가할 때 다른 예에서처럼 i에 1을 더하는 것이 아니라 2를 곱하기 때문입니다.
example6	O(∞)	무한 루프입니다. 함수가 종료되지 않습니다.

 

 

 

Reference

자바스크립트로 하는 자료 구조와 알고리즘

[Javascript] 시간 복잡도 정리 및 예제