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

점근적 표기

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

 

\(\Theta\)-표기

 

\(\Theta\)-표기는 다음을 의미합니다.

\(\Theta \left( g \left( n \right) \right) \ =\ \{ f \left( n\right) \ : \)모든\( n \geqslant n_0\)에 대해 \( 0 \leqslant c_{1}g\left( n \right) \leqslant f \left( n\right) \leqslant 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 \Theta(g(n))\) 이다." 가 됩니다. 즉, \(n\)을 무한히 크게 했을 때, \( 0 \leqslant c_{1}g\left( n \right) \leqslant f \left( n\right) \leqslant c_{2}g\left( n \right)\) 를 만족하면, \(f(n)\)을 \(\Theta(g(n))\)로 표현할 수 있다는 것을 의미합니다.

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

위의 그림을 보면 \(f(n)\) 이 \(c_1 g(n)\)와 \(c_2 g(n)\) 사이에 끼어있는 것을 볼 수 있습니다.

 

 

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

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