[ 자료구조 ] 빅오 표기법(Big-Oh Notation)

T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.

$$T(n)=5n^3+3n^2+2n+1$$

$$O(n^3)$$

대표적인 빅-오

$$O(1)$$

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

연산 횟수가 데이터 수에 상관없이 3회 진행되는 $O(1)$이라 한다.

$$O(logn)$$

로그형 빅-오라 한다. 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮다. 로그 밑이 얼마냐에 따라서 차이가 나긴 하지만, 알고리즘 성능 관점에서는 미미하기 때문에, 대부분의 경우에 있어서 무시가 된다.

$$O(nlogn)$$

선형로그형 빅-오라 한다. 데이터의 수가 두배로 늘 때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘이다.

외에도, $O(n^2)$와 $O(n^3)$가 있다.

빅-오 표기들의 대소 관계는 아래와 같다.

$O(1)$ < $O(logn)$ < $O(n)$ < $O(nlogn)$ < $O(n^2)$

$$n^2 =$$