[점근적 표기] #1 Θ-표기

점근적 표기

점근적 표기는 함수의 증가 양상을 점근적으로 표현하는 방법입니다. 점근적인 증가 양상을 나타내기 때문에, 함수의 각 변수에 대한 발산 속도가 가장 큰 항을 제외한 나머지와 모든 상수를 무시하여 나타낼 수 있습니다.

 

$\mathrm{\Theta }$-표기

 

$\mathrm{\Theta }$-표기는 다음을 의미합니다.

$\mathrm{\Theta }\left(g\left(n\right)\right)=\{f\left(n\right):$모든$n⩾n_0$에 대해 $0⩽c_{1}g\left(n\right)⩽f\left(n\right)⩽c_{2}g\left(n\right)$ 인 양의 상수$c_1$,$c_2$, $n_0$이 존재한다.$\}$

 

말로 풀어서 쓰면, "충분히 큰 $n$에 대해서 $f(n)$이 $c_{1}g(n)$과 $c_{2}g(n)$ 사이에 있는 (끼이는) 양의 상수 $c_1$ 과 $c_2$가 존재한다면, $f(n)\in \mathrm{\Theta }(g(n))$ 이다." 가 됩니다. 즉, $n$을 무한히 크게 했을 때, $0⩽c_{1}g\left(n\right)⩽f\left(n\right)⩽c_{2}g\left(n\right)$ 를 만족하면, $f(n)$을 $\mathrm{\Theta }(g(n))$로 표현할 수 있다는 것을 의미합니다.

pic 1. $\mathrm{\Theta }$ - 표기를 이용할 수있는 함수 $f(n)$ ref. Introduction to Algorithms 3rd Edition

위의 그림을 보면 $f(n)$ 이 $c_{1}g(n)$와 $c_{2}g(n)$ 사이에 끼어있는 것을 볼 수 있습니다.

 

 

점근적으로 엄밀한 한계(Asympotically tight bound)

$n⩾n_0$에 대해서만 $f(n)\in \mathrm{\Theta }(g(n))$이 성립합니다. 이는 상수 인자 $n$에 의해 $f(n)\in \mathrm{\Theta }(g(n))$인 범위가 결정된다고 할 수 있습니다. 이때, $g(n)$을 $f(n)$의 점근적으로 엄밀한 한계라고 합니다.