빅 오 표기법

- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다. 

- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.

- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.

- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

 

 

※ 시간 복잡도를 다룰 때 등호(=)는 같다는 뜻이 아니라 속한다(∈)에 가깝다. 

예를 들어 아래 식이 참인지 판별하려면 2n이 n과 같거나 더 빠른 범위에 포함되는지를 확인하면 된다. 시간복잡도를 다룰 때 상수는 무시하므로 2n은 n과 같다. 고로 아래 식은 참이다.

 

 

 

 

n^3/4이 nlogn보다 같거나 빠르다는 뜻이다. 입력값이 작은 경우는 고려하지 않고 계산하기 쉬운 큰 값을 넣어 맞는지 확인해 보자

n = 1000, 로그의 밑을 10으로 놓고 계산하면

좌항은 10000, 우항은 3000이므로 좌항이 더 크다. 즉 n^3/4가 nlogn보다 더 시간복잡도가 큰 느린 알고리즘이므로 위 식은 거짓이다.

 

 

상수는 무시하고, 최고차항만을 고려하므로 좌항과 우항은 같다. 곧 위 식은 참이다.