[점근적 표기] #2 O-표기, Ω-표기

\(O\)-표기

\(O\)-표기는 가장 흔하게 볼 수 있는 점근적 표기법입니다. 간단하게 말해 \(O\)-표기는 함수의 점근적 상한을 결정짓는 표기입니다. \(c g(n)\)이 특정한 상수 \(n_0\)보다 큰 모든 \(n\)에 대해 \(f(n)\)보다 크기만 하다면, \(f(n)\)을 \(O(g(n))\)으로 표기할 수 있습니다. \(O\)-표기가 많이 사용되는 이유 또한 이러한 특성 때문인데, Problem Solving을 할 경우에 특정 문제에 대해 적용한 풀이가 문제에서 주어진 시간제한을 넘어서는지 아닌지를 나타낼 수 있기 때문입니다. \(O\)-표기를 함수의 집합으로 나타내면 아래와 같습니다.

\(O(g(n))\ =\ \{ f(n)\) : 모든 \( n \geqslant n_0 \) 에 대해 \( 0\leqslant f(n) \leqslant cg(n)\) 인 양의 상수 \( c,\ n_0\) 이 존재한다.\(\}\)

 

\(\Omega\)-표기

\(\Omega\)-표기는 함수의 점근적 하한을 결정짓는 표기입니다. \(c g(n)\)이 특정한 상수 \(n_0\)보다 큰 모든 \(n\)에 대해 \(f(n)\)보다 작기만 하다면, \(f(n)\)을 \(\Omega (g(n))\)으로 표기할 수 있습니다. \(\Omega\)-표기를 집합으로 나타내면 아래와 같습니다.

\(\Omega(g(n))\ =\ \{ f(n)\) : 모든 \( n \geqslant n_0 \) 에 대해 \( 0\leqslant cg(n) \leqslant f(n)\) 인 양의 상수 \( c,\ n_0\) 이 존재한다.\(\}\)

(b)는 \(O\)-표기를, (c)는 \(\Omega\)-표기에 대해 표현이 성립하는 함수를 시각적으로 보여주고 있다. ref. Introduction to Algorithms 3rd Edition

위 그림은 직관적으로 \(O\)-표기와 \(\Omega\)-표기를 사용할 수 있는 함수를 보여주고 있습니다.(b)에서\(n\)이 \(n_0\) 이상일 때, \(f(n)\)의 값은 절대로 \(cg(n)\)을 넘어가지 않습니다. 반면에 (c)에서는 \(f(n)\)의 값이 절대로 \(cg(n)\)보다 작지 않다는 것을 알 수 있습니다.

 

\(\Theta\)-표기, \(O\)-표기, \(\Omega\)-표기 사이의 관계

\(\Theta\)-표기는 함수의 점근적 상한과 하한을 동시에 표현합니다. 즉, \(f(n)\in O(g(n))\)이면서, \(f(n) \in \Omega(g(n))\) 이면, \(\Theta(g(n)) \in f(n)\) 입니다. 이러한 관계는 역도 성립합니다. \(\Theta(g(n)) \in f(n)\)라면, \(f(n)\in O(g(n))\)와 \(f(n) \in \Omega(g(n))\)가 성립하게 됩니다.