시간 복잡도 (빅오, 빅오메가, 빅세타)

시간 복잡도란?

시간 복잡도는 특정 알고리즘이 얼마나 빠르게 수행이되는지 표현하기 위해 사용된다.

즉, 시간복잡도는 쉽게 말해서 알고리즘의 실행 시간을 말한다.

시간 복잡도의 종류

빅오 (big-O) 표기법

• 시간의 상한 (최악의 경우)
• 해당 알고리즘은 big-O 보다 더 오래 걸릴 수 없다.

 

빅오메가 (big-Omega) 표기법

• 시간의 하한 (최선의 경우)
• 해당 알고리즘은 big-Omega 보다 더 빠를 수 없다.

 

빅세타 (big-theta) 표기법

• 평균적인 경우, 딱 맞는 수행 시간
• big-O 와 big-Omega 를 하나로 합쳐 표현한것과 같다.
  • 예를들어, 수행시간이 빅오가 N, 빅오메가가 N 이라면, 빅세타도 N 이다. (아래 그림 참조)

빅세타 참고용 그림(출처: https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation)

가장 많이 쓰이는 표기법

보통은 빅오와 빅세타를 많이 사용하지만, 가장 많이 사용하는 표기법은 빅오 표기법이다.

• 현실에서는 항상 최악의 경우를 생각해야 하기 때문에, 흔히 빅오 표기법을 많이 사용한다.

 

반면, 최선의 경우(big-Omega)의 경우는 별로 쓸모가 없다. 대부분의 알고리즘이 특정한 데이터를 삽입해서 O(1)이 나오게 할 수 있기 때문이다.

• 예를들어, 이미 정렬이 완료된 데이터들을 정렬 알고리즘으로 정렬하는 경우

---

참고

가장 많이 사용하는 빅오에 대한 상세 내용은 아래 링크를 확인한다.

• 2020/02/16 - [Algorithm] - 알고리즘의 시간 복잡도 - 빅오(O) 표기법

알고리즘의 시간 복잡도 - 빅오(O) 표기법