빅 오 표기법을 계산하는 방법?

Big O 표기법이란 무엇입니까?

Big O 표기법은 인수가 특정 값이나 무한대로 향하는 경향이 있을 때 함수의 제한 동작을 설명하는 수학적 표기법입니다. src

시간복잡도란?

시간 복잡도는 입력 길이의 함수로 알고리즘을 실행하는 데 걸리는 시간으로 정의됩니다.

아래 표에서 다양한 복잡도 시간을 확인할 수 있습니다.


시간 복잡도 이름
복잡성


끊임없는
오(1)

선의
에)

대수
O(로그 n)

이차
오(n²)

지수
오(2^n)

계승
에!)


공통 함수의 큰 표기법here을 볼 수 있습니다.

시간 복잡도에 대한 좋은 시각을 얻기 위해 이러한 상수의 그래픽 계산기를 사용할 수 있습니다. desmos 그래프 계산기를 사용할 수 있습니다. 간단한 데모를 만들었습니다. 확인하실 수 있습니다here.

알고리즘의 시간 복잡도를 계산하여 확장성과 성능에 대한 정보를 얻을 수 있습니다. 2차 또는 지수적 시간 복잡도에서 수행되는 알고리즘이 있는 경우 최적화를 시도하여 확장할 수 있습니다.

루프의 시간 복잡성에 대한 몇 가지 예를 볼 수 있습니다.

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

}

//O(n*m) --> O(n²)
for(let i=0; i<n; i++){
    for(let j=0; j<m; j++){

    }
}

let s = 0; //O(1)


//O(log(n))
for(let i=n; i>0; i=i/2){

}

desmos 계산기에서 그래프 예제를 확인하면 알고리즘이 어떻게 확장될 수 있는지 더 잘 이해할 수 있습니다. 그리고 이것은 유일한 알고리즘과 관련이 없으며 이 지식을 데이터베이스 쿼리에 사용할 수 있습니다. 예를 들어 인덱스가 정의되지 않은 테이블이 있는 경우 검색 시간 복잡도는 O(n)입니다. 하지만 인덱스를 정의하면 검색의 시간 복잡도는 O(log(n))가 됩니다. 인덱스를 만들 때 테이블의 모든 행을 확인할 필요가 없기 때문입니다. 대신 인덱스를 기반으로 찾아 분할 정복 알고리즘을 사용할 수 있습니다.

계산

알고리즘의 빅오 표기법을 어떻게 계산할 수 있는지 봅시다.

let sum = (n) => {
    let res = 0 // O(1)
    for(let i=0; i<n; i++){ //O(n)
        res += i // O(1)
    }
    return res // O(1)
}

따라서 모든 시간 복잡도를 합하면 O(n)이 됩니다.

sum = 1 + n*1 + 1 = n + 2 => O(n)

n*log(n) 시간 복잡성에 대한 예

let sumDivide = (n) => {
    let res = 0 // O(1)
    for(let i=n; i<n; i/2){ //O(log(n))
        for(let j=n; j<n; j/2){ //O(n)
            res += j // O(1)
        }
    }
    return res // O(1)
}

sumDivide = 1 + log(n)*n*1 + 1 = n*log(n) + 2 => O(n*log(n))