아무 말

\(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 \) 에 대해 \..

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