[TIL] 자료구조 - 빅 오 표기법

※ 빅 오 표기법?

- 빅 오 표기법은 알고리즘의 효율성을 표시하는 표기법으로 한 알고리즘을 다른 알고리즘과 비교하여 표현하는 것이 가능하다.

 

복잡도가 n인 알고리즘에 빅 오 표기법을 적용한 표

위 그림에서 x축은 복잡도 n을, y축은 필요한 일의 양이나 메모리를 의미한다.

다른 알고리즘들이 이 표에서 어떤 위치에 있는지에 따라 복잡도 n인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있다. 만약 다른 알고리즘이 복잡도 n인 알고리즘의 아래에 있을 경우 같은 일을 처리하는데 시간이 덜 들기 때문에 빠른 알고리즘이라고 한다. 하지만 복잡도 n인 알고리즘의 위에 있다면, 더 느린 알고리즘이다.

 

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

- Θ (세타 복잡도): 비교 대상 그래프가 일치하면 비교대상 알고리즘과 같다.

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

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

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