알고리즘의 시간복잡도를 계산하기 위해, 가장 많이 사용되는 방법 중 하나가 바로 빅오 표기법이다.

이번에는 빅오표기법을 통해 시간복잡도를 어떻게 계산하는지, 어떤 빅오가 효율적인지 공부했다.

빅오 표기법(Big-Oh Notation)

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

대표적인 빅-오

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

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

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

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

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

어떤 빅-오가 효율적일지 대소관계를 표현해보자면, 아래와 같다.

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