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

빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정합니다. 빅오 표기법에서 n은 입력의 개수를 나타냅니다. 알고리즘을 구현할 때 빅오 표기법이 해당 알고리즘이 얼마나 효율적인지 나타내기 때문에 빅오 표기법은 중요합니다. 빅오와 관련된 질문으로 "n이 무한으로 접근할 때 무슨 일이 일어날까?"가 있을 수 있습니다.

 

일반적인 빅오 복잡도

 

 

[시간복잡도의 예]

1. O(1) - Constant Time

O(1)은 입력 공간에 대해 변하지 않습니다. 따라서 O(1)을 상수 시간이라고 부릅니다. n의 값이 얼마나 크든 상관이 없습니다. O(1) 알고리즘의 예로 배열에 있는 항목을 인덱스를 사용해 접근하는 경우가 있습니다.

function exampleConstant(arr) {
    console.log(arr[0]);
}

 

 

2. O(n) - Linear Time

O(n)은 선형 시간이고 최악의 경우에 n번의 연산을 수행해야 하는 알고리즘에 적용됩니다. O(n)의 예로 0부터 n-1까지의 숫자를 출력하는 경우가 있습니다.

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

 

 

3. O(n²) - Quadratic Time

O(n)과 마찬가지로 O(n²)은 2차 시간입니다. O(n^3)은 3차 시간이겠죠? 2차 시간과 3차 시간 복잡도의 예는 다음과 같습니다.

function exampleQuadratic(n) {
    for (let i = 0; i < n; i++) {
        console.log(i); 
        for (let j = i; j < n; j++) {
            console.log(j);
        }
    }
}

function exampleCubic(n) {
    for (let i = 0; i < n; i++) {
        console.log(i);
        for (let j = i; j < n; j++) {
            console.log(j);
            for (let k = j; k < n; k++) {
                console.log(k);
            }
        }
    }
}

 

 

4. O(log n) - Log

로그 시간 복잡도를 지닌 알고리즘의 예는 2의 2승부터 n승까지의 항목들을 출력하는 경우가 있습니다. 예를 들어 exampleLogarithmic(10)은 다음 결과를 출력합니다.

2,4,8,16,32,64

로그 시간 복잡도의 효율은 백만 개의 항목과 같이 큰 입력이 있는 경우에 분명합니다. n이 100만이라고 하더라도 exampleLog는 log2(1,000,000)= 19.931.. 이기 때문에 단지 19개의 항목만을 출력합니다. 로그 시간 복잡도를 구현한 코드는 아래와 같습니다.

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

* 혹시라도 log를 너무 오랜만에 접해 저처럼 까먹으신 분들을 위해 기억 하는데 도움이 되고자 적습니다.

 

 

[시간 복잡도 비교]

O(1) < O(log n) < O(n) < O(N log n) < O(n²) < O(2^n)
n의 값이 커지면 커질수록, 시간복잡도가 복잡한 알고리즘은 수행 시간이 급격하게 길어지게 됩니다.

 

References
https://mathbang.net/595

https://joshuajangblog.files.wordpress.com/2016/09/1.jpg?w=638
자바스크립트로 하는 자료구조와 알고리즘(배세민)