개요
주어진 어떤 알고리즘에 대한 시간 복잡도는 가능한 문제 인스턴스 크기에 대한 함수들이며, 이들을 정밀하게 다루는 것은 매우 어렵다. 따라서 이들을 단순화하여 분석하는 것이 매우 좋은 방식 중 하나이다. 예를 들어, [math]\displaystyle{ T(n) = 12754n^2 + 4353n + 834log_2^n + 13546 }[/math]와 같은 시간 복잡도 함수는 정밀하게 분석하기란 매우 어렵지만, 시간 복잡도가 n에 대해 2차적으로 증가한다는 관찰이 틀렸다고 볼 수는 없다.
“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다. 빅 오 표기는 곱셈 상수들 간의 차이를 무시한다. 함수 [math]\displaystyle{ f(n) = 2n }[/math]과 [math]\displaystyle{ g(n) = n }[/math]은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.
- [math]\displaystyle{ f(n) = O(g(n)) }[/math]는 [math]\displaystyle{ c\cdot g(n) }[/math]가 [math]\displaystyle{ f(n) }[/math]에 대한 상한임을 의미한다.
- 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 [math]\displaystyle{ f(n) \le c \cdot g(n) }[/math]가 성립한다.
- [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]는 [math]\displaystyle{ c\cdot g(n) }[/math]가 [math]\displaystyle{ f(n) }[/math]에 대한 하한임을 의미한다.
- 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 [math]\displaystyle{ f(n) \ge c \cdot g(n) }[/math]가 성립한다.
- [math]\displaystyle{ f(n) = O(g(n)) }[/math]는 [math]\displaystyle{ c_1\cdot g(n) }[/math]가 [math]\displaystyle{ f(n) }[/math]에 대한 상한이고 [math]\displaystyle{ c_2\cdot g(n) }[/math]가 [math]\displaystyle{ f(n) }[/math]에 대한 하한임을 의미한다.
- 따라서 어떤 상수 c1, c2가 존재하여 충분히 큰 모든 n에 대하여 [math]\displaystyle{ c_2 \cdot g(n) \le f(n) \le c_1 \cdot g(n) }[/math]가 성립한다.
이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n0가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다.