[개념] BigO 표기법

빅오표기법이란?

우리는 알고리즘 문제를 풀던 코드를 짜던 무엇이 가장 효율적인지 시간상 짧게 걸리는지를 확인 할 필요가 있다.

( 성능과 직접적으로 연결되는 부분이기 때문 )

 

빅오표기법

상수시간 알고리즘(Constant Time Algorithm)

 - 가장 이상적인 알고리즘으로써 실행되는 횟수가 상수값으로 나타나서 그 횟수만큼만 실행을 하기때문에 Input되는 데이터가 어떻든 같은 시간안에 처리하게 된다.

const array = [1, 2, 3, 4, 5]
const fnc = (array) => {
	console.log(array[0])
}

만약 아래 코드와 같이 출력하는 값이 여러개로 늘어난다하더라도 상수는 제외하고 나타내기 때문에 결국은 O(1)으로 표기된다.

const array = [1, 2, 3, 4, 5]
const fnc = (array) => {
	console.log(array[0]) // 1번
    console.log(array[0]) // 2번
    console.log(array[0]) // 3번
}

 

O(N)

 - 위의 상수시간 알고리즘과 동일하게 상수는 표현하지 않고 Input의 크기에 정비례하여 step이 증가하는 알고리즘

const array = [1, 2, 3, 4, 5, 6]
const func = (array) => {
	for (i of array) {
    	console.log(i)
    }
}

 

O(N^2) ... 

 - step의 증가량이 굉장히 비효율적으로 증가하는 알고리즘으로써 이중반복문 이상의 것들이 이러한 모습을 나타낸다.

const array = [1, 2, 3, 4, 5, 6]
const func = (array) => {
	for (i of array) {
    	for(j of array) {
        console.log(j + i)
        }
    }
}

 

O(log N)

- 이진검색 알고리즘에서 보였던 모습을 나타낸 것으로 정렬된 input에서만 사용할 수 있는 제한적이지만 효율적인 알고리즘

이진검색 알고리즘에서 input의 크기가 2배가 되어도 step의 수는 1번이 늘어나는 것을 생각하면 된다.