[자료구조] 빅 오 표기법

빅 오 표기법

 

: 알고리즘의 효율성을 표시하는 표기법

: 빅 오 표기법을 사용하면 어떤 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능하다.

 

 

: 위 그래프는 복잡도가  n인 알고리즘에 빅 오 표기법을 적용한 결과이다.

: x축은 복잡도 n, y축은 필요한 일의 양이나 메모리를 의미

 

: 다른 알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도  n인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수  있다.

: 다른 알고리즘이 복잡도  n인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘

: 반대로, 복잡도  n인 알고리즘의 위에 있다면, 더 느린 알고리즘

 

알고리즘 간 관계 표현

- O (빅 오)

: 비교 대상인 그래프가 일치 혹은 아래에 있을 때.  비교 대상인 다른 알고리즘과 같거나 더 빠르다.

: same or faste

- o (리틀 오)

: 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.

:faster but not the same

 

- Ω (빅 오메가) 

: 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

: same or slower

- ω (리틀 오메가) 

: 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

: slower but not the same

 

- θ (세타)

: 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.

: same rate

 

[출처: 자바로 구현하고 배우는 자료 구조]

 

자바로 구현하고 배우는 자료구조