점근 표기법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 로봇이 더함: he:סימון אסימפטוטי |
잔글 <math> 태그 적용 |
||
2번째 줄:
점근 표기법에는 크게 다음과 같은 표기법이 있다.
* 대문자 [[O]] 표기법
* 소문자 [[o]] 표기법
* 대문자 오메가
* 소문자 오메가
* 대문자 세타([[Θ]]) 표기법
== 대문자 O 표기법 ==
=== 정의 ===
<math>\frac{f(x)}{g(x)}</math>가 <math>\ x \rightarrow \infty</math>일 때의 [[함수의 극한|극한]]값이 [[상수]]로 수렴한다면, 즉
<math>x>x_0</math>인 모든 실수 ''x''에 대하여 <math>|f(x)| \le
=== 예 ===
17번째 줄:
:<math> f(x) = 6x^4 -2x^3 +5 \,</math>
:<math> g(x) = x^4. \,</math>
이때 <math>f(x)
:
:<math> |6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4
:<math> |6x^4 - 2x^3 + 5| \le 13x^4
:<math> |6x^4 - 2x^3 + 5| \le 13
=== 표기법 문제 ===
<math>f(x) = O(g(x))</math>라는 표현에서, [[등호]]는 원래의 등호와는 다른 의미를 가진다. 예를 들어,
어떤 함수가 <math>O(x)</math>이면 <math>O(x
이러한 문제를 방지하기 위해, <math>O(g(x))</math>를 원래 정의에서 해당하는 함수들의 집합으로 정의하는 경우도 많이 사용된다. 이러한 경우 <math>f(x) \in O(g(x))</math>과 같이 표기할 수 있고, 이것은 기호의 원래 정의와 잘 맞아 떨어진다.
61번째 줄:
|}
또한 Õ 표기법은 대문자 O 표기법의 일종으로 <math>\tilde{O} (g(n))</math>는 <math>
[[분류:계산 복잡도 이론]]
|