빅오 표기법(big-O notation)

2022. 11. 18.

by. JJo 😊

빅오 표기법(big-O notation)

빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다. 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다. 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.

시간 복잡도 : 속도에 해당하는 알고리즘의 수행시간 분석결과

공간 복잡도 : 메모리 사용량에 대한 분석결과

👉 일반적으로는 중요도는 실행속도가 메모리 사용량보다 중요하다.

👉 알고리즘의 성능을 판단하는 데 있어서 중요한 것은 '최악의 경우'이다.

O(1)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘. 데이터가 증가해도 성능에 영향을 거의 미치지 않는다. O(1)을 상수 시간이라고 부른다. n의 값이 얼마나 크든 상관 없다. ex) stack의 push, pop

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

O(n)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘. 데이터가 10배가 되면, 처리 시간도 10배가 된다. 선형 탐색 알고리즘이 대표적이다. ex) 1중 for문

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

O(log n)

연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (log의 지수는 항상 2)

ex) binary search 알고리즘, tree 형태 자료구조 탐색, 이진트리

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

O(N log N)

O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태 ex) 퀵 / 병합 / 힙 정렬

O(n²)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다. 이중 루프(n² matrix)가 대표적이다. ex) 2중 For 문, 삽입/거품/선택 정렬

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);
            }
        }
    }
}

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다. ex) fibonacci 수열