복잡도 함수 표기법

빅($O$) 표기법

정의 : 점근적 상한

어떤 함수 $g(n)$이 $O(f(n))$에 속한다는 말은 $n$이 커짐에 따라 $cf(n)$보다는 작은 값을 가지게 된다는 의미

따라서 $g(n)$은 $cf(n)$에 비해 좋다(빠르다)라고 할 수 있다.

즉, 어떤 알고리즘의 시간복잡도가 $O(f(n))$이라는 것은 입력 $n$에 대해 알고리즘의 수행시간이 늦어도 $cf(n)$은 된다는 말이다. (점근적 상한)

알고리즘의 수행시간이 $cf(n)$보다 느릴 수 없다는 말과 같다.

 

오메가($\Omega$) 표기법

정의 : 점근적 하한

어떤 함수 $g(n)$이 $\Omega (f(n))$에 속한 다는 말은 $n$이 커짐에 따라 $cf(n)$보다는 큰 값을 가지게 된다는 의미

따라서 $g(n)$은 $cf(n)$에 비해 나쁘다(느리다)라고 할 수 있다.

즉, 어떤 알고리즘의 시간복잡도가 $\Omega (f(n))$이라는 것은 입력 $n$에 대해 알고리즘의 수행시간이 아무리 빨라도 $cf(n)$이라는 말이다. (점근적 하한)

알고리즘의 수행시간이 $cf(n)$보다 빠를 수 없다는 말과 같다.

 

세타($\Theta$) 표기법

정의 : $f(n)$에 대해서 $\Theta(f(n))=O(f(n)) \cap  \Omega (f(n))$

$g(n) \in \Theta  (f(n))$이라면 $g(n)$은 $f(n)$의 차수라고 한다.

 

작은($o$) 표기법

정의 : $f(n)$에 대해 $(g(n)) \cap o(f(n))$일 때 모든 양의 실수 $c$에 대해,

$n \geq N$인 모든 $n$에 대해 $0 \leq g(n) \leq c \times f(n)$이 성립하는 음이 아닌 정수 N이 존재하는 경우

 

큰 ($O$)와의 차이점

큰 $O$는 $c>0$을 만족하는 특정한 실수 $c$에 대해 하나만 성립하여도 된다.

작은 $o$는 $c>0$인 모든 실수 $c$에 대해 성립하여야 한다.

 

$(g(n))\in o(f(n))$ 라는 것은 $g(n)$이 $cf(n)$보다 훨씬 낫다(빠르다)는 의미

 

$g(n)$과 $f(n)$의 시간 복잡도 비교는 극한값을 이용해 판정할 수 있다.