점근 표기법
위키백과 ― 우리 모두의 백과사전.
점근 표기법은 어떤 함수의 증가율을 다른 함수와의 비교로 표현하는 방법이다. 알고리즘의 시간복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.
점근 표기법에는 크게 다음과 같은 표기법이 있다.
- 대문자 O 표기법
- 소문자 o 표기법
- 대문자 오메가 표기법 (Ω)
- 소문자 오메가 표기법 (ω)
- 세타 표기법 (Θ)
목차 |
[편집] 대문자 O 표기법
[편집] 정의
가
일 때 상수로 수렴한다면, 즉 x > x0인 모든 실수 x에 대하여
가 성립하는
가 존재한다면
일 때
는
라고 한다. f(x) = O(g(x))라고 표기하기도 하며, 혹은 O(g(x))를 해당 f(x)의 집합으로 정의하기도 한다.
[편집] 예
두 다항식 f,g를 다음과 같이 정의한다.
이때 f(x)는 O(g(x)), 혹은 O(x4)이 된다. 증명은 다음과 같다.
- x가 1보다 클 때
(x3 < x4와 같은 방법)
[편집] 표기법 문제
f(x) = O(g(x))라는 표현에서, 등호는 원래의 등호와는 다른 의미를 가진다. 예를 들어,
어떤 함수가 O(x)이면 O(x2)이므로 O(x) = O(x2)로 표기할 수는 있지만, O(x2) = O(x)와 같이 쓰는 것은 잘못된 표기이다. 이 때, 등호 표기는 일반적인 표기법과 다르게 사용된 기호의 남용으로 볼 수 있다.
이러한 문제를 방지하기 위해, O(g(x))를 원래 정의에서 해당하는 함수들의 집합으로 정의하는 경우도 많이 사용된다. 이러한 경우 과 같이 표기할 수 있고, 이것은 기호의 원래 정의와 잘 맞아 떨어진다.
[편집] 다른 표기법들
대문자 O 표기법과 비슷하게, 다음의 표기법들이 사용된다.
표기법 | 설명 | 수학적 정의 |
---|---|---|
![]() |
상한 점근 | ![]() |
![]() |
![]() |
|
![]() |
하한 점근 | ![]() |
![]() |
![]() |
|
![]() |
상한/하한 점근 | ![]() |