점근 표기법 문서 원본 보기

{{위키데이터 속성 추적}}
'''점근 표기법'''(漸近 表記法, {{llang|en|asymptotic notation}})은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 [[수론]]과 [[해석학 (수학)|해석학]]의 방법이다. [[알고리즘]]의 [[복잡도 이론|복잡도]]를 단순화할 때나 [[무한급수]]의 뒷부분을 간소화할 때 쓰인다.

대표적으로 다음의 다섯 가지 표기법이 있다.
* 대문자 [[O]] 표기법
* 소문자 [[o]] 표기법 
* 대문자 오메가([[Ω]]) 표기법 
* 소문자 오메가([[ω]]) 표기법 
* 대문자 세타([[Θ]]) 표기법 
이 중 압도적으로 많이 쓰이는 것이 대문자 O 표기법으로, [[에드문트 란다우|란다우]] 표기법이라고도 한다. 

특히, [[알고리즘]]의 [[복잡도 이론|복잡도]]를 나타내는 용어로는 "[[계산 복잡도 이론]]" 또는 "[[시간복잡도]]"로 대문자 [[O]] 표기법이 일반적으로 사용된다.

== 대문자 O 표기법 (Big-O notation)==
=== 정의 ===
함수 ''<math>f(x)</math>'', ''<math>g(x)</math>''에 대해 ''<math>f(x)</math>''가 ''<math>O(g(x))</math>''라는 것은 '''상한 점근'''에 관한 다음의 동치인 정의와 같다.
* <math>x>x_0</math>를 만족하며 충분히 큰 모든 <math>x</math>에 대하여 <math>|f(x)| \le M |g(x)|</math>가 성립하도록 하는 양의 실수 <math>M</math>과 실수<math>x_0</math>가 존재한다.
* <math>|x - a| < \delta</math>를 만족하는 <math>x</math>에 대하여 <math>|f(x)| \le \; M |g(x)|</math> 가 성립하도록 하는 양수 <math>\delta</math> 와 <math>M</math>이 존재한다.
* <math>\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty.</math>
이를 <math>f(x) = O(g(x))</math> 혹은 <math>f(x) \in O(g(x))</math>로 표기하기도 한다.

=== 예 ===
두 [[다항식]] <math>f, g</math>를 다음과 같이 정의한다.
:<math> f(x) = 6x^4 -2x^3 +5</math>
:<math> g(x) = x^4</math>
이때 <math>f(x) = O(g(x)) \mbox{ or } O(x^4)</math>이 된다. 증명은 다음과 같다.

:<math> |6x^4 - 2x^3 + 5| \le 6x^4 + 2x^3 + 5</math> (<math>x > 1</math>일 때)
:<math> |6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4</math> (<math>x^3 < x^4</math>와 같은 방법)
:<math> |6x^4 - 2x^3 + 5| \le 13x^4 </math>
:<math> |6x^4 - 2x^3 + 5| \le 13 |x^4|</math>

=== 표기법 문제 ===
<math>f(x) = O(g(x))</math>라는 표현에서, [[등호]]는 원래의 등호와는 다른 의미를 가진다. 예를 들어, 어떤 함수가 <math>O(x)</math>이면 <math>O(x^2)</math>이므로 <math>O(x) = O(x^2)</math>로 표기할 수는 있지만, <math>O(x^2) = O(x)</math>와 같이 쓰는 것은 잘못된 표기이다. 이 때, 등호 표기는 일반적인 표기법과 다르게 사용된 [[기호의 남용]]으로 볼 수 있다.

이러한 문제를 방지하기 위해, <math>O(g(x))</math>를 원래 정의에서 해당하는 함수들의 집합으로 정의하는 경우도 많이 사용된다. 이러한 경우 <math>f(x) \in O(g(x))</math>과 같이 표기할 수 있고, 이것은 기호의 원래 정의와 잘 맞아 떨어진다.

== 다른 표기법들 ==

대문자 [[O]] 표기법과 비슷하게, 다음의 표기법들이 사용된다.

{| class="wikitable"
!표기법
!설명
!수학적 정의
|-
|<math>f(n) \in O(g(n))</math>
|상한 점근
|<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty</math>
|-
|<math>f(n) \in o(g(n))</math>
|<!--asymptotically negligible-->
|<math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0</math>
|-
|<math>f(n) \in \Omega(g(n))</math>
|하한 점근
|<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 </math>
|-
|<math>f(n) \in \omega(g(n))</math>
|<!--asymptotically dominant-->
|<math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty</math>
|-
|<math>f(n) \in \Theta(g(n))</math>
|상한/하한 점근
|<math>0 < \lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty</math>
|}

또한 Õ 표기법은 대문자 O 표기법의 일종으로, <math>\tilde{O} (g(n))</math>는 <math>O(g(n) \, \log^k g(n))</math>(<math>k</math>는 임의의 상수)를 의미한다. 이 표기법은 함수의 로그 증가 비율을 무시하는 의미를 가지고 있다.
== 같이 보기 ==
* [[상극한과 하극한]]
* [[마스터 정리]]
* [[근삿값의 순서]]

{{전거 통제}}

[[분류:수학 표기법]]
[[분류:점근 해석]]
[[분류:알고리즘 분석]]