빅 오 표기법 Big-Oh Notation

빅 오 표기법이란 알고리즘의 효율성을 표기해주는 표기법,

데이터의 수 n에 따른 연산 횟수를 구하는 함수 T(n)에서 가장 영향이 부분을 따지는 것,

데이터의 수 n의 증가에 따른 연산횟수의 증가 형태를 나타내는 표기법이다.

 

예를 들자면 T(n) = 5n^3+3n+2의 빅오는 n^3이다. 이는 n이 커질수록 n^3가 차지하는 비율이 커지므로 T(n)의 변화 정도가 n^3의 형태를 띠므로 그렇다.

 

위의 말을 간단히 정리하면, T(n)이 다항식으로 표현 된 경우, 최고차 항의 차수가 빅 오가 된다.

예를 들어 T(n) = 5n^3+3n+2은 O(n^3)이 된다.

위 예시에서 5n^3은 n^3이 됐는데, 최고차항의 계수는 빅오에서 중요치 않다, 왜냐하면 5n^3이나 n^3이나 n이 증가할수록 값이 증가하는 추세가 촉진되는 것은 같기 때문이다. 빅오에서 중요한것은 연산 횟수의 증가 형태이다.

 

빅 오 표기법에는 대표적인 빅오가 몇가지 있다.

- O(1)

    상수형 빅-오이다. 데이터 수에 상관없이 연산 횟수가 고정인 알고리즘 유형이다.

- O(logn)

    로그형 빅-오이다. 데이터수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 알고리즘이다.

- O(n)

    선형 빅-오이다. 데이터의 수와 연산횟수가 비례하는 알고리즘 유형이다.

- O(nlogn)

    선형로그형 빅-오이다. 데이터의 수가 두 배로 늘어날 때, 연산 횟수는 두배를 조금 넘게 증가한다.

- O(2^n)

    지수형 빅-오이다. 데이터의 수가 증가할 수록 엄청난 연산 횟수의 증가를 보여서 사용하기 힘들다.