점근 표기법: 두 판 사이의 차이

* 대문자 [[O]] 표기법

* 소문자 [[o]] 표기법

* 대문자 오메가 표기법 ([[Ω]]) 표기법

* 소문자 오메가 표기법 ([[ω]]) 표기법

<math>\frac{f(x)}{g(x)}</math>가 <math>\ x \rightarrow \infty</math>일 때의 [[함수의 극한|극한]]값이 [[상수]]로 수렴한다면, 즉

<math>x>x_0</math>인 모든 실수 ''x''에 대하여 <math>|f(x)| \le \; M |g(x)|</math>가 성립하는 <math>\; x_0,\ \;M>0</math>가 존재한다면

:<math>\qquad x \rightarrow \infty</math>일 때 <math>f(x) \,</math>는 <math>O(g(x)) \,</math>라고 한다. <math>f(x) = O(g(x))</math>라고 표기하기도 하며, 혹은 <math>O(g(x))</math>를 해당 <math>f(x)</math>의 집합으로 정의하기도 한다.

이때 <math>f(x)는 = O(g(x)), 혹은\mbox{ or } O(x<sup>^4)</supmath>)이 된다. 증명은 다음과 같다.

:''<math>x''가 1보다> 클1</math>일 때 <math> |6x^4 - 2x^3 + 5| \le 6x^4 + 2x^3 + 5 \,</math>

:<math> |6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4 \,</math> (''x''<supmath>x^3</sup> < ''x''<sup>^4</supmath>와 같은 방법)

:<math> |6x^4 - 2x^3 + 5| \le 13x^4 \,</math>

:<math> |6x^4 - 2x^3 + 5| \le 13 \,|x^4 |. \,</math>

어떤 함수가 <math>O(x)</math>이면 <math>O(x<sup>^2)</supmath>)이므로 <math>O(x) = O(x^2)</math>로 표기할 수는 있지만, <math>O(x^2) = O(x)</math>와 같이 쓰는 것은 잘못된 표기이다. 이 때, 등호 표기는 일반적인 표기법과 다르게 사용된 [[기호의 남용]]으로 볼 수 있다.

또한 Õ 표기법은 대문자 O 표기법의 일종으로 <math>\tilde{O} (g(n))</math>는 <math> O(g(n) \, \log^k g(n))</math>(k는 임의의 상수)를 의미한다. 이 표기법은 함수의 로그 증가 비율을 무시하는 의미를 가지고 있다.