점근 표기법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론해석학의 방법이다. 알고리즘복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.

대표적으로 다음의 다섯 가지 표기법이 있다.

  • 대문자 O 표기법
  • 소문자 o 표기법
  • 대문자 오메가(Ω) 표기법
  • 소문자 오메가(ω) 표기법
  • 대문자 세타(Θ) 표기법

이 중 압도적으로 많이 쓰이는 것이 대문자 O 표기법으로, 란다우 표기법이라고도 한다.

대문자 O 표기법[편집]

정의[편집]

함수 f(x), g(x)에 대해 f(x)O(g(x))라는 것은 상한 점근에 관한 다음의 동치인 정의와 같다.

  • \frac{f(x)}{g(x)}\ x \rightarrow \infty일 때의 극한값이 상수로 수렴한다.
  • \lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = M
  • x>x_0인 임의의 x에 대하여 |f(x)| \le M |g(x)|가 성립하도록 하는 \; x_0,\ M>0가 존재한다.

이를 f(x) = O(g(x)) 혹은 f(x) \in O(g(x))로 표기하기도 한다.

[편집]

다항식 f, g를 다음과 같이 정의한다.

 f(x) = 6x^4 -2x^3 +5
 g(x) = x^4

이때 f(x) = O(g(x)) \mbox{ or } O(x^4)이 된다. 증명은 다음과 같다.

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

표기법 문제[편집]

f(x) = O(g(x))라는 표현에서, 등호는 원래의 등호와는 다른 의미를 가진다. 예를 들어,

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

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

다른 표기법들[편집]

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

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

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