빅 O 표기법

적합 근사
개념
근사 순서 스케일 분석 · 빅 O 표기법 곡선 피팅 · 오정밀 유의한 수치
기타 기초
근사치 · 일반화 오류 테일러 다항식 과학적 모델링
v t

빅 O 표기법은 인수가 특정 값 또는 무한대로 향하는 경우 함수의 제한 동작을 설명하는 수학 표기법입니다.Big O는 Paul Bachmann,^[1] Edmund Landau,^[2] 그리고 다른 사람들에 의해 발명된 표기법의 일종으로, 집합적으로 Bachmann-Landau 표기법 또는 점근 표기법이라고 불립니다.문자 O는 바흐만에 의해 Ordnung의 약자로 선택되었고, 이는 근사 순서를 의미합니다.

컴퓨터 과학에서 빅 O 표기법은 입력 크기가 ^[3]커짐에 따라 실행 시간 또는 공간 요구 사항에 따라 알고리즘을 분류하는 데 사용됩니다.해석수 이론에서, 빅 O 표기법은 종종 산술 함수와 더 잘 이해된 근사치 사이의 차이에 대한 경계를 표현하기 위해 사용된다; 그러한 차이의 유명한 예는 소수 정리의 나머지 항이다.Big O 표기법은 유사한 추정치를 제공하기 위해 다른 많은 필드에서도 사용됩니다.

Big O 표기법은 함수의 성장률에 따라 특징지을 수 있습니다.동일한 성장률을 가진 다른 함수는 동일한 O 표기법을 사용하여 나타낼 수 있습니다.함수의 성장률을 함수의 순서라고도 하기 때문에 문자 O가 사용됩니다.빅 O 표기법의 관점에서 함수에 대한 설명은 일반적으로 함수의 성장률에 대한 상한만 제공합니다.

Big O 표기법과 관련된 몇 가지 표기는 점근 성장률에 대한 다른 종류의 경계를 나타내기 위해 기호 o, ,, ,를 사용한다.

형식적 정의

추정할 함수인 f를 실수 또는 복소수 가치 함수로 하고 비교 함수인 g를 실수 가치 함수로 한다.두 함수는 모두 양의 실수의 무제한 서브셋에 $정의$되며${\displaystyle g}$($$x ) {$displaystyle g($x)}는$$ ^[4]x의 충분히 큰 모든 값에 대해 엄밀하게 양의 함수가 됩니다. 1은 씁니다.

f$x)$ {style f${\displaystyle (}$$x)}$의 절대값이 g$)$ {$display style$ g$(x)}$의 $양$의 정수 배수인 경우.$즉{\displaystyle ,}$ f (${\displaystyle x}$ ) ${\displaystyle =O}$ (${\displaystyle g}$ (${\displaystyle x}$)$$\ $displaystyle$ f$(x$) $=$$O{\bigl(}g(x){\bigr}}:$ 다음과$$ 같은 양의 실수 M과 실수₀ x가 존재하는 경우

많은 문맥에서 변수 x가 무한대로 갈 때 우리가 성장률에 관심이 있다는 가정은 기술되지 않은 채로 남겨지고, 누군가는 더 간단하게 다음과 같이 씁니다.

이 표기법은 또한 어떤 실수 a(종종 a = 0)에 가까운 f의 동작을 설명하는 데 사용할 수 있습니다.0< - < \ $displaystyle$0 < x - a \ delta인 모든 x에 대해 $양수{\displaystyle }$ ${\$ { $displaystyle$ \ $delta$$$$}$ 및 M이 존재하는 경우 a에 충분히 가까운 x의 값에 대해 g(x)가 0이 아닌 것으로 선택되기 때문에 다음 두 정의를 모두 상한값을 사용하여 통합할 수 있습니다.한다면

컴퓨터 과학에서는 조금 더 제한적인 정의가 일반적이다.$f{\displaystyle }$ {\$displaystyle$ f$}$와$$g {\$displaystyle$ g$}$는 모두 양의 정수에서 음이 아닌 실수까지의 함수여야 한다.${\displaystyle }f{\displaystyle }$ (${\displaystyle x}$ )${\displaystyle =O}$ (${\displaystyle x}$) {$displaystyle$f ($x$ $=$$O{\bigl(}g(x){\bigr}}:$ 모든$$ $n{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}${ $displaystyle$ $n$$\geq n_{0$^[5] 에 대해 f${\displaystyle (n)}$m ${\displaystyle M}$ ${\displaystyle g}$(${\displaystyle n}$)\$displaystyle$ f$(n)\leq$Mg($n)}$ 의$$ $정수{\displaystyle }$ M 및 n이₀ 정의되어 있는 경우필요한 경우 n을 충분히 크게 선택하여₀ f ${\$$displaystyle$ f$\}$s $및{\displaystyle }$g {\$displaystyle$ g$\}$의 도메인에서 $유한$한 범위를 제외합니다(예를 들어 log${\displaystyle }$) (${\displaystyle n}$) {$displaystyle \log ( n$ )는 n ${\displaystyle =}$ {$displaystyle$ n=$0}$에서 정의되지 않습니다).$$

예

일반적으로 O 표기법은 점근적, 즉 매우 큰 x를 나타냅니다.이 설정에서는 "가장 빠르게" 증가하는 용어의 기여는 결국 다른 용어와 무관하게 됩니다.따라서 다음과 같은 단순화 규칙을 적용할 수 있습니다.

• f(x)가 여러 항의 합계인 경우, 가장 큰 증가율이 있는 항이 있으면 f(x)를 유지하고 다른 항은 모두 생략할 수 있다.
• f(x)가 여러 인자의 곱이면 상수(x에 의존하지 않는 제품의 항)를 생략할 수 있습니다.

예를 들어, f(x) = 6x⁴ - 2x³ + 5라고 가정하고, O 표기법을 사용하여 이 함수를 단순화하여 x가 무한대에 가까워질 때 증가율을 설명한다고 가정합니다.이 함수는 6x⁴, -2x³ 및 5의 세 가지 항의 합입니다.이 세 항 중 가장 높은 증가율을 보이는 항은 x의 함수로 가장 큰 지수인 6배이다⁴.이제 두 번째 규칙을 적용할 수 있습니다. 6x는⁴ 첫 번째 인자가 x에 의존하지 않는 6과⁴ x의 곱입니다. 이 인자를 생략하면 x가⁴ 단순해집니다.따라서, 우리는 f(x)가 x의⁴ "큰 O"라고 말한다. 수학적으로, 우리는 f(x) = O(x⁴)라고 쓸 수 있다.f(x) = 6x⁴ - 2x³ + 5 및 g(x) = x⁴. 위의 공식 정의를 적용하여 f(x) = O(x⁴)가 팽창과 동등하다는 문구를 사용하여 이 계산을 확인할 수 있다.

x와 M의₀ 적절한₀ 선택과 모든 x > x의 경우. 이를 증명하려면 x = 1 및 M = 13으로 한다₀.다음으로 모든 x > x₀:그렇게

사용.

Big O 표기법에는 주로 다음 두 가지 영역이 있습니다.

• 수학에서, 특히 잘린 테일러 급수나 점근 팽창의 경우, 유한 급수가 주어진 함수에 얼마나 가깝게 근접하는지를 기술하는 데 일반적으로 사용된다.
• 컴퓨터 과학에서, 그것은 알고리즘의 분석에 유용하다.

두 응용 프로그램 모두에서, O(·) 내에 나타나는 함수 g(x)는 일반적으로 가능한 한 단순하게 선택되며, 상수 인자와 낮은 차수의 항을 제외한다.

이 ^{[citation needed]}표기법에는 형식적으로는 가깝지만 현저하게 다른 두 가지 용도가 있습니다.

• 무한 점근율
• 미량 점근율

그러나 이러한 구별은 적용상에만 있으며 원칙적으로는 그렇지 않다. 즉, "빅 O"에 대한 공식 정의는 두 경우 모두 동일하며 기능 ^{[original research?]}인수에 대한 제한만 다를 뿐이다.

무한 점근율

빅 O 표기법은 알고리즘의 효율을 분석할 때 유용합니다.예를 들어, 크기 n의 문제를 완료하는 데 걸리는 시간(또는 단계 수)은 T(n) = 4n² - 2n + 2인 것으로 밝혀질 수 있습니다. n이 커지면 n항이² 지배하게 되므로 다른 모든 항이 무시될 수 있습니다. 예를 들어 n = 500일 때, 4n항은² 2n항만큼 1000배입니다.후자를 무시하면 대부분의 경우 식 값에 거의 영향을 미치지 않습니다.또한, 항³ n 또는⁴ n을 포함하는 식과 같은 다른 식 순서와 비교하면 계수는 무관하게 된다.T(n) = 1,000,000n일지라도² U(n) = n일³ 경우 n이 1,000,000(T(1,000,000) = 1,000,000³ = U(1,000,000))보다 커지면 후자는 항상 전자를 초과한다.또한 스텝 수는 알고리즘이 실행되는 머신모델의 상세 내용에 따라 달라지지만 일반적으로 알고리즘 실행에 필요한 스텝 수에 따라 다양한 유형의 머신이 일정하게 변화합니다.따라서 빅 O 표기법은 남은 내용을 캡처합니다.

${\displaystyle T(n)=O(n^{2})}$

또는

${\displaystyle T(n)\in O(n^{2})}$

그리고 알고리즘이 n개의 시간 복잡성을 갖는다고² 가정합니다.기호 "="는 일반적인 수학적인 의미에서 "같다"는 것을 의미하는 것이 아니라 보다 구어체적인 "is"를 의미하는 것이므로, 두 번째 표현은 더 정확하다고 여겨지기도 한다(아래의 "같다" 논의 참조). 반면 첫 번째 표현은 ^[6]일부에서는 표기법의 오용이라고 여겨지기도 한다.

무한소수 점근율

빅 O는 오차항을 수학적 함수에 대한 근사치로 설명하는 데 사용할 수도 있습니다.가장 유의한 항은 명시적으로 작성된 다음 가장 유의하지 않은 항은 단일 빅 O 항으로 요약됩니다.예를 들어 x가 작을 때 유효한 지수 급수와 그 두 식을 생각해 보겠습니다.

${\displaystyle {x}e^{x}&=1+x+{\frac {x^{2}}{2!}+{\frac {x^{3}}}{3!}+{\frac {x^{4}}{4}!}+\text{모든 }}x\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as}}x\to0\[4pt]=1+x+O(x{2})&{\text{x}\end}}}}x\aligned$

두 번째 식(O(x³)이 있는 식)은 오류^x e - (1 + x + x²/2)의 절대값이 x가 0에 충분히 가까울 때 일부 상수 곱하기³ x임을 의미합니다.

특성.

함수 f를 다른 함수의 유한합으로 쓸 수 있다면 가장 빠르게 성장하는 함수에 따라 f(n)의 순서가 결정된다.예를들면,

$\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {text{as}n\to\infty}$

특히, 함수가 n에서 다항식으로 제한될 수 있다면, n은 무한대 경향이 있기 때문에 다항식의 하위 항을 무시할 수 있다.세트 O(n^c)와 O(cⁿ)는 크게 다릅니다.c가 1보다 크면 후자는 훨씬 빠르게 성장합니다.어떤 c에서도 n보다 빠르게 증가하는^c 함수를 초다항함수라고 합니다.c 형식의ⁿ 지수 함수보다 느리게 성장하는 함수를 서브 지수 함수라고 합니다.알고리즘은 초다항식 및 준지수 둘 다의 시간을 필요로 할 수 있습니다.이 알고리즘의 예로는 정수 인수분해를 위한 가장 빠른 알고리즘과 함수^{log n} n이 있습니다.

로그 안에 있는 n의 거듭제곱은 무시할 수 있습니다.세트 O(log n)는 O(log(n^c)와 완전히 동일합니다.로그는 상수 인자(log(n^c) = c log n이므로)로만 다르므로 큰 O 표기법은 이를 무시합니다.마찬가지로 상수가 다른 로그도 동일합니다.반면, 서로 다른 기수를 갖는 지수들은 같은 순서가 아닙니다.예를 들어, 2와ⁿ 3은 같은ⁿ 순서가 아닙니다.

단위를 변경하면 결과 알고리즘의 순서에 영향을 줄 수도 있고 그렇지 않을 수도 있습니다.단위를 변경하는 것은 해당 변수에 상수를 곱하는 것과 같습니다.예를 들어 알고리즘이 n의 순서로² 실행되는 경우 n을 cn으로 대체하면 알고리즘이 cn의 순서로²² 실행되는 것을 의미하며 빅O 표기법에서는 상수² c가 무시됩니다.이것은 cn = O(n²)로²² 쓸 수 있습니다.그러나 알고리즘이 2의 순서로ⁿ 실행되는 경우 n을 cn으로 대체하면 2 ⁿ= (2)가^cnc 됩니다.이것은 일반적으로 2와 같지ⁿ 않다.변수를 변경하면 결과 알고리즘의 순서에도 영향을 줄 수 있습니다.예를 들어 입력번호 x의 자릿수 n으로 측정했을 때 알고리즘의 실행시간이 O(n)이면 n=O(log x)이므로 입력번호 x 자체의 함수로 측정했을 때 알고리즘의 실행시간은 O(log x)가 된다.

제품.

${\displaystyle f_{1}=O(g_{1}){\text{및 }}f_{2}=O(g_{2})\오른쪽 화살표 f_{1}f_{2}=O(g_{1}g_{2}}}$

${\displaystyle f(g)=O(fg)}$

합

${\displaystyle {f\mathrm{}}_{}}$ 1 $=$ ( g${\displaystyle {}_{}{1\mathrm{}}_{}}$ )$$（ { $displaystyle f$$_${ 1$$$$} ${\displaystyle {}_{}}$ O ( ${\displaystyle {g\mathrm{}}_{}}$ _ {$$1} )$$} 、 ${\displaystyle {f\mathrm{}}_{}}$ ${\displaystyle 2}$ $=$ O ($g$_ {$$2} )인 $경우{\displaystyle {}_{}}$ ${\displaystyle {f\mathrm{}}_{}}$1 + ${\displaystyle {f\mathrm{}}_{}}$ 2 $=$ (${\displaystyle }$max ( ${\displaystyle {g\mathrm{}}_{}}$ ${\displaystyle {}_{}}$, ${\displaystyle {}_{}{2\mathrm{}}_{}}$)$${ $displaystyle$ f _ {$1$ + f _ { 1 + f _ { 1 } $f$( $max$)$displaystyle f_{2}=O(g)}$ $다음$ ${\displaystyle {f1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {f2\mathrm{}}_{}o}$O (${\displaystyle g}$ $){display f_{1$}+$f_{2}\in$ O$(g$ 즉, 이 두 번째 문장은 O${\displaystyle }$($){displaystyle$ O$(g)}$가 볼록 원뿔임을 $나타냅니다{\displaystyle }$.

상수에 의한 곱셈

k를 0이 아닌 상수라고 합니다.$다음$으로 O${\displaystyle (k\mathrm{kg})}$ ${\displaystyle =}$ ${\displaystyle O(g)}${$displaystyle$ O$(k\cdot$ g)=$O(g$ $즉{\displaystyle }$, f ${\displaystyle =}$ ${\displaystyle O(g}$$)$ {$displaystyle$ f$=$$)}.$ {$displaystyle$ k$\cdot$ f$=O(g$)}.$}$

다중 변수

Big O(및 little O, δ 등)는 여러 변수와 함께 사용할 수도 있습니다.여러 변수에 대해 공식적으로 빅 O를 정의하려면 f$\displaystyle$f와$$ $\$$displaystyle g$가 R ${\displaystyle {}^{}}$의$일부$ 서브셋에 정의되어 있다고 $가정$합니다$.$

${\displaystyle f(\mathbf {x}){\text{는 }O(g(\mathbf {x})}\quad {\text}\mathbf {x}\to\infty}}$

만약을 경우에만 상수 M{M\displaystyle}, C>0{\displaystyle C>0}가 모든){\displaystyle \mathbf{)}}에 x과 f())≤ Cg()){\displaystyle f(\mathbf{x})\leq Cg(\mathbf{x})}나는 ≥ M{\displaystyle x_{나는}\geq M}일부.{\dis을 위해 존재한다.playst$yle$ i$.}$ 마찬가지로$$^[7] 일부 $(\displaystyle$ i$)$에 ${\displaystyle {대해}_{}}$ $M$$displaystyle x_{i}\$geq M$)$을 ${\displaystyle 입력}$할 수 있습니다$.{\displaystyle }$여기서${\displaystyle x-style\mathbf{}}$$\mathbf {x} \geQ$ M은${\displaystyle {}_{}}$x-style $\$ {$x}$ \mathbstyle {x} \mathbstyle {$xf}$ \mathm} \mathm}입니다.예를 들어, 스테이트먼트

${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad {}n,m\to\infty}$

C와 M의 상수가 존재한다고 단언하다

$(\displaystyle f(n,m)-(n^{2}+m^{3}) \leq C n+m }$

${\displaystyle$ m$\geq$ M$}$ $또는$ n $displaystyle$ n$\geq$ M$}$이(가) 유지되면 언제든지 사용할 수 있습니다.이 정의를 사용하면 x$${\$displaystyle \mathbf {x}}$의 모든 좌표가 무한대로 증가할 수 있습니다.특히, 성명서는

$\displaystyle f(n,m)=O(n^{m})\quad {텍스트}n,m\to\infty}$

(예:${\displaystyle \mathrm{}}$"${\displaystyle C"\mathrm{}}$ "M${\displaystyle "\mathrm{}}$ "${\displaystyle n"\mathrm{}}$ "$"$ "{$displaystyle\exists$ C$,\exists$ M$,\forall$ n$,\forall$ m$,\cdots$는 와는 크게 다릅니다.

$\displaystyle \forall m\infty ~f(n,m)=O(n^{m})\quad {text}n\to\infty}$

(예:${\displaystyle \mathrm{}}$"${\displaystyle m"\mathrm{}}$ "${\displaystyle C"\mathrm{}}$ "M${\displaystyle "\mathrm{}}$ "${\displaystyle n}$" "$n"$ "{displaystyle $\forall$ m$,\exists$ C$,\exists$ M$,\forall$ n$,\cdots})$

이 정의에서 함수가 정의된 부분 집합은 일변량 설정에서 다변량 설정으로 문장을 일반화할 때 유의합니다.예를 들어 f${\displaystyle (n,}$ ${\displaystyle m)}$ ${\displaystyle =}$ $1{\displaystyle }$$${\$displaystyle$ f$(n$${\displaystyle ,}$ ${\displaystyle m)}$ ${\displaystyle =n}${$displaystyle$ g$(n,$m) $= n$ $\}$이면 $f{\displaystyle (n,}$ $m$ ${\displaystyle =}$ ${\displaystyle O(n,}$ $)$ {$display$ f$(n,$m) $= O(n,$ m$)$ styledisplay$$f(g$,$ m) } $style$ $($f f(f, $m{\displaystyle }$) =$n$, m )[ ${\displaystyle 0}$, "${\displaystyle \mathrm{}{}^{}}$ {\$displaystyle [0$, \$infty$)^{$2$${\displaystyle }$에 정의되어 있습니다.

빅 O를 다변량 함수로 일반화한 것은 이것뿐만이 아니며,^[8] 실제로 정의 선택에 불일치가 있습니다.

표기 사항

등호

위에서 정의한 "f(x) is O(g(x)" 문장은 일반적으로 f(x) = O(g(x)로 작성된다.어떤 사람들은 등호 부호의 사용은 이 문장이 갖지 못한 대칭성을 시사하기 때문에 이것을 표기법의 남용이라고 생각한다.de Bruijn이 말했듯이, O(x) = O(x²)는 참이지만 O²(x) = O(x)^[9]는 아니다.만약 양측이 번복 될 수 있기 때문에, 또 하나의 편지"우리는 정체성 n에서 O(n2 cm이고 n2)O(n2)=nxn2처럼 바보 같은 추론할 수 있다."[10]에서 크누스 또한, 이 표기법에서,"cus 수학자들이"는 등호 그런 표기에 대해서 대칭이 아니다"을 지적했다 크누스"일방 equalities"로, 같은 발언들에 대해 설명합니다.tomarily 영어에서 "is"라는 단어를 사용할 때 = 기호를 사용합니다. 아리스토텔레스는 남자지만, 사람이 반드시 아리스토텔레스는 아닙니다.^[11]

이러한 이유로, 집합 표기법을 사용하여 f(x) g O(g(x)로 표기하는 것이 보다 정확할 것입니다. 즉, "f(x)는 O(g(x)의 요소" 또는 "f(x)는 O(g(x)의 집합 O(x)에 있다"라고 읽습니다.단,^[9][10] 등호 사용은 관례입니다.

기타 연산자

빅 O 표기법은 더 복잡한 방정식의 다른 산술 연산자와 함께 사용할 수도 있습니다.예를 들어, h(x) + O(f(x))는 h(x)의 성장을 갖는 함수의 집합과 f(x)의 성장으로 제한된 부분을 의미한다.따라서,

$\displaystyle g(x)=h(x)+O(f(x))}$

와 같은 것을 나타내다

$\displaystyle g(x)-h(x)=O(f(x)).}$

예

n개의 요소 집합에서 작동하도록 알고리즘이 개발되고 있다고 가정합니다.개발자들은 입력 집합의 요소 수를 기준으로 알고리즘이 실행되는 데 걸리는 시간을 나타내는 함수 T(n)를 찾는 데 관심이 있습니다.알고리즘은 먼저 서브루틴을 호출하여 세트 내의 요소를 정렬한 후 자체 연산을 수행합니다.정렬의 시간 복잡도는 O(n²)로 알려져 있으며 서브루틴이 실행된 후 알고리즘은 종료되기 전에 55n³ + 2n + 10단계를 수행해야 합니다.따라서 알고리즘의 전체 시간 복잡도는 T(n) = 55n³ + O(n²)로 표현될 수 있다.여기서 2n + 10이라는 용어는 빠르게 성장하는 O(n²)에 포함된다.이 사용법은 "=" 기호의 형식적 의미 중 일부를 무시하지만, 일종의 편리한 자리 표시자로 큰 O 표기법을 사용할 수 있습니다.

다용도

좀 더 복잡한 용법에서는 O(·)가 방정식의 다른 위치에 나타날 수 있으며, 각 변에 여러 번 나타날 수도 있습니다.예를 들어, n ${\displaystyle \to }$ $∞$ \ $displaystyle n$ \ $to$\ infty $\}$ 의 $경우$는 다음과 같습니다.

이러한 문장의 의미는 다음과 같다. 왼쪽의 각 O(·)를 만족하는 함수에 대해 오른쪽의 각 O(·)를 만족하는 함수가 있으므로, 이 모든 함수를 방정식으로 대입하면 두 변이 같아진다.예를 들어, 위의 세 번째 방정식은 "어떤 함수 f(n) = O(1)에 대하여, n = g(n)와^f(n) 같은 함수 g(n) = Oⁿ(e)가 존재한다"는 것을 의미한다. 위의 "집합 표기법"에서, 왼쪽이 나타내는 함수 클래스가 오른쪽이 나타내는 함수 클래스의 부분 집합이라는 것을 의미한다.이 용도에서 "="는 일반적인 "=" 사용과는 달리 대칭 관계가 아닌 형식 기호이다.따라서^O(1) 예를 들어 n = O(eⁿ)는 거짓 진술 O(eⁿ) = n을^O(1) 의미하지 않습니다.

조판

$빅{\displaystyle }$ O는 O${\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$ 2$$) \ $displaystyle$ O$(n^{2$^[12][13] 의 예시와 같이 이탤릭체로 대문자로 "O" 라고 타이프 세트로 되어 있습니다.TeX 에서는 연산 모드에서 O 를 입력하기만 하면 됩니다.그리스 이름인 바흐만-란다우 표기법과 달리 특별한 기호가 필요하지 않습니다.$그러나$ 일부 작가들은 ^[14][15]서예$변종{\displaystyle \mathcal{}}$O를 $대신$ 사용한다$.$

공통 기능 순서

다음은 알고리즘 실행 시간을 분석할 때 일반적으로 발생하는 함수 클래스 목록입니다.두 경우 모두 c는 양의 상수이고 n은 경계 없이 증가합니다.일반적으로 성장이 느린 기능이 먼저 나열됩니다.

표기법	이름.	예
${\displaystyle O(1)}$	일정한	이진수가 짝수인지 홀수인지 판단; 계산${\displaystyle }$(-${\displaystyle 1{}^{}}$ $\$ 고정 크기 조회 테이블 사용
${\displaystyle O(\log \log n)}$	이중 로그	균등하게 분포된 값의 정렬된 배열에서 보간 검색을 사용하여 항목을 찾는 데 소요된 평균 비교 수
${\displaystyle O(\log n)}$	로그의	이진 검색 또는 균형 잡힌 검색 트리와 이항 힙의 모든 작업을 사용하여 정렬된 배열에서 항목 찾기
${\displaystyle O(\log n)^{c}}$ ${\textstyle c>1}$	다산술의	매트릭스 체인 순서는 병렬 랜덤 액세스 머신 상에서 다산술 시간에 해결할 수 있다.
${\displaystyle O(n^{c}}$ ${\textstyle 0<c<1}$	분수 검정력	k-d 트리에서 검색
${\displaystyle O(n)}$	선형의	정렬되지 않은 목록 또는 정렬되지 않은 배열에서 항목 찾기, 리플 자리올림으로 두 개의 n비트 정수 추가
${\displaystyle O(n\log ^{*}n}}$	n 로그스타 n	자이델 알고리즘 또는 합집합-찾기 알고리즘을 사용하여 단순 폴리곤의 삼각측량을 수행합니다."" " ( ) {0 , 1+ "( "n )> { $displaystyle \log$^ { * * } ( n ) $= syslog${$cases$}0 , & ${$ \ $text$ { if } $n$\ $leq$ 1 \ 1 \$1$ + \ log ^ * } , \ $log$（$n }$ > { n } ） } } } } $。$
$(\displaystyle O(n\log n)=O(\log n!))$	선형, 로그 선형, 준선형 또는 "n log n"	고속 푸리에 변환 수행, 가능한 가장 빠른 비교 정렬, 힙소트 및 병합 정렬
${\displaystyle O(n^{2})}$	이차적인	두 개의 n자리 숫자에 교재 곱셈, 버블 정렬, 선택 정렬 및 삽입 정렬과 같은 단순한 정렬 알고리즘, 퀵 정렬, 셸 정렬, 트리 정렬과 같은 보통 더 빠른 정렬 알고리즘에 바인딩된 (최악의 경우)
${\displaystyle O(n^{c}}$	다항식 또는 대수적	트리 결합 문법 구문 분석, 초당 그래프에 대한 최대 일치, LU 분해로 결정 요인 찾기
${\displaystyle L_{n}[\alpha,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln n)^{1-\alpha }}$ ${\textstyle 0<\alpha<1}$	L 주석 또는 하위 지수	2차 체 또는 숫자 필드 체를 사용하여 숫자 인수분해
${\displaystyle O(c^{n})}$ ${\textstyle c>1}$	지수적	동적 프로그래밍을 사용하여 출장 중인 세일즈맨 문제에 대한 (정확한) 해결책을 찾고, 브루트 포스 검색을 사용하여 두 개의 논리문이 동일한지 확인
${\displaystyle O(n)!}$	요인	무차별 검색을 통해 이동 중인 세일즈맨 문제 해결, 포셋의 모든 제한 없는 배열 생성, Laplace 확장으로 결정 요인 찾기, 세트의 모든 파티션 열거

$문{\displaystyle }$ f${\displaystyle }$(${\displaystyle n}$ ) ${\displaystyle =O}$ ( ${\displaystyle n!}$ )$${$displaystyle$ f$(n$)=$O(n!)}$는 f${\displaystyle }$(${\displaystyle n)}$ $=$${\displaystyle O}$ ($)$ {$displaystyle$ f(n)=로 약해지는 경우가 $있습니다{\displaystyle }$.$O\$left$(n^{n}\right)$ 점근$$ 복잡성에 대한 간단한 공식을 도출합니다.어떤 k>로 O(n댁+ε){O(n^{c+\varepsilon})\displaystyle}의 어떤ε 을에 0{\displaystyle k>0}c>0{\displaystyle c>0}, O(소음 한계(통나무⁡ n)k={\displaystyle O(n^{c}(n\log)^{km그리고 4.9초 만})}하위 집합;0{\displaystyle \varepsilon>0} 있는데요, 다항식으로 간주될 수 있다.더 큰 order.

관련 점근 표기법

Big O는 컴퓨터 공학에서 널리 사용된다.다른 관련 표기와 함께 바흐만-란다우 ^{[citation needed]}표기의 패밀리를 형성한다.

리틀오 표기법

직관적으로, "f(x) is o(g(x)" ("f(x) is little-o of g(x)" ("f(x) is little-o of g(x)")는 f(x)보다 훨씬 빠르게 성장한다는 것을 의미한다.앞의 f가 실수 또는 복소수 값 함수이고 g가 실수 값 함수로 정의되어 g(x)가 충분히 큰 x의 모든 값에 대해 엄밀하게 양의 함수로 정의된다고 가정하자.

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

모든 양의 상수 θ에 대해 다음과 같은 $상수{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 0$(\$이 존재하는 경우

$\displaystyle f(x) \leq \varepsilon g(x)\display { text { for }x\geq x_{0}.}$^[16]

예를 들면,

${\displaystyle 2}$ x ${\displaystyle =o}$ ( ${\displaystyle {}^{}{2\mathrm{}}^{}}$) { $style 2x = o$ ( x$$^ {$2}$ )$및$ 1 / ${\displaystyle x}$ $=$ (${\displaystyle }$1${\displaystyle }$) ,$${ $displaystyle$1/x →$o$ ($$1 )는$$ 모두 x ${\displaystyle \to }$ $displaystyle .\to$\$infty .$ } $로서{\displaystyle }$ ${\displaystyle \mathrm{사용}}$됩니다.

big-O 표기법과 little-o의 정의의 차이는 전자는 적어도 하나의 상수 M에 대해 참이어야 하지만 후자는 아무리 ^[17]작더라도 모든 양의 상수 θ에 대해 유지되어야 한다는 것이다.이와 같이 little-o 표기법은 대응하는 big-O 표기법보다 강력한 표현을 합니다.g의 little-o인 모든 함수도 g의 big-O이지만 g의 big-O인 모든 함수도 g의 little-o인 것은 아닙니다.$예$를 들어 ${\displaystyle {}^{}}$ x ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}O}$ ( ${\displaystyle {}^{}{2\mathrm{}}^{}}$) { $displaystyle 2x$$^{$$2$} $= O$ ($x^{2}$ ) $2$ ${\displaystyle {}^{}}$ $x$ 2${\displaystyle {}^{}\mu {}^{}}$ ( x${\displaystyle {}^{}{2\mathrm{}}^{}}$) \ $neq$o ( $x$^ {2}$$} 。

g(x)가 0이 아니거나 적어도 특정 지점을 넘어서 0이 아니므로 f${\displaystyle }$(${\displaystyle x}$ ) $=$ (${\displaystyle g}$ (${\displaystyle x}$) {$displaystyle$ f$(x$)=$o(g(x)}$ )의$$ 관계는 $다음$과 같습니다.

${\displaystyle \underset{}{lim}}$ x ${\displaystyle \underset{}{\to }}$ ${\displaystyle \underset{}{\mathrm{\infty }}\frac{}{}\underset{}{}\frac{}{}}$ (${\displaystyle \frac{x}{}}$ )${\displaystyle \frac{}{}}$ (${\displaystyle \frac{x}{}}$ ) $=$ \ $displaystyle \lim$_ {$x\to \infty$}{\$frac {f(x)}{g(x$)}=$0}$ (실제로 이것이 Landau가 little-o 표기법을 정의한 방법입니다^[16]).

Little-o는 많은 산술 연산을 존중한다.예를들면,

c가 0이 아닌 $상수$이고 f ${\displaystyle =o}$ (${\displaystyle g}$) { $displaystyle$ f $=$${\displaystyle o}$ ($g$ )$$}인 경우 c${\displaystyle =o}$( g ) { $displaystyle c\cdot$ f$=o$( g )$$。

f ${\displaystyle =o}$($F)$ {$style$ f$=o(F)}$ 및$$ $g{\displaystyle }$ ${\displaystyle =o}$($)$ {$display style$ g${\displaystyle =o}$$(G)}$이면 $f{\displaystyle }$ ${\displaystyle =o}$(${\displaystyle F)}$ .$${$display f\cdot$ g$=o(F\cdot$ G$)$입니다.$}$

또한 다음과 같은 이동성 관계도 충족합니다.

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

빅 오메가 표기법

또 다른 점근 표기법은$\delta {\displaystyle \mathrm{}}$ {$displaystyle \Omega$로 "big amega"^[18]로 읽힌다.이 진술에는 두 가지 광범위하고 양립할 수 없는 정의가 있습니다.

$displaystyle$$\Omega(g(x))},$ $x$ ${\displaystyle \to }$ {\$displaystyle$ x$\to$a$\},$

여기서 a는 어떤 실수, θ 또는 -dism입니다.여기서 f와 g는 a의 근방에서 정의되는 실함수이며 g는 이 근방에서 양수입니다.

하디-리틀우드 정의는 주로 해석수 이론에서 사용되고 크누트 정의는 주로 계산 복잡도 이론에서 사용된다. 정의는 동일하지 않다.

하디-리틀우드 정의

1914년 Godfrey Harold Hardy와 John Edensor Littlewood는 다음과 같이 정의된 새로운 기호$\omega {\displaystyle \mathrm{}}$ {\$displaystyle \Omega$^[19]를 도입했다.

$displaystyle$$\Omega$ ($g$$(x)$ ) ${\displaystyle \to }$ x$$ f ( ) () 0 . \ $displaystyle \limsup$ _ ${ x$\ $to$ \ infty$$$}$ \$left$ \ $frac${ f( x ) } {$g$ ( x ) $}$$$} 、 \ $right{\displaystyle }$> $0 。$$}$

${\displaystyle \mathrm{따라서}}$f (${\displaystyle }$x ) ${\displaystyle =\delta }$ (${\displaystyle g}$(${\displaystyle }$x )$$\ $displaystyle$ f$(x$) $=$$\Omega(g(x))}$는 f${\displaystyle (x)}$ $=$($g)$ {$style$ f$(x$)=$o(g($x)}}의 부정입니다$.$

1916년에 동일한 저자가 다음과 ^[20]같이 정의된 두 가지 새로운 기호 ${\displaystyle r_{}}$R (\$displaystyle \Omega$ _${R})$와 ${\displaystyle l_{}}$L (\$displaystyle \Omega$ _${L$을 도입했습니다.

$displaystyle$$\Omega$ _${R}(g(x))},$ x$$ ( ) ()> \ $displaystyle \limsup$_ {$x\to \infty$$$$}$ {\$frac {f(x)}{g(x)}}}$ $0$ ;

$displaystyle$$\Omega$ _${L}(g(x$$$$))},$ x$$ ( ) () <$0$. \ $displaystyle$\$liminf$_ {$x$ \ $to$\ $infty$$$$}$ { \ $frac { f$ ( x )$}$ { \ $g$( x ) } $。$

이 기호들은 1924년 ^[21]에드먼드 란다우에 의해 같은 의미로 사용되었다.Landau 이후 표기는 $정확히{\displaystyle {\mathrm{}}_{}}$ 사용되지 않았습니다.${\displaystyle {\omega }_{}}$ R$$\ \ $displaystyle$ \ $Omega$$_$ {$${ R$$$$ }${\$ + \ $displaystyle$ \ Omega$$$_$ { + } 、$$$l$ L$$\ $displaystyle$\$Omega$$$_ { -$\}$^{[citation needed]} ${\displaystyle {。}_{}}$

이들 3개의 기호 $\delta {\displaystyle \mathrm{},{}_{\mathrm{}}}$ $+,$-$$\$Omega _{+},\Omega$ _$\{-\}$ 및${\displaystyle }f{\displaystyle }$ (${\displaystyle x}$ )$$± (${\displaystyle g}$ ) \ $display style$ f$(x$ $=$$\Omega$ _${\pm$}($g(x)})}($f${\displaystyle }$(${\displaystyle x)}$ ${\displaystyle ={}_{}}$+ (${\displaystyle g}$($))$ {\$style$ f$(x$) $=$ 를 $표시$함)$\Omega$ _${+}(g(x))}}}$ 및$$ $f{\displaystyle (x)}$ ${\displaystyle ={}_{\mathrm{}}}$ -${\displaystyle {}_{}}$(${\displaystyle g}$ (${\displaystyle x}$) {$displaystyle$ f$(x$) $=$$\Omega$ _${-}(g(x))})$는 현재 해석수 이론에서 ^[22][23]사용되고 있다.

간단한 예

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 소스되지 않은 소재는 이의를 제기하여 삭제할 수 있습니다. (2021년 4월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

우리는 가지고 있다.

${\displaystyle \sin }$ ${\displaystyle }$ x${\displaystyle =}$ ${\displaystyle \mathrm{\omega }}$ (${\displaystyle 1}$ )x$$${\displaystyle \to }$$x$ 、 \ $displaystyle x →$ \ Omega (1)$x$ 、 \ $displaystyle$x \ $to$\$infty$ ,$$}

더 정확히 말하면

${\displaystyle \sin }$ ${\displaystyle ={}_{}}$± ( ${\displaystyle 1}$) {$displaystyle \sin$ x =\$Omega$ _${\pm }(1$)는 x ${\displaystyle \to \mathrm{.}}$。{ $display style$ x$\to$ \$infty$. }

우리는 가지고 있다.

${\displaystyle \sin }$ ${\displaystyle x}$ + ${\displaystyle 1}$ ${\displaystyle =\mathrm{\omega }}$ (${\displaystyle 1}$ $)x$${\displaystyle \to }$ ${\displaystyle ,}$ $x{\displaystyle }$ 、 \ $displaystyle$$\ sin$ x + $1$= \ Omega ( $1$$$)$$、 \ $displaystyle x$ \ $to \$ infty , 。

더 정확히 말하면

${\displaystyle \sin }$ ${\displaystyle x}$ + ${\displaystyle 1}$ ${\displaystyle ={}_{}}$+ (${\displaystyle 1}$ $)x$ ${\displaystyle \to }x{\displaystyle }$ ${\displaystyle \mathrm{、}}$ \ displaystyle \$sin$x + 1$$→ \ $Omega$ _ { + } ($1$ ) ;$${ $displaystyle$x \ $to$\$infty$; }

하지만

${\displaystyle \sin }$ ${\displaystyle }$${\displaystyle }$x${\displaystyle }$+ ${\displaystyle 1{}_{\mathrm{}}}$ -${\displaystyle {}_{}}$(${\displaystyle 1}$)x ${\displaystyle \to }$ $x{\displaystyle }$ x ${\displaystyle \mathrm{（}}$ \ displaystyle \ $sin$x +$1$ \ $not$= \ $Omega$ _ { - $}$( $1$ )$$。{ $displaystyle$x \ $to$\$infty$} 。

Knuth 정의

1976년 도널드 크누스는 더 강한 ^[24]성질을 설명하기 위해$\delta {\displaystyle \mathrm{}}$(\$displaystyle\Omega)$ 기호를$$ 사용한 것을 정당화하는 논문을 발표했다.Knuth는 다음과 같이 쓰고 있습니다.지금까지 컴퓨터 과학 분야에서 본 모든 어플리케이션에는 보다 강력한 요건이 있습니다.훨씬 더 적절합니다.그는 정의했다

${\displaystyle f(x)=\Omega(g(x))\왼쪽 화살표 g(x)=O(f(x))}$

코멘트와 함께: "$나$는 하디와 리틀우드의$$$ω$에 대한 정의를 바꿨지만, 그들의 정의는 결코 널리 쓰이지 않고,^[24] 그들의 정의가 적용될 때 그들이 말하고 싶은 다른 방법들이 있기 때문에 나는 그렇게 하는 것이 정당하다고 생각한다.

바흐만-란다우 표기법

표기법	이름[24]	묘사	형식적 정의	제한[25][26][27][24][19] 정의
$\displaystyle f(n)=o(g(n))}$	스몰 O; 스몰 오	f는 점근적으로 g에 의해 지배된다.	$\displaystyle \forall k> 0,\forall n_{0},\forall n>n_{0}\forl f(n) <k\cdot g(n)}$	$\displaystyle \lim _{n\to\infty}{\frac\left f(n)\right }{g(n)}=0}$
$\displaystyle f(n)=O(g(n))}$	빅오, 빅오, 빅오미크론	${\displaystyle f}${\$displaystyle$ f $}$는 점근적으로 g(최대 상수 계수)에 의해 위쪽으로 경계된다.	$\displaystyle \cdot k> 0,\cdot n_{0},\forall n>n_{0}\cdot f(n)\leq k\cdot g(n)}$	$\displaystyle \limsup _{n\to\infty}{\frac\left f(n)\right }{g(n)}<\infty }$
${\displaystyle f(n)=\Theta(g(n))}$	빅세타	f는 점근적으로 g에 의해 위와 아래에 모두 경계된다.	$\displaystyle \displaystyle k_{1}> 0,\display k_{2}> 0,\display n_{0},\forall n>n_{0}\displays }$ $\displaystyle k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)}$	${\displaystyle f}$ ${\displaystyle (n}$ ) ${\displaystyle =O}$ ($g$ (${\displaystyle n}$) { $displaystyle$f ( n )$=$O ($g$ ($n$ ) } 、${\displaystyle \mathrm{f<img\; alt="f(n)=O(g(n))"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/6f4ecd455bbf94b9eeab71366619cb18e040dce4"\; style="vertical-align:\; -0.838ex;\; width:15.484ex;\; height:2.843ex;">}}$ ( n ) $=$ (${\displaystyle g}$ ( n )$$、 { $displaystyle$f ( n )= \$Omega$ ($g$ ( n )$$}$$ 、 ( Knuth 버전)
${\displaystyle f(n)\sim g(n)}$	의 주문으로	f는 점근적으로 g와 같다.	$\displaystyle \varepsilon > 0,\forall n_{0},\forall n>n_{0}\frech \ frac {f(n)}{g(n)}-1\right <\varepsilon }$	$\displaystyle \lim _{n\to\infty}{\frac {f(n)}{g(n)}}=1}$
$\displaystyle f(n)=\Omega(g(n))}$	복잡도 이론의 빅 오메가(Knuth)	f는 점근적으로 g에 의해 아래에 경계된다.	$\displaystyle \cdot k> 0,\cdot n_{0},\forall n>n_{0}\cdot f(n)\geq k\cdot g(n)}$	$\displaystyle \liminf _{n\to\infty}{\frac\left f(n)\right }{g(n)}}> 0}$
$\displaystyle f(n)=\omega(g(n))}$	스몰 오메가	f는 점근적으로 g를 지배한다	$\displaystyle \forall k> 0,\forall n_{0},\forall n>n_{0}\forl f(n)>k\cdot g(n)}$	$\displaystyle \lim _{n\to\infty}{\frac {\left f(n)\right }{g(n)}=\infty }$
$\displaystyle f(n)=\Omega(g(n))}$	수 이론의 빅 오메가(Hardy-Littlewood)	$displaystyle$ f $}$는 점근적으로 g에 의해 지배되지 않는다.	$\displaystyle \cdot k> 0,\forall n_{0},\display n>n_{0}\display f(n)\geq k\cdot g(n)}$	$\displaystyle \limsup _{n\to\infty}{\frac\left f(n)\right }{g(n)}}> 0}$

제한 정의는 충분히 $\displaystyle$n에 대해 g( 0 { $displaystyle$g ($n$ ) > $0$을 로 하고 있습니다.그 탁자(부분적으로)3위의에서,시, OΘ,∼을,{\displaystyle o,O,\Theta ,\sim,}(의 크누스의 버전)Ω, 기능에ω{\displaystyle\Omega ,\omega}&lt에 해당하는에, ≤, ≈, 음,{\displaystyle<>,\leq ,\approx ,=,}≥,>구분이 진짜 lin에{\displaystyle \geq ,>.}.e[27](하드$단$, (\displaystyle$\Omega$의 y-Littlewood 버전은 이러한 설명에 대응하지 않습니다.)

컴퓨터 공학에서는 $큰{\displaystyle }$ O$,$ 큰 $Theta$$Ⅱ,$ $작은 O$ 작은 O, $작은$ O, $작은$ Omega$,$ 그리고 Knuth의 큰 Omega$Ⅱ{\displaystyle \mathrm{}}$, 큰 Omega$$^[28]Ⅱ의$$ $표기법$을 사용합니다.해석적 숫자 이론에서는 종종 $큰{\displaystyle }$O(\$displaystyle$ O$),$ $작은{\displaystyle }$O(\$displaystyle$O$),$ Hardy-Littlewood의 큰 Omega$$$Ⅱ{\displaystyle \mathrm{}}$(+, - 또는 ± 첨자 유무) 및$~(\displaystyle \sim$$$$}$ ^[22]표기를$$ 사용합니다.$작은{\displaystyle }$ 오메가$${\(\$displaystyle \omega)$ 표기법은$$ ^[29]분석에서 자주 사용되지 않습니다.

컴퓨터 공학에 사용

비공식적으로, 특히 컴퓨터 과학에서, 빅 O 표기법은 종종 주어진 ^{[citation needed]}맥락에서 빅 세타 δ 표기법을 사용하는 것이 더 사실적으로 적절할 수 있는 점근적 엄격한 경계를 설명하기 위해 다소 다르게 사용될 수 있다.예를 들어, 함수 T(n) = 73n³² + 22n + 58을 고려할 때, 일반적으로 다음 모든 것이 허용되지만, 더 엄격한 경계(아래 번호 2와 3 등)가 느슨한 경계(아래 번호 1 등)보다 강하게 선호됩니다.

1. T(n) = O(n¹⁰⁰)
2. T(n) = O(n³)
3. T(n) = Ω(n³)

각각 동등한 영어 문장은 다음과 같습니다.

1. T(n)는 점근적으로 n보다 빠르게¹⁰⁰ 성장하지 않는다
2. T(n)는 점근적으로 n보다 빠르게³ 성장하지 않는다
3. T(n)는 n만큼³ 점근적으로 빠르게 성장한다.

따라서 이 세 가지 진술이 모두 사실이지만, 점차 더 많은 정보가 각 진술에 포함되어 있습니다.단, 일부 필드에서는 빅 O 표기법(위 목록의 2번)이 빅 Theta 표기법(위 목록의 3번 항목)보다 더 일반적으로 사용됩니다.예를 들어, T(n)가 입력 크기 n에 대해 새롭게 개발된 알고리즘의 실행 시간을 나타낸다면, 알고리즘의 발명가와 사용자는 점근 하한에 대한 명시적인 진술을 하지 않고 실행하는데 걸리는 시간에 대해 점근 상한을 두는 경향이 있을 수 있다.

기타 표기법

Cormen, Leiserson, Rivest 및 Stein은 알고리즘 입문서에서 다음을 충족하는 함수 집합을 고려합니다.

$\displaystyle f(n)=O(g(n)\quad(n\to\infty)~ .}$

예를 들어, 올바른 표기법에서는 이 집합을 O(g)라고 부를 수 있다.

${\displaystyle O(g)=\{f:{\text{and}}~{\text{n_{0}}~{\text{that}}}~{\leq f(n)\leq cg(n){\text{0}\}}.}$^[30]

저자들은 집합 멤버십 연산자(set membership 연산자)가 아닌 집합 멤버십을 나타내기 위해 평등 연산자(=)를 사용하는 것은 표기법의 남용이지만,^[6] 그렇게 하는 것은 장점이 있다고 말한다.방정식 또는 부등식 내에서 점근 표기법의 사용은 집합 O(g)에서 익명 함수를 나타내며, 이는 낮은 차수의 항을 제거하고 방정식의 불필요한 혼란을 줄이는 데 도움이 됩니다.^[31] 예를 들어 다음과 같습니다.

${\displaystyle 2n^{2}+3n+1=2n^{2}+O(n)}$

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

컴퓨터 과학에서 가끔 사용되는 또 다른 표기법은 δ(읽기 소프트-O)이다: f(n) = δ(g(n)는 일부 ^[32]k에 대한 f(n) = O(g(n^k) log n)의 약어이다.어떤 ^[33]작가들은 같은 목적으로^* O를 쓴다.기본적으로 로그 인자를 무시하는 빅 O 표기법입니다. 왜냐하면 다른 슈퍼 로그 함수의 성장률 효과는 로그 성장 인자에 의한 미세한 점의 효과보다 나쁜 런타임 성능을 예측하는 데 더 중요한 대규모 입력 파라미터의 성장률 폭발을 나타내기 때문입니다.이 표기법은 (로그 n은 항상 상수 k와 θ > 0에 대해 o(n^ε)이기^k 때문에) 눈앞의 문제에 대해 너무 엄격한 경계로 기술된 성장률 내의 "니트픽킹"을 배제하기 위해 자주 사용됩니다.

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

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

는 ln${\displaystyle n}$n \ $displaystyle \ln$n$$의 ${\displaystyle \mathrm{관점}}$에서 다항식과 지수 함수 사이에 있는 함수에 편리합니다.

일반화와 관련 사용법

노름 벡터 공간에서 값을 취하는 함수에 대한 일반화(절대값을 노름으로 대체)는 간단하며, 여기서 f와 g는 같은 공간에서 값을 취할 필요가 없다.임의의 토폴로지 그룹에서 값을 취하는 함수 g에 대한 일반화도 가능하다^{[citation needed]}.또한 "유향 프로세스" x_o → x는 임의의 필터 베이스, 즉 유향 그물 f와 g를 도입함으로써 일반화 될 수 있다.o 표기법은 상당히 일반적인 공간에서의 미분 및 미분 가능성 및 함수의 (점근적) 동등성을 정의하기 위해 사용할 수 있다.

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

(f와 g가 양의 실수치 함수일 경우 lim f / g = 1로 감소)예를 들어 2x는 Ω(x)이지만 2x - x는 o(x)가 아닙니다.

이력(바흐만-란다우, 하디 및 비노그라도프 표기법)

기호 O는 수 이론가 폴 바흐만이 1894년 그의 책 Analytische Zahlentheory의 두 번째 권에서 처음 소개했습니다.^[1]숫자 이론가 에드먼드 란다우는 그것을 채택했고, 그래서 1909년에 ^[2]o 표기법을 도입하도록 영감을 받았다; 그래서 지금은 둘 다 란다우 기호라고 불린다.이러한 표기법은 1950년대에 점근 ^[34]분석을 위해 응용 수학에 사용되었다.기호$\delta {\displaystyle \mathrm{}}$('displaystyle $\Omega')$는 1914년 Hardy와 ^[19]Littlewood에 의해 도입되었다.하디, 리틀 우드는 또한 1916년 기호에 소개된 Ω R{\displaystyle \Omega_{R}}("바로")과Ω 나는{\displaystyle \Omega_{나는}}(" 떠났다")[20]선구자들이 현대 기호Ω+{\displaystyle \Omega_{+}}(" 작은시보다 작지 않다")과Ω −{\displaystyle \Omega_{-}}(" 있지 않다.rt"의 작은 o"를 표시합니다.따라서 오메가 기호(원래의 의미와 함께)는 때때로 "란다우 기호"라고도 불린다.이 표기법$\delta {\displaystyle \mathrm{}}$(\$displaystyle \Omega)$는 적어도 1950년대부터 ^[35]수 이론에서 일반적으로 사용되었다.1970년대에 빅 O는 관련된 세타 표기법을 도입한 도널드 크누스에 의해 컴퓨터 과학에서 대중화되었고, 오메가 ^[24]표기법에 대한 다른 정의를 제안했다.

란다우는 절대 큰 세타와 작은 오메가 기호를 사용하지 않았다.

하디의 기호는 (현대 O 표기법의 관점에서)

${\displaystyle fg}$ g${\displaystyle }$o f${\displaystyle o}$O$$($g$ ) { $displaystyle$f \ $precurlyeq$g \ $ifff f$ ( g$)$ }및$$${\displaystyle }$ f${\displaystyle g}$f${\displaystyle o}$ (${\displaystyle g}$)$$;{ $displaystyle$f\$prec$ g$\iff$f \ $in o$ ($$g )

(단, $displaystyle \prec \!!"$ 표기법을 정의하거나 사용하지 않았습니다.$\prec$ $\}$ , 또는 $"\displaystyle$ \ll$"$ 입니다.Hardy는 1910년 자신의 저서 "Order of Infinity"에서 기호$$${\(및$ 기타 기호)와 display(\displaystyle$\prec)$을 소개했으며, 세 개의 논문(1910-1913)에서만 그것들을 사용했다.400여 권의 종이와 책에서 그는 꾸준히 란다우 기호 O와 O를 사용했다.

하디의 표기법은 더 이상 사용되지 않는다.한편, 1930년대에 ^[36]러시아의 숫자 이론가 이반 마트베예비치 비노그라도프는 그의 표기법인 "\$displaystyle\ll$을 도입했는데$,$ 이는 O\$displaystyle$O $표기법$ 대신 숫자 이론에서 점점 더 많이 사용되고 있다.우리는 가지고 있다.

${\displaystyle f\ll g\iff f(g) in O(g)}$

또한 두 표기가 동일한 문서에서 사용되는 경우가 많습니다.

Big-O는 원래 "Order of" (Ordnung, 바흐만 1894)의 약자로 라틴 문자이다.바흐만과 란다우 둘 다 그것을 "오미크론"이라고 부르지 않았다.크누스는 훨씬 늦은 1976년에 오메가 상징에 대한 그의 정의를 언급하면서 수도 오미크론으로 ^[24]보았다.숫자 0은 사용하지 마십시오.

「 」를 참조해 주세요.

• 점근 확장:Taylor의 공식을 일반화하는 함수의 근사치
• 점근 최적 알고리즘:문제에 대한 하한 상수 내에 점근적으로 상한을 갖는 알고리즘을 설명하는 데 자주 사용되는 구문
• 확률 표기법에서의_p 빅 O: O_p
• 상한 상한 및 하한 하한 하한:이 문서에 사용된 일부 제한 표기법에 대한 설명입니다.
• 마스터 정리(알고리즘 분석):Big O 표기법을 사용하여 분할 및 정복 재귀 알고리즘을 분석하는 경우
• 나흐빈의 정리:적분변환의 수렴영역을 기술할 수 있도록 복소해석함수의 정확한 경계를 정하는 방법
• 근사 순서
• 수학적 연산의 계산 복잡성

레퍼런스 및 메모

추가 정보

• Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press.
• Knuth, Donald (1997). "1.2.11: Asymptotic Representations". Fundamental Algorithms. The Art of Computer Programming. Vol. 1 (3rd ed.). Addison-Wesley. ISBN 978-0-201-89683-1.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "3.1: Asymptotic notation". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. pp. 226–228. ISBN 978-0-534-94728-6.
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. doi:10.1007/978-3-540-25984-8_27.
• Black, Paul E. (11 March 2005). Black, Paul E. (ed.). "big-O notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "little-o notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "Ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "Θ". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006.

외부 링크

• 시퀀스 증가 - OEIS(온라인 정수 시퀀스 백과사전) Wiki
• 점근 표기 개요^{[영구 데드링크]}
• 란다우 기호
• Big-O 표기법– 용도
• 쉬운 영어로 설명되는 Big O 표기법
• Wayback Machine에서 2018-10-07년 아카이브된 1차 파생상품에 대한 중앙 분할 차분 방식의 정확도 Big O의 예
• 알고리즘 복잡도 분석의 부드러운 입문