Study/정리
시간 복잡도
별천랑
2021. 4. 2. 13:42
최선의 경우를 바라되, 최악의 경우를 대비하라.
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
평균인 세타 표기를 하면 가장 정확하고 좋겠지만 평가하기가 까다롭다. 일반적으로 가장 중요한 경우는 최악의 경우 입니다. 최소한의 기준점이 되기 때문이죠. 최악의 상황을 상정하면 더 나쁜 상황은 있을 수 없는 거니까요. 상황에 대한 설명이 주어지지 않았다면, 최악의 상황을 상정해야 하는 겁니다. - 한 권으로 그리는 컴퓨터과학 로드맵 중에서
- 아래는 대표적인 Big-O의 복잡도를 나타내는 표이다.
