점근 표기법

빅-O 표기법(Big O notation)은 함수의 정의역에 대한 대략적인 크기를 설명하는 수학적 표기법이다. 빅-O는 독일 수학자 파울 바흐만과^[1] 에드문트 란다우가 발명하고^[2] 다른 사람들이 확장한 일련의 표기법 중 하나이며, 이를 통틀어 바흐만-란다우 표기법이라고 한다. 문자 O는 바흐만이 근삿값의 순서를 의미하는 Ordnung을 나타내기 위해 선택했다.

컴퓨터 과학에서 빅-O 표기법은 입력 크기가 증가함에 따라 실행 시간 또는 공간 요구 사항이 어떻게 증가하는지에 따라 알고리즘을 분류하는 데 사용된다.^[3][a] 해석적 수론에서 빅-O 표기법은 수론적 함수의 증가에 대한 경계를 표현하는 데 자주 사용된다. 잘 알려진 예 중 하나는 소수 정리의 나머지 항이다.^[4] 미적분학을 포함한 수학적 해석에서 빅-O 표기법은 멱급수를 절단할 때의 오차를 제한하고 더 간단한 함수에 의한 실수 또는 복소수 값 함수의 근사 품질을 표현하는 데 사용된다.

종종 빅-O 표기법은 변수가 커짐에 따라 함수의 성장률에 따라 함수를 특징짓는다. 동일한 점근 성장률을 가진 다른 함수는 동일한 O 표기법을 사용하여 표현될 수 있다. 문자 O는 함수의 성장률을 "함수의 차수"라고도 부르기 때문에 사용된다. 빅-O 표기법으로 함수를 설명하는 것은 함수의 성장률에 대한 상한만 제공한다.

빅-O 표기법과 관련된 여러 표기법이 있으며, ${\displaystyle o}$, ${\displaystyle \sim }$, ${\displaystyle \Omega }$, ${\displaystyle \ll }$, ${\displaystyle \gg }$, ${\displaystyle \asymp }$, ${\displaystyle \omega }$, ${\displaystyle \Theta }$ 기호를 사용하여 다른 종류의 성장률 경계를 설명한다.^[5][6][7]

정식 정의

추정할 함수 ${\textstyle f}$는 정의역 ${\textstyle D}$에서 정의된 실수 또는 복소수 값 함수이며, 비교 함수 ${\textstyle g}$는 동일한 집합 ${\textstyle D}$에서 정의된 음이 아닌 실수 값 함수라고 하자. 정의역에 대한 일반적인 선택은 유한 또는 무한한 실수 구간, 양의 정수 집합, 복소수 집합, 실수/복소수 튜플이다. 정의역이 명시적으로 쓰여 있거나 암묵적으로 이해되는 경우, 다음과 같이 쓴다.

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\ }$$

이는 " ${\textstyle f(x)}$는 ${\textstyle g(x)}$의 빅-${\textstyle O}$"라고 읽으며, 양의 실수 ${\textstyle M}$이 존재하여 다음을 만족하는 경우이다.

$${\displaystyle \left|f(x)\right|\leq M\ g(x)\qquad ~{\mathsf {\ for\ all\ }}~\quad x\in D.}$$

만약 ${\displaystyle g(x)>0}$(즉, 정의역 ${\displaystyle D}$ 전체에서 ${\displaystyle g}$가 0이 아님)이면, 동등한 정의는 비율 ${\textstyle {\frac {f(x)}{g(x)}}}$이 유계라는 것이다. 즉, 모든 ${\displaystyle x\in D}$에 대해 ${\textstyle {\Big |}{\frac {f(x)}{g(x)}}{\Big |}\leq M}$을 만족하는 양의 실수 ${\displaystyle M}$이 존재한다. 이는 정의역이 유한, 무한, 실수, 복소수, 단일 변수 또는 다변수인 경우를 포함하여 컴퓨터 과학 및 수학에서 빅-${\textstyle O}$의 모든 사용을 포괄한다. 대부분의 응용 프로그램에서 ${\textstyle O{\bigl (}\cdot {\bigr )}}$의 인자 안에 나타나는 함수 ${\displaystyle g(x)}$를 가능한 한 간단한 형태로 선택하며, 상수 인자와 하위 차수 항은 생략한다. 숫자 ${\textstyle M}$은 암시적 상수라고 불리는데, 이는 일반적으로 지정되지 않기 때문이다. 빅-${\textstyle O}$ 표기법을 사용할 때 중요한 것은 어떤 유한한 ${\displaystyle M}$이 존재한다는 것이지, 그 특정 값은 아니다. 이는 많은 해석적 부등식의 표현을 단순화한다.

양의 실수 또는 양의 정수에서 정의된 함수에 대해서는 더 제한적이고 다소 상충되는 정의가 여전히 일반적으로 사용된다.^[3][8] 특히 컴퓨터 과학에서 그렇다. 점근적으로 양수인 함수로 제한될 때, 표기법

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\mathsf {as}}\quad x\to \infty }$$

는 어떤 실수 ${\textstyle a}$에 대해 ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$가 정의역 ${\textstyle \left[a,\infty \right)}$에서 성립한다는 것을 의미한다. 여기서 표현 ${\textstyle x\to \infty }$는 극한을 나타내는 것이 아니라, 부등식이 충분히 큰 ${\textstyle x}$에 대해 성립한다는 개념을 나타낸다. 표현 ${\textstyle x\to \infty }$는 종종 생략된다.^[3]

마찬가지로 유한한 실수 ${\textstyle a}$에 대해 표기법

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\text{ as }}\ x\to a}$$

는 어떤 상수 ${\textstyle c>0}$에 대해 ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$가 구간 ${\displaystyle \left[c-a,c+a\right]}$에서 성립한다는 것을 의미한다. 즉, ${\displaystyle a}$의 작은 근방에서 성립한다. 또한 표기법 $${\displaystyle \ f(x)=h(x)+O{\bigl (}g(x){\bigr )}\ }$$ 는 ${\textstyle f(x)-h(x)=O{\bigl (}g(x){\bigr )}}$를 의미한다. 더 복잡한 표현도 가능하다.

등호(=}})가 쓰여 있음에도 불구하고 ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$라는 표현은 등식 관계가 아니라 ${\textstyle f}$와 ${\textstyle g}$를 관련시키는 부등식을 나타낸다.

1930년대에,^[6] 러시아의 정수론학자 I.M. 비노그라도프는 ${\displaystyle \ll }$ 표기법을 도입했으며, 이는 정수론^[4][9][10] 및 다른 수학 분야에서 ${\textstyle O}$ 표기법의 대안으로 점점 더 많이 사용되고 있다. 우리는 다음을 가진다.

$${\displaystyle \ f\ll g\iff f=O{\bigl (}g{\bigr )}.}$$

종종 두 표기법 모두 동일한 작업에서 사용된다.

빅-O의 집합 버전

컴퓨터 과학^[3]에서는 빅-${\textstyle O}$를 함수의 집합을 정의하는 것으로 정의하는 것이 일반적이다. 양수(또는 음이 아닌) 함수 ${\displaystyle g(x)}$가 지정되면, ${\textstyle O{\bigl (}g(x){\bigr )}}$는 ${\textstyle {\tilde {f}}(x)=O{\bigl (}g(x){\bigr )}}$를 만족하는 모든 함수 ${\textstyle {\tilde {f}}}$의 집합을 나타내는 것으로 해석된다. 그러면 동등하게 ${\textstyle f(x)\in O{\bigl (}g(x){\bigr )}}$로 쓸 수 있으며, "함수 ${\textstyle \ f(x)\ }$는 차수가 최대 ${\textstyle g(x)}$인 모든 함수들의 집합에 속한다."라고 읽는다.

무한 정의역을 사용한 예시

일반적인 사용에서 ${\displaystyle O}$ 표기법은 실수 ${\displaystyle [a,\infty )}$의 무한 구간에 적용되며 매우 큰 ${\displaystyle x}$에 대한 함수의 동작을 나타낸다. 이 설정에서 "가장 빠르게" 성장하는 항의 기여는 결국 다른 항들을 무관하게 만들 것이다. 결과적으로 다음 단순화 규칙이 적용될 수 있다.

• ${\displaystyle f(x)}$가 여러 항의 합인 경우, 가장 큰 성장률을 가진 항이 있다면 그 항을 유지하고 다른 모든 항은 생략할 수 있다.
• ${\displaystyle f(x)}$가 여러 인자의 곱인 경우, ${\displaystyle x}$에 의존하지 않는 상수(곱의 인자)는 생략할 수 있다.

예를 들어, ${\displaystyle f(x)=6x^{4}-2x^{3}+5}$라고 하고, 이 함수를 큰 ${\displaystyle x}$에 대한 성장률을 설명하기 위해 ${\displaystyle O}$ 표기법을 사용하여 단순화하고자 한다고 가정하자. 이 함수는 ${\displaystyle 6x^{4}}$, ${\displaystyle -2x^{3}}$, ${\displaystyle 5}$의 세 항의 합이다. 이 세 항 중 가장 높은 성장률을 가진 항은 ${\displaystyle x}$의 함수로서 가장 큰 지수를 가진 항, 즉 ${\displaystyle 6x^{4}}$이다. 이제 두 번째 규칙을 적용할 수 있다. ${\displaystyle 6x^{4}}$는 ${\displaystyle 6}$과 ${\displaystyle x^{4}}$의 곱이며, 첫 번째 인자는 ${\displaystyle x}$에 의존하지 않는다. 이 인자를 생략하면 단순화된 형태 ${\displaystyle x^{4}}$가 된다. 따라서 우리는 ${\displaystyle f(x)}$가 ${\displaystyle x^{4}}$의 "빅-O"라고 말한다. 수학적으로, 모든 ${\displaystyle x\geq 1}$에 대해 ${\displaystyle f(x)=O(x^{4})}$라고 쓸 수 있다. 위에서 언급한 정식 정의를 사용하여 이 계산을 확인할 수 있다. ${\displaystyle f(x)=6x^{4}-2x^{3}+5}$와 ${\displaystyle g(x)=x^{4}}$라고 하자. ${\displaystyle f(x)=O(x^{4})}$라는 진술은 다음과 같이 확장될 수 있다. $${\displaystyle |f(x)|\leq Mx^{4}}$$ 양의 실수 ${\displaystyle M}$의 적절한 선택과 모든 ${\displaystyle x\geq 1}$에 대해. 이를 증명하기 위해 ${\displaystyle M=13}$이라고 하자. 그러면 모든 ${\displaystyle x\geq 1}$에 대해: $${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|-2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$$ 따라서 $${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$ 같은 논리로 다음도 사실이지만, ${\displaystyle f(x)=O(x^{10})}$ 이는 함수 ${\displaystyle f}$의 덜 정확한 근사값이다. 반면에 ${\displaystyle f(x)=O(x^{3})}$이라는 진술은 거짓이다. 왜냐하면 항 ${\displaystyle 6x^{4}}$으로 인해 ${\displaystyle f(x)/x^{3}}$이 유계가 아니기 때문이다.

함수 ${\displaystyle T(n)}$이 입력 ${\displaystyle n}$을 가진 알고리즘에 필요한 단계 수를 설명할 때, 다음과 같은 표현식 $${\displaystyle T(n)=O(n^{2})}$$ 암시된 정의역이 양의 정수 집합인 경우, 알고리즘이 최대 ${\displaystyle n^{2}}$의 시간 복잡도를 가진다는 것을 의미하는 것으로 해석될 수 있다.

유한 정의역을 사용한 예시

빅-O는 유한 구간에서 수학 함수의 근사값에 대한 오차 항을 설명하는 데도 사용될 수 있다. 가장 중요한 항들은 명시적으로 쓰여지고, 그 다음 가장 중요하지 않은 항들은 단일 빅-O 항으로 요약된다. 예를 들어, 지수 급수와 ${\displaystyle x}$가 작을 때 유효한 두 가지 표현을 고려해 보자. $${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {\;x^{2}\ }{2!}}+{\frac {\;x^{3}\ }{3!}}+{\frac {\;x^{4}\ }{4!}}+\dotsb &&{\text{ for all finite }}x\\[4pt]&=1+x+{\frac {\;x^{2}\ }{2}}+O(|x|^{3})&&{\text{ for all }}|x|\leq 1\\[4pt]&=1+x+O(x^{2})&&{\text{ for all }}|x|\leq 1.\end{aligned}}}$$ 중간 표현("${\displaystyle O(|x^{3}|)}$")을 포함하는 줄)은 오차의 절댓값 ${\displaystyle \ e^{x}-(1+x+{\frac {\;x^{2}\ }{2}})\ }$가 ${\displaystyle \ x~}$가 작을 때 어떤 상수 곱하기 ${\displaystyle ~|x^{3}|\ }$ 이하임을 의미한다. 이는 테일러 정리의 사용 예시이다.

주어진 함수의 동작은 유한 정의역과 무한 정의역에서 매우 다를 수 있다. 예를 들어, $${\displaystyle (x+1)^{8}=x^{8}+O(x^{7})\quad {\text{ for }}x\geq 1}$$ 반면 $${\displaystyle (x+1)^{8}=1+8x+O(x^{2})\quad {\text{ for }}|x|\leq 1.}$$

다변수 예시

$${\displaystyle x\sin y=O(x)\quad {\text{ for }}x\geq 1,y{\text{ any real number}}}$$

$${\displaystyle 3a^{2}+7ab+2b^{2}+a+3b+14\ll a^{2}+b^{2}\ll a^{2}\quad {\text{ for all }}a\geq b\geq 1}$$

$${\displaystyle {\frac {xy}{x^{2}+y^{2}}}=O(1)\quad {\text{ for all real }}x,y{\text{ that are not both }}0}$$

$${\displaystyle x^{it}=O(1)\quad {\text{ for }}x\neq 0,t\in \mathbb {R} .}$$

여기서는 두 변수의 복소변수 함수가 있다. 일반적으로 모든 유계 함수는 ${\displaystyle O(1)}$이다.

$${\displaystyle (x+y)^{10}=O(x^{10})\quad {\text{ for }}x\geq 1,-2\leq y\leq 2.}$$

마지막 예는 다른 변수에 대해 유한 및 무한 정의역이 혼합된 경우를 보여준다.

이 모든 예에서 경계는 두 변수 모두에서 균일하다. 때로는 다변수 표현에서 한 변수가 다른 변수보다 더 중요하며, 빅-O 기호 또는 ${\displaystyle \ll }$ 기호에 첨자를 사용하여 암시된 상수 ${\displaystyle M}$이 하나 이상의 변수에 의존한다는 것을 표현할 수 있다. 예를 들어, 다음 표현을 고려해 보자.

$${\displaystyle (1+x)^{b}=1+O_{b}(x)\quad {\text{ for }}0\leq x\leq 1,b{\text{ any real number.}}}$$

이는 각 실수 ${\displaystyle b}$에 대해 ${\displaystyle b}$에 의존하는 상수 ${\displaystyle M_{b}}$가 존재하여 모든 ${\displaystyle 0\leq x\leq 1}$에 대해 다음이 성립한다는 것을 의미한다. $${\displaystyle |(1+x)^{b}-1|\leq M_{b}\cdot x.}$$ 이 특정 진술은 일반 이항 정리에서 비롯된다.

테일러 급수 이론에서 흔히 볼 수 있는 또 다른 예는 $${\displaystyle e^{x}=1+x+O_{r}(x^{2})\quad {\text{ for all }}|x|\leq r,r{\text{ being any real number.}}}$$ 여기서 암시된 상수는 정의역의 크기에 따라 달라진다.

첨자 표기법은 이 페이지의 다른 모든 표기법에 적용된다.

속성

곱

${\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})}$

${\displaystyle f\cdot O(g)=O(|f|g)}$

합

만약 ${\displaystyle f_{1}=O(g_{1})}$ 이고 ${\displaystyle f_{2}=O(g_{2})}$ 이면 ${\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}$ 이다. 따라서 만약 ${\displaystyle f_{1}=O(g)}$ 이고 ${\displaystyle f_{2}=O(g)}$ 이면 ${\displaystyle f_{1}+f_{2}=O(g)}$ 이다.

상수로 곱하기

k가 0이 아닌 상수라고 하자. 그러면 ${\displaystyle O(|k|\cdot g)=O(g)}$이다. 다시 말해, ${\displaystyle f=O(g)}$이면 ${\displaystyle k\cdot f=O(g)}$이다.

추이적 속성

만약 ${\displaystyle f=O(g)}$이고 ${\displaystyle g=O(h)}$이면 ${\displaystyle f=O(h)}$이다.

양의 정수 ${\displaystyle n}$의 함수 ${\displaystyle f}$가 다른 함수들의 유한 합으로 쓰여질 수 있다면, 가장 빠르게 성장하는 함수가 ${\displaystyle f(n)}$의 차수를 결정한다. 예를 들어,

${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{for }}n\geq 1.}$

무한으로 향하는 성장에 대한 몇 가지 일반적인 규칙. 아래의 두 번째 및 세 번째 속성은 로피탈의 정리를 사용하여 엄밀하게 증명할 수 있다.

큰 거듭제곱이 작은 거듭제곱을 지배한다

${\displaystyle b>a\geq 0}$인 경우, $${\displaystyle n^{a}=O(n^{b}).}$$

거듭제곱이 로그를 지배한다

임의의 양수 ${\displaystyle a,b}$에 대해, $${\displaystyle (\log n)^{a}=O_{a,b}(n^{b}),}$$ ${\displaystyle a}$가 아무리 크고 ${\displaystyle b}$가 아무리 작더라도. 여기서 암시된 상수는 ${\displaystyle a}$와 ${\displaystyle b}$ 모두에 의존한다.

지수가 거듭제곱을 지배한다

임의의 양수 ${\displaystyle a,b}$에 대해, $${\displaystyle n^{a}=O_{a,b}(e^{bn}),}$$ ${\displaystyle a}$가 아무리 크고 ${\displaystyle b}$가 아무리 작더라도.

어떤 ${\displaystyle c}$에 대해서도 ${\displaystyle n^{c}}$보다 빠르게 성장하는 함수를 초다항식(superpolynomial)이라고 한다. ${\displaystyle c>1}$인 형태의 어떤 지수 함수 ${\displaystyle c^{n}}$보다 느리게 성장하는 함수를 준지수식(subexponential)이라고 한다. 알고리즘은 초다항식적이면서 준지수적일 수 있다. 이러한 예로는 소인수분해의 알려진 가장 빠른 알고리즘과 함수 ${\displaystyle n^{\log n}}$이 있다.

로그 안의 ${\displaystyle n}$의 어떤 거듭제곱도 무시할 수 있다. 임의의 양수 ${\displaystyle c}$에 대해 ${\displaystyle O(\log n)}$ 표기법은 ${\displaystyle O(\log(n^{c}))}$와 정확히 같은 의미이다. 왜냐하면 ${\displaystyle \log(n^{c})=c\log n}$이기 때문이다. 마찬가지로, 다른 상수 밑을 가진 로그는 빅-O 표기법에 대해 동등하다. 반면에, 다른 밑을 가진 지수는 동일한 차수가 아니다. 예를 들어, ${\displaystyle 2^{n}}$과 ${\displaystyle 3^{n}}$은 동일한 차수가 아니다.

더 복잡한 표현

더 복잡한 사용에서는 ${\displaystyle O(\cdot )}$가 방정식의 여러 위치, 심지어 각 변에 여러 번 나타날 수도 있다. 예를 들어, ${\displaystyle n}$이 양의 정수일 때 다음이 성립한다. $${\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}}$$ 이러한 진술의 의미는 다음과 같다. 왼쪽 변의 각 ${\displaystyle O(\cdot )}$를 만족하는 어떤 함수들에 대해, 오른쪽 변의 각 ${\displaystyle O(\cdot )}$를 만족하는 어떤 함수들이 존재하여, 이 모든 함수들을 방정식에 대입하면 양변이 같아진다는 것이다. 예를 들어, 위 세 번째 방정식은 " ${\displaystyle f(n)=O(1)}$을 만족하는 어떤 함수에 대해, ${\displaystyle n^{f(n)}=g(n)}$을 만족하는 어떤 함수 ${\displaystyle g(n)=O(e^{n})}$가 존재한다"는 의미이다. " ${\displaystyle g(n)=O(e^{n})}$"라는 진술의 암시된 상수는 " ${\displaystyle f(n)=O(1)}$"라는 표현의 암시된 상수에 의존할 수 있다.

몇 가지 추가 예시: $${\displaystyle {\begin{aligned}f=O(g)\;&\Rightarrow \;\int _{a}^{b}f=O{\bigg (}\int _{a}^{b}g{\bigg )}\\f(x)=g(x)+O(1)\;&\Rightarrow \;e^{f(x)}=O(e^{g(x)})\\(1+O(1/x))^{O(x)}&=O(1)\quad {\text{ for }}x>0\\\sin x&=O(|x|)\quad {\text{ for all real }}x.\end{aligned}}}$$

비노그라도프의 ${\displaystyle \gg }$와 커누스의 빅 오메가

${\displaystyle f,g}$가 모두 양의 함수인 경우, 비노그라도프^[6]는 ${\displaystyle f(x)\gg g(x)}$ 표기법을 도입했으며, 이는 ${\displaystyle g(x)=O(f(x))}$와 동일한 의미이다. 비노그라도프의 두 표기법은 양의 함수 ${\displaystyle f,g}$에 대해 시각적 대칭을 즐긴다. $${\displaystyle f(x)\ll g(x)\Longleftrightarrow g(x)\gg f(x).}$$

1976년, 도널드 커누스^[7]는 다음과 같이 정의했다.

${\displaystyle f(x)=\Omega (g(x))\Longleftrightarrow g(x)=O(f(x))}$

이는 비노그라도프의 ${\displaystyle f(x)\gg g(x)}$와 같은 의미를 갖는다.

훨씬 이전에 하디와 리틀우드는 ${\displaystyle \Omega }$를 다르게 정의했지만, 이는 더 이상 거의 사용되지 않는다(이비치(Ivić)의 책^[9]은 예외 중 하나이다). 더 강한 속성을 설명하기 위해 ${\displaystyle \Omega }$-기호를 사용한 것을 정당화하며,^[7] 커누스는 다음과 같이 썼다. "내가 지금까지 컴퓨터 과학에서 본 모든 응용 프로그램에 대해 더 강한 요구 사항...이 훨씬 더 적절하다." 커누스는 또한 "하디와 리틀우드의 ${\displaystyle \Omega }$ 정의를 변경했지만, 그들의 정의가 널리 사용되지 않고, 그들의 정의가 적용되는 비교적 드문 경우에 그들이 말하고 싶은 것을 표현할 다른 방법이 있기 때문에 그렇게 하는 것이 정당하다고 생각한다."고 썼다.^[7]

실제로 커누스의 빅 ${\displaystyle \Omega }$는 오늘날 하디-리틀우드의 빅 ${\displaystyle \Omega }$보다 훨씬 더 널리 사용되며, 컴퓨터 과학과 조합론에서 일반적인 특징이다.

하디의 ≍와 커누스의 빅 세타

해석적 수론에서^[10] 표기법 ${\displaystyle f(x)\asymp g(x)}$는 ${\displaystyle f(x)=O(g(x))}$와 ${\displaystyle g(x)=O(f(x))}$ 모두를 의미한다. 이 표기법은 원래 하디에게서 비롯되었다.^[5] 동일한 개념에 대한 커누스의 표기법은 ${\displaystyle f(x)=\Theta (g(x))}$이다.^[7] 대략적으로 말하면, 이 진술들은 ${\displaystyle f(x)}$와 ${\displaystyle g(x)}$가 동일한 차수를 가진다는 것을 주장한다. 이 표기법들은 양의 상수 ${\displaystyle M,N}$이 존재하여 $${\displaystyle Ng(x)\leq f(x)\leq Mg(x)}$$ ${\displaystyle f,g}$의 공통 정의역의 모든 ${\displaystyle x}$에 대해 성립한다는 것을 의미한다. 함수가 양의 정수 또는 양의 실수에서 정의될 때, 빅-O와 마찬가지로 저자들은 종종 진술 ${\displaystyle f(x)=\Omega (g(x))}$ 및 ${\displaystyle f(x)=\Theta (g(x))}$를 충분히 큰 모든 ${\displaystyle x}$에 대해, 즉 어떤 지점 ${\displaystyle x_{0}}$ 이후의 모든 ${\displaystyle x}$에 대해 성립하는 것으로 해석한다. 때로는 이를 진술에 ${\displaystyle x\to \infty }$를 추가하여 나타내기도 한다. 예를 들어, $${\displaystyle 2n^{2}-10n=\Theta (n^{2})}$$ 는 정의역이 ${\displaystyle n\geq 6}$일 때는 참이지만, 함수가 ${\displaystyle n=5}$에서 0이므로 정의역이 모든 양의 정수일 때는 거짓이다.

추가 예시

$${\displaystyle n^{3}+20n^{2}+n+12\asymp n^{3}\quad {\text{ for all }}n\geq 1.}$$

$${\displaystyle (1+x)^{8}=x^{8}+\Theta (x^{7})\quad {\text{ for all }}x\geq 1.}$$

표기법

$${\displaystyle f(n)=e^{\Omega (n)}\quad {\text{ for all }}n\geq 1,}$$ 은 양의 상수 ${\displaystyle M}$이 존재하여 모든 ${\displaystyle n\geq 1}$에 대해 ${\displaystyle f(n)\geq e^{Mn}}$임을 의미한다. 대조적으로, $${\displaystyle f(n)=e^{-O(n)}\quad {\text{ for all }}n\geq 1,}$$ 은 양의 상수 ${\displaystyle M}$이 존재하여 모든 ${\displaystyle n\geq 1}$에 대해 ${\displaystyle f(n)\geq e^{-Mn}}$임을 의미하고 $${\displaystyle f(n)=e^{\Theta (n)}\quad {\text{ for all }}n\geq 1,}$$ 은 양의 상수 ${\displaystyle M,N}$이 존재하여 모든 ${\displaystyle n\geq 1}$에 대해 ${\displaystyle e^{Mn}\leq f(n)\leq e^{Nn}}$임을 의미한다.

임의의 정의역 ${\displaystyle D}$에 대해, $${\displaystyle f(x)=g(x)+O(1)\Longleftrightarrow e^{f(x)}\asymp e^{g(x)},}$$ 각 진술은 ${\displaystyle D}$의 모든 ${\displaystyle x}$에 대해 성립한다.

일반적인 함수의 차수

 시간 복잡도 § 일반적인 시간 복잡도 표 문서에 이 부분의 추가 정보가 있습니다.

알고리즘의 실행 시간을 분석할 때 일반적으로 접하게 되는 함수 클래스 목록이다. 각 경우에 c는 양의 상수이고 n은 무한히 증가한다. 느리게 성장하는 함수가 일반적으로 먼저 나열된다.

표기법	이름	예시
${\displaystyle O(1)}$	상수	정렬된 숫자 배열에서 중앙값 찾기; ${\displaystyle (-1)^{n}}$ 계산; 상수 크기 순람표 사용
${\displaystyle O(\alpha (n))}$	역 아커만 함수	서로소 집합 자료 구조의 연산당 상각 복잡도
${\displaystyle O(\log \log n)}$	이중 로그	균일하게 분포된 값의 정렬된 배열에서 보간 탐색을 사용하여 항목을 찾는 데 걸리는 평균 비교 횟수
${\displaystyle O(\log n)}$	로그	이진 탐색 또는 균형 잡힌 검색 트리를 사용하여 정렬된 배열에서 항목 찾기, 이항 힙의 모든 연산
${\displaystyle O((\log n)^{c})}$ ${\textstyle c>1}$	다항 로그	행렬 체인 순서는 병렬 RAM에서 다항 로그 시간에 해결될 수 있다.
${\displaystyle O(n^{c})}$ ${\textstyle 0<c<1}$	분수 거듭제곱	K-d 트리 검색
${\displaystyle O(n)}$	선형	정렬되지 않은 목록이나 정렬되지 않은 배열에서 항목 찾기; 리플 캐리를 사용하여 두 개의 n비트 정수 더하기
${\displaystyle O(n\log ^{*}n)}$	n 로그-스타 n	Seidel의 알고리즘을 사용하여 단순 다각형의 삼각화 수행,[11] 여기서 ${\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}$
${\displaystyle O(n\log n)=O(\log n!)}$	선형 로그, 로그 선형, 준선형, 또는 "${\displaystyle n\log n}$"	고속 푸리에 변환 수행; 가장 빠른 비교 정렬; 힙 정렬 및 합병 정렬
${\displaystyle O(n^{2})}$	이차	학교식 곱셈으로 두 개의 ${\displaystyle n}$자리 숫자 곱하기; 버블 정렬, 선택 정렬 및 삽입 정렬과 같은 간단한 정렬 알고리즘; 퀵 정렬, 셸 정렬 및 트리 정렬과 같이 일반적으로 더 빠른 정렬 알고리즘의 (최악의 경우) 경계
${\displaystyle O(n^{c})}$	다항 또는 대수	트리 인접 문법 구문 분석; 이분 그래프의 최대 부합; LU 분해로 행렬식 찾기
${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ ${\textstyle 0<\alpha <1}$	L-표기법 또는 준지수	이차 체 또는 수체 체를 사용하여 숫자 인수분해
${\displaystyle O(c^{n})}$ ${\textstyle c>1}$	지수	동적 계획법을 사용하여 외판원 문제의 (정확한) 해 찾기; 무차별 대입 검색을 사용하여 두 논리적 진술이 동등한지 결정
${\displaystyle O(n!)}$	계승	무차별 대입 검색을 통해 외판원 문제 해결; 부분 순서 집합의 모든 제한 없는 순열 생성; 라플라스 전개로 행렬식 찾기; 집합의 모든 분할 열거

진술 ${\displaystyle f(n)=O(n!)}$은 점근적 복잡성에 대한 더 간단한 공식을 유도하기 위해 때때로 ${\displaystyle f(n)=O\left(n^{n}\right)}$로 약화된다. 이러한 예시 중 많은 경우, 실행 시간은 실제로 ${\displaystyle \Theta (g(n))}$이며, 이는 더 많은 정확성을 전달한다.

스몰-o 표기법

충분히 큰 ${\displaystyle x}$에 대해 ${\displaystyle g(x)>0}$인 실수 변수 ${\displaystyle x}$의 실수 또는 복소수 값 함수에 대해 다음과 같이 쓴다. ^[2]

${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty }$

만약 $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.}$$ 즉, 모든 양의 상수 ε에 대해 상수 ${\displaystyle x_{0}}$가 존재하여 다음을 만족한다.

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}$

직관적으로, 이것은 ${\displaystyle g(x)}$가 ${\displaystyle f(x)}$보다 훨씬 빠르게 성장하거나, 동등하게 ${\displaystyle f(x)}$가 ${\displaystyle g(x)}$보다 훨씬 느리게 성장한다는 것을 의미한다. 예를 들어, 다음을 가진다.

${\displaystyle 200x=o(x^{2})}$ and ${\displaystyle 1/x=o(1),}$     both as ${\displaystyle x\to \infty .}$

${\displaystyle x}$의 큰 값에 대한 함수의 동작에 관심이 있을 때, 스몰-o 표기법은 해당 빅-O 표기법보다 더 강한 진술을 한다. ${\displaystyle g}$의 스몰-o인 모든 함수는 어떤 구간 ${\displaystyle [a,\infty )}$에서 ${\displaystyle g}$의 빅-O이기도 하지만, ${\displaystyle g}$의 빅-O인 모든 함수가 ${\displaystyle g}$의 스몰-o인 것은 아니다. 예를 들어, ${\displaystyle 2x^{2}=O(x^{2})}$이지만 ${\displaystyle 2x^{2}\neq o(x^{2})}$ for ${\displaystyle x\geq 1}$.

스몰-o는 여러 산술 연산을 따른다. 예를 들어,

${\displaystyle c}$가 0이 아닌 상수이고 ${\displaystyle f=o(g)}$이면 ${\displaystyle c\cdot f=o(g)}$이고,

${\displaystyle f=o(F)}$이고 ${\displaystyle g=o(G)}$이면 ${\displaystyle f\cdot g=o(F\cdot G).}$

${\displaystyle f=o(F)}$이고 ${\displaystyle g=o(G)}$이면 ${\displaystyle f+g=o(F+G)}$

또한 추이성 관계를 만족한다.

${\displaystyle f=o(g)}$이고 ${\displaystyle g=o(h)}$이면 ${\displaystyle f=o(h).}$

스몰-o는 유한한 경우로도 일반화될 수 있다.^[2] ${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to x_{0}}$ 만약 $${\displaystyle \lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.}$$ 다시 말해, ${\displaystyle \lim _{x\to x_{0}}\alpha (x)=0}$인 어떤 ${\displaystyle \alpha (x)}$에 대해 ${\displaystyle f(x)=\alpha (x)g(x)}$이다.

이 정의는 테일러 급수를 사용하여 극한을 계산하는 데 특히 유용하다. 예를 들어:

${\displaystyle \sin x=x-{\frac {x^{3}}{3!}}+\ldots =x+o(x^{2}){\text{ as }}x\to 0}$, 따라서 ${\displaystyle \lim _{x\to 0}{\frac {\sin x}{x}}=\lim _{x\to 0}{\frac {x+o(x^{2})}{x}}=\lim _{x\to 0}1+o(x)=1}$

점근 표기법

스몰-o와 관련된 관계는 점근 표기법이다. ${\displaystyle \sim }$. 실수 값 함수 ${\displaystyle f,g}$에 대해, 표현식 $${\displaystyle f(x)\sim g(x)\quad {\text{ as }}x\to \infty }$$ 은 다음을 의미한다. $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.}$$ ${\displaystyle f(x)\sim g(x)}$가 ${\displaystyle f(x)=(1+o(1))g(x)}$와 동등하다는 것을 관찰함으로써 이를 스몰-o와 연결할 수 있다. 여기서 ${\displaystyle o(1)}$은 ${\displaystyle x\to \infty }$일 때 0으로 수렴하는 함수를 나타낸다. 이를 "${\displaystyle f(x)}$는 ${\displaystyle g(x)}$에 점근한다"라고 읽는다. 동일한 (유한 또는 무한) 정의역에서 0이 아닌 함수에 대해, ${\displaystyle \sim }$는 동치 관계를 형성한다.

${\displaystyle \sim }$ 표기법을 사용하는 가장 유명한 정리 중 하나는 스털링 근사이다. $${\displaystyle n!\sim {\bigg (}{\frac {n}{e}}{\bigg )}^{n}{\sqrt {2\pi n}}\quad {\text{ as }}n\to \infty .}$$ 정수론에서 유명한 소수 정리는 다음을 나타낸다. $${\displaystyle \pi (x)\sim {\frac {x}{\log x}}\quad {\text{ as }}x\to \infty ,}$$ 여기서 ${\displaystyle \pi (x)}$는 ${\displaystyle x}$ 이하인 소수의 개수이고 ${\displaystyle \log }$는 ${\displaystyle x}$의 자연로그이다.

스몰-o와 마찬가지로, 유한 극한(양측 또는 일측)을 사용하는 버전도 있다. 예를 들어 $${\displaystyle \sin x\sim x\quad {\text{ as }}x\to 0.}$$

추가 예시: $${\displaystyle x^{a}=o_{a,b}(e^{bx})\quad {\text{ as }}x\to \infty ,{\text{ for any positive constants }}a,b,}$$ $${\displaystyle f(x)=g(x)+o(1)\quad \Longleftrightarrow \quad e^{f(x)}\sim e^{g(x)}\quad (x\to \infty ).}$$ $${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}\sim {\frac {1}{s-1}}\quad (x\to \infty ).}$$ 마지막 점근성은 리만 제타 함수의 기본적인 속성이다.

커누스의 스몰 오메가 (${\displaystyle \omega }$)

결과적으로 양수인 실수 값 함수 ${\displaystyle f,g}$에 대해, 표기법 $${\displaystyle f(x)=\omega (g(x))\quad {\text{ as }}x\to \infty }$$ 은 다음을 의미한다. $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty .}$$ 다시 말해, ${\displaystyle g(x)=o(f(x))}$이다. 대략적으로 말하면, 이것은 ${\displaystyle f(x)}$가 ${\displaystyle g(x)}$보다 훨씬 빠르게 성장한다는 것을 의미한다.

하디-리틀우드의 Ω 표기법

1914년 G.H. 하디와 J.E. 리틀우드는 새로운 기호 ${\displaystyle \ \Omega }$를 도입했으며,^[12] 이는 다음과 같이 정의된다.

${\displaystyle f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}\quad }$ as ${\displaystyle \quad x\to \infty \quad }$ if ${\displaystyle \quad \limsup _{x\to \infty }\ \left|{\frac {\ f(x)\ }{g(x)}}\right|>0~.}$

따라서 ${\displaystyle ~f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}~}$는 ${\displaystyle ~f(x)=o{\bigl (}\ g(x)\ {\bigr )}~}$의 부정이다.

1916년에 동일한 저자들은 ${\displaystyle \ \Omega _{R}\ }$과 ${\displaystyle \ \Omega _{L}\ }$이라는 두 개의 새로운 기호를 다음과 같이 정의했다.^[13]

${\displaystyle f(x)=\Omega _{R}{\bigl (}\ g(x)\ {\bigr )}\quad }$ as ${\displaystyle \quad x\to \infty \quad }$ if ${\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\$ ;}

${\displaystyle f(x)=\Omega _{L}{\bigl (}\ g(x)\ {\bigr )}\quad }$ as ${\displaystyle \quad x\to \infty \quad }$ if ${\displaystyle \quad ~\liminf _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}<0~.}$

이 기호들은 E. 란다우에 의해 1924년에 동일한 의미로 사용되었다.^[14] 그러나 란다우를 따른 저자들은 동일한 정의에 대해 다른 표기법을 사용한다.^[9] 기호 ${\displaystyle \ \Omega _{R}\ }$는 현재 표기법 ${\displaystyle \ \Omega _{+}\ }$으로 대체되었고, ${\displaystyle \ \Omega _{L}\ }$은 ${\displaystyle \ \Omega _{-}~}$가 되었다.

이 세 가지 기호 ${\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,}$ 뿐만 아니라 ${\displaystyle \ f(x)=\Omega _{\pm }{\bigl (}\ g(x)\ {\bigr )}\ }$(${\displaystyle \ f(x)=\Omega _{+}{\bigl (}\ g(x)\ {\bigr )}\ }$와 ${\displaystyle \ f(x)=\Omega _{-}{\bigl (}\ g(x)\ {\bigr )}\ }$가 모두 만족됨을 의미함)는 현재 해석적 수론에서 사용되고 있다.^{[9] [10]}

간단한 예시

우리는 다음을 가진다.

${\displaystyle \sin x=\Omega (1)\quad }$ as ${\displaystyle \quad x\to \infty \ ,}$

더 정확하게는

${\displaystyle \sin x=\Omega _{\pm }(1)\quad }$ as ${\displaystyle \quad x\to \infty ,~}$

여기서 ${\displaystyle \Omega _{\pm }}$는 좌변이 ${\displaystyle \Omega _{+}(1)}$과 ${\displaystyle \Omega _{-}(1)}$을 모두 의미한다는 뜻이다.

우리는 다음을 가진다.

${\displaystyle 1+\sin x=\Omega (1)\quad }$ as ${\displaystyle \quad x\to \infty \ ,}$

더 정확하게는

${\displaystyle 1+\sin x=\Omega _{+}(1)\quad }$ as ${\displaystyle \quad x\to \infty \$ ;}

그러나

${\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad }$ as ${\displaystyle \quad x\to \infty ~.}$

바흐만-란다우 표기법 계열

공식적인 정의를 이해하려면 수학에서 사용되는 논리 기호 목록을 참조한다.

표기법	이름[7]	설명	정식 정의	간결한 정의 [4] [5] [7] [12] [15][16]
${\displaystyle f(n)=o(g(n))}$	스몰 O; 스몰 오; 리틀 O; 리틀 오	f는 점근적으로 (어떤 상수 인자 ${\displaystyle k}$에 대해) g에 의해 지배된다.	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}$
${\displaystyle f(n)=O(g(n))}$ 또는 ${\displaystyle f(n)\ll g(n)}$ (비노그라도프 표기법)	빅 O; 빅 오; 빅 오미크론	${\displaystyle |f|}$는 (상수 인자 ${\displaystyle k}$까지) g에 의해 위로 유계이다.	${\displaystyle \exists k>0\,\forall n\in D\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \sup _{n\in D}{\frac {\left|f(n)\right|}{g(n)}}<\infty }$
${\displaystyle f(n)\asymp g(n)}$ (하디 표기법) 또는 ${\displaystyle f(n)=\Theta (g(n))}$ (커누스 표기법)	(하디)와 같은 차수; 빅 세타 (커누스)	f는 g에 의해 위(상수 인자 ${\displaystyle k_{2}}$와 함께)와 아래(상수 인자 ${\displaystyle k_{1}}$와 함께) 모두 유계이다.	${\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\forall n\in D\colon }$ ${\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)}$	${\displaystyle f(n)=O(g(n))}$ and ${\displaystyle g(n)=O(f(n))}$
${\displaystyle f(n)\sim g(n)}$ as ${\displaystyle n\to a}$, where ${\displaystyle a}$ is finite, ${\displaystyle \infty }$ or ${\displaystyle -\infty }$	점근 동치	f는 점근적으로 g와 같다.	${\displaystyle \forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon }$ (${\displaystyle a=\infty }$의 경우)	${\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=1}$
${\displaystyle f(n)=\Omega (g(n))}$ (커누스 표기법), 또는 ${\displaystyle f(n)\gg g(n)}$ (비노그라도프 표기법)	복잡도 이론의 빅 오메가 (커누스)	f는 상수 인자까지 g에 의해 아래로 유계이다.	${\displaystyle \exists k>0\,\forall n\in D\colon f(n)\geq k\,g(n)}$	${\displaystyle \inf _{n\in D}{\frac {f(n)}{g(n)}}>0}$
${\displaystyle f(n)=\omega (g(n))}$ as ${\displaystyle n\to a}$, where ${\displaystyle a}$ can be finite, ${\displaystyle \infty }$ or ${\displaystyle -\infty }$	스몰 오메가; 리틀 오메가	f는 점근적으로 g를 지배한다.	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)}$ ( ${\displaystyle a=\infty }$의 경우)	${\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=\infty }$
${\displaystyle f(n)=\Omega (g(n))}$	정수론의 빅 오메가 (하디-리틀우드)	${\displaystyle |f|}$는 점근적으로 g에 의해 지배되지 않는다.	${\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0}$

극한 정의는 극한의 근방에서 ${\displaystyle g(n)>0}$을 가정한다. 극한이 ${\displaystyle \infty }$일 때는 충분히 큰 ${\displaystyle n}$에 대해 ${\displaystyle g(n)>0}$임을 의미한다.

컴퓨터 과학 및 조합론은 빅 ${\displaystyle O}$, 빅 세타 ${\displaystyle \Theta }$, 스몰 ${\displaystyle o}$, 스몰 오메가 ${\displaystyle \omega }$ 및 커누스의 빅 오메가 ${\displaystyle \Omega }$ 표기법을 사용한다.^[3] 해석적 수론은 종종 빅 ${\displaystyle O}$, 스몰 ${\displaystyle o}$, 하디의 ${\displaystyle \asymp }$, 하디-리틀우드의 빅 오메가 ${\displaystyle \Omega }$ (+, − 또는 ± 첨자 유무), 비노그라도프의 ${\displaystyle \ll }$ 및 ${\displaystyle \gg }$ 표기법 및 ${\displaystyle \sim }$ 표기법을 사용한다. ^{[9] [4] [10]} 스몰 오메가 ${\displaystyle \omega }$ 표기법은 해석학이나 정수론에서 자주 사용되지 않는다. ^[17]

다른 표기법을 사용한 근사의 품질

 알고리즘 분석 문서에 이 부분의 추가 정보가 있습니다.

비공식적으로, 특히 컴퓨터 과학에서 빅-O 표기법은 주어진 맥락에서 빅-세타 ${\displaystyle \Theta }$ 표기법이 더 사실적으로 적절할 수 있는 점근적으로 정확한 경계를 설명하는 데 다소 다르게 사용될 수 있다.^[18] 예를 들어, 함수 ${\displaystyle T(n)=73n^{3}+22n^{2}+58}$를 고려할 때, 다음은 모두 일반적으로 허용되지만, 더 느슨한 경계(아래 1번)보다 더 엄격한 경계(아래 2, 3, 4번)가 일반적으로 훨씬 선호된다.

1. ${\displaystyle T(n)=O(n^{100})}$
2. ${\displaystyle T(n)=O(n^{3})}$
3. ${\displaystyle T(n)=\Theta (n^{3})}$
4. ${\displaystyle T(n)\sim 73n^{3}}$ as ${\displaystyle n\to \infty }$.

이 세 진술은 모두 참이지만, 각 진술에 포함된 정보는 점진적으로 더 많다. 그러나 일부 분야에서는 빅-O 표기법(위 목록의 2번)이 빅-세타 표기법(위 목록의 3번)보다 더 일반적으로 사용될 수 있다. 예를 들어, ${\displaystyle T(n)}$이 입력 크기 ${\displaystyle n}$에 대한 새로 개발된 알고리즘의 실행 시간을 나타내는 경우, 알고리즘의 개발자와 사용자는 하한 또는 점근적 동작에 대한 명시적인 진술 없이 실행되는 데 걸리는 시간에 상한을 두는 것을 더 선호할 수 있다.

바흐만-란다우 표기법의 확장

컴퓨터 과학에서 때때로 사용되는 또 다른 표기법은 다항 로그 인자를 숨기는 ${\displaystyle {\tilde {O}}}$(소프트-O로 읽음)이다. 두 가지 정의가 사용되고 있다. 일부 저자는 ${\displaystyle f(n)={\tilde {O}}(g(n))}$을 어떤 ${\displaystyle k}$에 대해 ${\displaystyle f(n)=O(g(n)\log ^{k}n)}$의 약어로 사용하는 반면, 다른 저자는 ${\displaystyle f(n)=O(g(n)\log ^{k}g(n))}$의 약어로 사용한다.^[19] ${\displaystyle g(n)}$이 ${\displaystyle n}$에 대한 다항식일 때는 차이가 없지만, 후자의 정의는 예를 들어 ${\displaystyle n2^{n}={\tilde {O}}(2^{n})}$라고 말할 수 있게 하는 반면, 전자의 정의는 어떤 상수 ${\displaystyle k}$에 대해 ${\displaystyle \log ^{k}n={\tilde {O}}(1)}$을 허용한다. 일부 저자는 후자의 정의와 동일한 목적으로 O^*를 사용한다.^[20] 본질적으로 이는 빅-O 표기법으로, 로그 인자를 무시한다. 왜냐하면 다른 초-로그 함수들의 성장률 효과가 큰 입력 매개변수에 대한 성장률 폭발을 나타내며, 이는 로그 성장 인자(들)에 의해 기여된 더 미세한 효과보다 나쁜 실행 시간 성능을 예측하는 데 더 중요하기 때문이다. 이 표기법은 종종 당면한 문제에 대해 너무 엄격하게 제한된 성장률 내에서의 "사소한 시비"를 피하기 위해 사용된다(왜냐하면 ${\displaystyle \log ^{k}n=o(n^{\varepsilon })}$ 어떤 상수 ${\displaystyle k}$와 어떤 ${\displaystyle \varepsilon >0.}$

또한 다음과 같이 정의된 L 표기법

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}$

은 ${\displaystyle \log n}$ 관점에서 다항식과 지수 함수 사이에 있는 함수에 편리하다.

일반화 및 관련 용도

노름 벡터 공간에서 값을 취하는 함수로의 일반화는 간단하다(절댓값을 노름으로 대체). 여기서 ${\displaystyle f}$와 ${\displaystyle g}$는 같은 공간에서 값을 취할 필요는 없다. 임의의 위상군에서 값을 취하는 함수 ${\displaystyle g}$로의 일반화도 가능하다. "극한 과정" ${\displaystyle x\to x_{0}}$는 임의의 필터 기저를 도입함으로써 일반화될 수도 있다. 즉, 유향 그물 ${\displaystyle f}$와 ${\displaystyle g}$로 일반화될 수 있다. ${\displaystyle o}$ 표기법은 매우 일반적인 공간에서 미분과 미분가능성을 정의하는 데 사용될 수 있으며, 또한 함수들의 (점근적) 동등성을 정의하는 데도 사용될 수 있다.

${\displaystyle f\sim g\iff (f-g)\in o(g)}$

이는 동치 관계이며 위에서 언급한 "${\displaystyle f}$는 ${\displaystyle \Theta (g)}$" 관계보다 더 제한적인 개념이다. (만약 ${\displaystyle f}$와 ${\displaystyle g}$가 양의 실수 값 함수라면 ${\displaystyle \lim f/g=1}$로 축소된다.) 예를 들어, ${\displaystyle 2x=\Theta (x)}$는 참이지만 ${\displaystyle 2x-x\neq o(x)}$는 거짓이다.

역사

보아-레이몬드, 바흐만-란다우, 하디, 비노그라도프, 커누스 표기법의 역사를 간략하게 설명한다.

1870년, 파울 뒤 부아-레이몬드(Paul du Bois-Reymond)^[21]는 ${\displaystyle f(x)\succ \phi (x)}$, ${\displaystyle f(x)\sim g(x)}$, ${\displaystyle f(x)\prec \phi (x)}$를 각각 다음과 같이 정의했다. $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=\infty ,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}>0,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=0.}$$ 이들은 널리 채택되지 않았고 오늘날에는 사용되지 않는다. 첫 번째와 세 번째는 대칭성을 가진다. ${\displaystyle f(x)\prec \phi (x)}$는 ${\displaystyle \phi (x)\succ f(x)}$와 동일한 의미이다. 나중에 란다우는 ${\displaystyle \sim }$를 ${\displaystyle f(x)/\phi (x)}$의 극한이 1과 같다는 좁은 의미로 채택했다. 이 표기법들은 오늘날에는 사용되지 않는다.

기호 O는 1894년 정수론학자 파울 바흐만이 그의 책 "Analytische Zahlentheorie" (해석적 수론) 2권에서 처음 도입했다.^[1] 정수론학자 에드문트 란다우가 이를 채택했고, 1909년에 o 표기법을 도입하는 데 영감을 얻었다.^[2] 따라서 둘 다 현재 란다우 기호라고 불린다. 이 표기법들은 1950년대에 점근 해석을 위해 응용 수학에서 사용되었다.^[22] 기호 ${\displaystyle \Omega }$(“~의 o가 아님”이라는 의미에서)는 1914년 하디와 리틀우드에 의해 도입되었다.^[12] 하디와 리틀우드는 또한 1916년에 ${\displaystyle \Omega _{R}}$(“오른쪽”)과 ${\displaystyle \Omega _{L}}$(“왼쪽”) 기호를 도입했다.^[13] 이 ${\displaystyle \Omega }$ 표기법은 적어도 1950년대부터 정수론에서 다소 일반적으로 사용되었다.^[23]

${\displaystyle \sim }$ 기호는 이전에 다른 의미로 사용되었지만,^[21] 1909년 란다우^[2]와 1910년 하디^[5]에 의해 현대적인 정의가 주어졌다. 하디는 그의 논문의 같은 페이지 바로 위에서 ${\displaystyle \asymp }$ 기호를 정의했으며, 여기서 ${\displaystyle f(x)\asymp g(x)}$는 ${\displaystyle f(x)=O(g(x))}$와 ${\displaystyle g(x)=O(f(x))}$가 모두 만족됨을 의미한다. 이 표기법은 현재도 해석적 수론에서 사용되고 있다.^{[24] [10]} 하디는 그의 논문에서 ${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$ 기호를 제안했는데, 여기서 ${\displaystyle f\mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g}$는 어떤 상수 ${\displaystyle K\not =0}$에 대해 ${\displaystyle f\sim Kg}$임을 의미한다 (이는 보아-레이몬드의 ${\displaystyle f\sim g}$ 표기법에 해당한다).

1930년대, 비노그라도프^[6]는 ${\displaystyle f(x)\ll g(x)}$와 ${\displaystyle g(x)\gg f(x)}$ 표기법을 대중화시켰는데, 이 둘은 모두 ${\displaystyle f(x)=O(g(x))}$를 의미한다. 이 표기법은 해석적 수론에서 표준이 되었다.^[4]

1970년대에 도널드 커누스가 빅-O를 컴퓨터 과학에서 대중화시켰고, 하디의 ${\displaystyle f(x)\asymp g(x)}$에 대해 ${\displaystyle f(x)=\Theta (g(x))}$라는 다른 표기법을 제안했으며, 하디와 리틀우드 오메가 표기법에 대해 다른 정의를 제안했다.^[7]

하디는 ${\displaystyle \preccurlyeq }$ 기호를 도입했고, 1910년 논문 "Orders of Infinity"에서 보아-레이몬드의 ${\displaystyle \prec }$(및 이미 언급된 다른 기호들)를 옹호했지만,^[5] 세 편의 논문(1910–1913)에서만 사용했다. 그의 거의 400편에 달하는 나머지 논문과 책에서는 란다우 기호 O와 o를 일관되게 사용했다.^[25] 하디의 기호 ${\displaystyle \preccurlyeq }$와 ${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$는 더 이상 사용되지 않는다.

표기법 문제

화살표

수학에서 ${\displaystyle x\to \infty }$와 같은 표현은 극한의 존재를 나타낸다. 빅-O 표기법과 관련 표기법인 ${\displaystyle \Omega ,\Theta ,\gg ,\ll ,\asymp }$에는 스몰-o, ${\displaystyle \sim }$, ${\displaystyle \omega }$ 표기법과 달리 암시된 극한이 없다. ${\displaystyle f(x)=O(g(x))\;\;(x\to \infty )}$와 같은 표기법은 기호의 남용으로 간주될 수 있다.

등호

어떤 이들은 ${\displaystyle f(x)=O(g(x))}$를 기호의 남용으로 간주한다. 등호의 사용이 이 진술이 가지지 않는 대칭성을 암시하여 오해의 소지가 있기 때문이다. 드 브라윈이 말했듯이, ${\displaystyle O(x)=O(x^{2})}$는 참이지만 ${\displaystyle O(x^{2})=O(x)}$는 참이 아니다.^[26] 커누스는 이러한 진술을 "단방향 등식"이라고 설명한다. 왜냐하면 양변을 뒤집을 수 있다면, "우리는 ${\displaystyle n=O(n^{2})}$와 ${\displaystyle n^{2}=O(n^{2})}$라는 항등식으로부터 ${\displaystyle n=n^{2}}$와 같은 터무니없는 것을 추론할 수 있기 때문"이다.^[27] 다른 편지에서 커누스는 또한 다음과 같이 지적했다.^[28]

등호는 그러한 표기법에 대해 대칭적이지 않다. [이 표기법에서] 수학자들은 관습적으로 '=' 기호를 영어에서 'is'라는 단어를 사용하듯이 사용한다. 아리스토텔레스는 남자이지만, 남자가 반드시 아리스토텔레스는 아니다.

이러한 이유로 일부는 집합론적 표기법을 사용하고 ${\displaystyle f(x)\in O(g(x))}$라고 쓰도록 옹호한다. "${\displaystyle f(x)}$는 ${\displaystyle O(g(x))}$의 원소이다" 또는 "${\displaystyle f(x)}$는 ${\displaystyle O(g(x))}$ 집합에 있다" – 라고 읽으며, ${\displaystyle O(g(x))}$를 ${\displaystyle h(x)=O(g(x))}$를 만족하는 모든 함수 ${\displaystyle h(x)}$의 클래스로 생각한다.^[27] 그러나 등호의 사용은 관례적이며^[26][27] 다음과 같은 더 복잡한 표현에서 더 편리하다. $${\displaystyle f(x)=g(x)+O(h(x))=O(k(x)).}$$

정수론에서 널리 사용되는 비노그라도프 표기법 ${\displaystyle \ll }$과 ${\displaystyle \gg }$는^[9][4][10] 이러한 결함이 없다. 이는 빅-O가 등식보다는 부등식을 나타냄을 더 명확하게 보여주기 때문이다. 또한 빅-O 표기법이 부족한 대칭성을 즐긴다. ${\displaystyle f(x)\ll g(x)}$는 ${\displaystyle g(x)\gg f(x)}$와 동일한 의미이다. 조합론과 컴퓨터 과학에서는 이러한 표기법이 거의 보이지 않는다.^[3]

조판

빅-O는 이탤릭체 대문자 "O""로 조판되며, 다음 예시와 같다: ${\displaystyle O(n^{2})}$.^[29][30] TeX에서는 수학 모드 안에서 단순히 'O'를 입력하면 생성된다. 그리스어 이름의 바흐만-란다우 표기법과 달리 특별한 기호가 필요하지 않다. 그러나 일부 저자는 대신 필기체 변형 ${\displaystyle {\mathcal {O}}}$를 사용한다.^[31][32]

빅-O는 원래 "order of"("Ordnung", Bachmann 1894)를 의미하며, 따라서 라틴 문자이다. 바흐만도 란다우도 이를 "Omicron"이라고 부른 적이 없다. 이 기호는 훨씬 나중에(1976년) 커누스에 의해 대문자 오미크론으로 간주되었는데,^[7] 아마도 Omega 기호에 대한 그의 정의와 관련이 있을 것이다. 숫자 0은 사용해서는 안 된다.

같이 보기

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