The Big Oh Notation

개요

주어진 어떤 알고리즘에 대한 시간 복잡도는 가능한 문제 인스턴스 크기에 대한 함수들이며, 이들을 정밀하게 다루는 것은 매우 어렵다. 따라서 이들을 단순화하여 분석하는 것이 매우 좋은 방식 중 하나이다. 예를 들어, $T(n)=12754n^2+4353n+834lo{g}_2^n+13546$와 같은 시간 복잡도 함수는 정밀하게 분석하기란 매우 어렵지만, 시간 복잡도가 n에 대해 2차적으로 증가한다는 관찰이 틀렸다고 볼 수는 없다.

“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다. 빅 오 표기는 곱셈 상수들 간의 차이를 무시한다. 함수 $f(n)=2n$과 $g(n)=n$은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.

• $f(n)=O(g(n))$는 $c\cdot g(n)$가 $f(n)$에 대한 상한임을 의미한다.
  • 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 $f(n)\le c\cdot g(n)$가 성립한다.
• $f(n)=\mathrm{\Omega }(g(n))$는 $c\cdot g(n)$가 $f(n)$에 대한 하한임을 의미한다.
  • 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 $f(n)\ge c\cdot g(n)$가 성립한다.
• $f(n)=O(g(n))$는 $c_1\cdot g(n)$가 $f(n)$에 대한 상한이고 $c_2\cdot g(n)$가 $f(n)$에 대한 하한임을 의미한다.
  • 따라서 어떤 상수 c₁, c₂가 존재하여 충분히 큰 모든 n에 대하여 $c_2\cdot g(n)\le f(n)\le c_1\cdot g(n)$가 성립한다.

이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n₀가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다.