시간 복잡도를 표현하는 표기 방식이 총 3가지가 있습니다. (빅오, 빅 오메가, 빅 세타)
시간 복잡도를 나타내는 경우도 3가지 있습니다. (최상, 최악, 평균 / 그 중에서 최악이 제일 많이 쓰이고요)
그런데 빅오 표기법으로 최악의 경우를 나타낸다고 합니다.
제가 궁금한 것은 무조건 빅오는 최악, 빅 오메가는 최상, 빅 세타는 평균을 표현하도록 정의되어 있나요?
제가 가지고 있는 자료에서 순차탐색의 시간 복잡도를 설명하는 부분이 있는데
최선의 경우 : 찾고자 하는 숫자가 맨 앞에 있는 경우 : O(1)
최악의 경우 : 찾고자 하는 숫자가 맨 뒤에 있는 경우 : O(n)
평균적인 경우 : (n+1)/2 : O(n)
이렇게 기술되어 있어요. 각 경우에 따른 빅오 표기법을 보여주고 있는데
꼭 빅오 표기법이 최악의 경우를 말하는 것 같지 않는데요?
제가 어느 부분을 잘못 이해하고 있는 걸까요?
