점근 표기법

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

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

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

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

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

대문자 O 표기법 (Big-O notation)

정의

함수 ${\displaystyle f(x)}$, ${\displaystyle g(x)}$에 대해 ${\displaystyle f(x)}$가 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle O(g(x))} 라는 것은 상한 점근에 관한 다음의 동치인 정의와 같다.

• ${\displaystyle x>x_{0}}$를 만족하며 충분히 큰 모든 ${\displaystyle x}$에 대하여 ${\displaystyle |f(x)|\leq M|g(x)|}$가 성립하도록 하는 양의 실수 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M} 과 실수${\displaystyle x_{0}}$가 존재한다.
• ${\displaystyle |x-a|<\delta }$를 만족하는 ${\displaystyle x}$에 대하여 ${\displaystyle |f(x)|\leq \;M|g(x)|}$ 가 성립하도록 하는 양수 ${\displaystyle \delta }$ 와 ${\displaystyle M}$이 존재한다.
• ${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .}$

이를 ${\displaystyle f(x)=O(g(x))}$ 혹은 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f(x) \in O(g(x))} 로 표기하기도 한다.

예

두 다항식 ${\displaystyle f,g}$를 다음과 같이 정의한다.

${\displaystyle f(x)=6x^{4}-2x^{3}+5}$

${\displaystyle g(x)=x^{4}}$

이때 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f(x) = O(g(x)) \mbox{ or } O(x^4)} 이 된다. 증명은 다음과 같다.

${\displaystyle |6x^{4}-2x^{3}+5|\leq 6x^{4}+2x^{3}+5}$ (${\displaystyle x>1}$일 때)

${\displaystyle |6x^{4}-2x^{3}+5|\leq 6x^{4}+2x^{4}+5x^{4}}$ (구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle x^3 < x^4} 와 같은 방법)

${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}}$

구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |6x^4 - 2x^3 + 5| \le 13 |x^4|}

표기법 문제

${\displaystyle f(x)=O(g(x))}$라는 표현에서, 등호는 원래의 등호와는 다른 의미를 가진다. 예를 들어, 어떤 함수가 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle O(x)} 이면 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle O(x^2)} 이므로 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle O(x) = O(x^2)} 로 표기할 수는 있지만, ${\displaystyle O(x^{2})=O(x)}$와 같이 쓰는 것은 잘못된 표기이다. 이 때, 등호 표기는 일반적인 표기법과 다르게 사용된 기호의 남용으로 볼 수 있다.

이러한 문제를 방지하기 위해, 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle O(g(x))} 를 원래 정의에서 해당하는 함수들의 집합으로 정의하는 경우도 많이 사용된다. 이러한 경우 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f(x) \in O(g(x))} 과 같이 표기할 수 있고, 이것은 기호의 원래 정의와 잘 맞아 떨어진다.

다른 표기법들

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

표기법	설명	수학적 정의
구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f(n) \in O(g(n))}	상한 점근	구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty}
${\displaystyle f(n)\in o(g(n))}$		${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}$
구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f(n) \in \Omega(g(n))}	하한 점근	구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 }
${\displaystyle f(n)\in \omega (g(n))}$		구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty}
구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f(n) \in \Theta(g(n))}	상한/하한 점근	${\displaystyle 0<\lim _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty }$

또한 Õ 표기법은 대문자 O 표기법의 일종으로, ${\displaystyle {\tilde {O}}(g(n))}$는 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle O(g(n) \, \log^k g(n))} (${\displaystyle k}$는 임의의 상수)를 의미한다. 이 표기법은 함수의 로그 증가 비율을 무시하는 의미를 가지고 있다.

같이 보기

• 상극한과 하극한
• 마스터 정리
• 근삿값의 순서