점근 표기법

**빅-O 표기법**(Big O notation)은 함수의 정의역에 대한 대략적인 크기를 설명하는 수학적 표기법이다. 빅-O는 독일 수학자 파울 바흐만과 에드문트 란다우가 발명하고url=https://archive.org/stream/handbuchderlehre01landuoft#page/31/mode/2up 다른 사람들이 확장한 일련의 표기법 중 하나이며, 이를 통틀어 **바흐만-란다우 표기법**이라고 한다. 문자 O는 바흐만이 근삿값의 순서를 의미하는 Ordnung을 나타내기 위해 선택했다. 컴퓨터 과학에서 빅-O 표기법은 입력 크기가 증가함에 따라 실행 시간 또는 공간 요구 사항이 어떻게 증가하는지에 따라 알고리즘을 분류하는 데 사용된다. chapter=Characterizing running times 입력의 "크기"는 일반적으로 해결할 문제의 주어진 인스턴스가 얼마나 어려운지를 나타내는 데 사용된다. 답을 계산(또는 문제를 "해결")하는 데 필요한 [실행] 시간과 [메모리] 공간은 해당 문제 인스턴스의 어려움을 나타내는 것으로 간주된다. 계산 복잡도 이론의 목적을 위해 빅 O 표기법은 이 세 가지(입력 [데이터 스트림]의 크기, 필요한 [실행] 시간, 필요한 [메모리] 공간) 모두의 상한([크기 정도]의)에 사용된다. 해석적 수론에서 빅-O 표기법은 수론적 함수의 증가에 대한 경계를 표현하는 데 자주 사용된다. 잘 알려진 예 중 하나는 소수 정리의 나머지 항이다. 미적분학을 포함한 수학적 해석에서 빅-O 표기법은 멱급수를 절단할 때의 오차를 제한하고 더 간단한 함수에 의한 실수 또는 복소수 값 함수의 근사 품질을 표현하는 데 사용된다. 종종 빅-O 표기법은 변수가 커짐에 따라 함수의 성장률에 따라 함수를 특징짓는다. 동일한 점근 성장률을 가진 다른 함수는 동일한 O 표기법을 사용하여 표현될 수 있다. 문자 O는 함수의 성장률을 "함수의 차수"라고도 부르기 때문에 사용된다. 빅-O 표기법으로 함수를 설명하는 것은 함수의 성장률에 대한 상한만 제공한다. 빅-O 표기법과 관련된 여러 표기법이 있으며, o, \sim, \Omega, \ll, \gg, \asymp, \omega, \Theta 기호를 사용하여 다른 종류의 성장률 경계를 설명한다.publisher=케임브리지 대학교 출판부
# 정식 정의
추정할 함수 f는 정의역 D에서 정의된 실수 또는 복소수 값 함수이며, 비교 함수 g는 동일한 집합 D에서 정의된 음이 아닌 실수 값 함수라고 하자. 정의역에 대한 일반적인 선택은 유한 또는 무한한 실수 구간, 양의 정수 집합, 복소수 집합, 실수/복소수 튜플이다. 정의역이 명시적으로 쓰여 있거나 암묵적으로 이해되는 경우, 다음과 같이 쓴다. : f(x) = O\bigl(g(x)\bigr)\ 이는 " f(x)는 g(x)의 빅-O"라고 읽으며, 양의 실수 M이 존재하여 다음을 만족하는 경우이다. :\left| f(x) \right|\le M\ g(x) \qquad ~ \mathsf{\ for\ all\ } ~ \quad x \in D. 만약 g(x) > 0(즉, 정의역 D 전체에서 g가 0이 아님)이면, 동등한 정의는 비율 \frac{f(x)}{g(x)} 이 유계라는 것이다. 즉, 모든 x \in D에 대해 \Big|\frac{f(x)}{g(x)}\Big| \le M을 만족하는 양의 실수 M이 존재한다. 이는 정의역이 유한, 무한, 실수, 복소수, 단일 변수 또는 다변수인 경우를 포함하여 컴퓨터 과학 및 수학에서 빅-O의 모든 사용을 포괄한다. 대부분의 응용 프로그램에서 O\bigl( \cdot \bigr)의 인자 안에 나타나는 함수 g(x)를 가능한 한 간단한 형태로 선택하며, 상수 인자와 하위 차수 항은 생략한다. 숫자 M은 암시적 상수라고 불리는데, 이는 일반적으로 지정되지 않기 때문이다. 빅-O 표기법을 사용할 때 중요한 것은 어떤 유한한 M이 존재한다는 것이지, 그 특정 값은 아니다. 이는 많은 해석적 부등식의 표현을 단순화한다. 양의 실수 또는 양의 정수에서 정의된 함수에 대해서는 더 제한적이고 다소 상충되는 정의가 여전히 일반적으로 사용된다. publisher=PWS Publishin 특히 컴퓨터 과학에서 그렇다. 점근적으로 양수인 함수로 제한될 때, 표기법 : f(x) =O\bigl(g(x)\bigr) \qquad ~ \mathsf{ as } \quad x \to \infty 는 어떤 실수 a에 대해 f(x) = O\bigl(g(x)\bigr)가 정의역 \left[a,\infty\right)에서 성립한다는 것을 의미한다. 여기서 표현 x \to \infty는 극한을 나타내는 것이 아니라, 부등식이 충분히 큰 x에 대해 성립한다는 개념을 나타낸다. 표현 x \to \infty는 종종 생략된다. 마찬가지로 유한한 실수 a에 대해 표기법 : f(x) = O\bigl(g(x)\bigr) \qquad ~ \text{ as } \ x \to a 는 어떤 상수 c > 0에 대해 f(x) = O\bigl(g(x)\bigr)가 구간 \left[c-a, c+a\right]에서 성립한다는 것을 의미한다. 즉, a의 작은 근방에서 성립한다. 또한 표기법 \ f(x) = h(x) + O\bigl(g(x)\bigr)\ 는 f(x) - h(x)= O\bigl(g(x)\bigr)를 의미한다. 더 복잡한 표현도 가능하다. 등호(=)가 쓰여 있음에도 불구하고 f(x) = O\bigl(g(x)\bigr)라는 표현은 등식 관계가 아니라 f와 g를 관련시키는 부등식을 나타낸다. 1930년대에, pages=249–253 : Translated in English in:
publisher=Springer-Verlag 러시아의 정수론학자 I.M. 비노그라도프는 \ll 표기법을 도입했으며, 이는 정수론 publisher=American Mathematical Society 및 다른 수학 분야에서 O 표기법의 대안으로 점점 더 많이 사용되고 있다. 우리는 다음을 가진다. :\ f \ll g \iff f = O\bigl(g\bigr). 종종 두 표기법 모두 동일한 작업에서 사용된다.
## 빅-O의 집합 버전
컴퓨터 과학에서는 빅-O를 함수의 집합을 정의하는 것으로 정의하는 것이 일반적이다. 양수(또는 음이 아닌) 함수 g(x)가 지정되면, O\bigl(g(x)\bigr)는 \tilde f(x) = O\bigl(g(x)\bigr)를 만족하는 모든 함수 \tilde f의 집합을 나타내는 것으로 해석된다. 그러면 동등하게 f(x) \in O\bigl(g(x)\bigr)로 쓸 수 있으며, "함수 \ f(x)\ 는 차수가 최대 g(x)인 모든 함수들의 집합에 속한다."라고 읽는다.
# 무한 정의역을 사용한 예시
일반적인 사용에서 O 표기법은 실수 [a,\infty)의 무한 구간에 적용되며 매우 큰 x에 대한 함수의 동작을 나타낸다. 이 설정에서 "가장 빠르게" 성장하는 항의 기여는 결국 다른 항들을 무관하게 만들 것이다. 결과적으로 다음 단순화 규칙이 적용될 수 있다. *f(x)가 여러 항의 합인 경우, 가장 큰 성장률을 가진 항이 있다면 그 항을 유지하고 다른 모든 항은 생략할 수 있다. *f(x)가 여러 인자의 곱인 경우, x에 의존하지 않는 상수(곱의 인자)는 생략할 수 있다. 예를 들어, f(x)=6x^4-2x^3+5라고 하고, 이 함수를 큰 x에 대한 성장률을 설명하기 위해 O 표기법을 사용하여 단순화하고자 한다고 가정하자. 이 함수는 6x^4, -2x^3, 5의 세 항의 합이다. 이 세 항 중 가장 높은 성장률을 가진 항은 x의 함수로서 가장 큰 지수를 가진 항, 즉 6x^4이다. 이제 두 번째 규칙을 적용할 수 있다. 6x^4는 6과 x^4의 곱이며, 첫 번째 인자는 x에 의존하지 않는다. 이 인자를 생략하면 단순화된 형태 x^4가 된다. 따라서 우리는 f(x)가 x^4의 "빅-O"라고 말한다. 수학적으로, 모든 x\ge 1에 대해 f(x)=O(x^4)라고 쓸 수 있다. 위에서 언급한 정식 정의를 사용하여 이 계산을 확인할 수 있다. f(x)=6x^4-2x^3+5와 g(x)=x^4라고 하자. f(x)=O(x^4)라는 진술은 다음과 같이 확장될 수 있다. |f(x)| \le M x^4 양의 실수 M의 적절한 선택과 모든 x \ge 1에 대해. 이를 증명하기 위해 M=13이라고 하자. 그러면 모든 x\ge 1에 대해: \begin{align} |6x^4 - 2x^3 + 5| &\le 6x^4 + |-2x^3| + 5\\\ &\le 6x^4 + 2x^4 + 5x^4\\\ &= 13x^4 \end{align} 따라서 |6x^4 - 2x^3 + 5| \le 13 x^4 . 같은 논리로 다음도 사실이지만, f(x)=O(x^{10}) 이는 함수 f의 덜 정확한 근사값이다. 반면에 f(x)=O(x^3)이라는 진술은 거짓이다. 왜냐하면 항 6x^4으로 인해 f(x)/x^3이 유계가 아니기 때문이다. 함수 T(n)이 입력 n을 가진 알고리즘에 필요한 단계 수를 설명할 때, 다음과 같은 표현식 T(n)=O(n^2) 암시된 정의역이 양의 정수 집합인 경우, 알고리즘이 최대 n^2의 시간 복잡도를 가진다는 것을 의미하는 것으로 해석될 수 있다.
# 유한 정의역을 사용한 예시
빅-O는 유한 구간에서 수학 함수의 근사값에 대한 오차 항을 설명하는 데도 사용될 수 있다. 가장 중요한 항들은 명시적으로 쓰여지고, 그 다음 가장 중요하지 않은 항들은 단일 빅-O 항으로 요약된다. 예를 들어, 지수 급수와 x가 작을 때 유효한 두 가지 표현을 고려해 보자. \begin{align} 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|\le 1 \\\\[4pt] &= 1 + x + O(x^2) && \text{ for all } |x|\le 1. \end{align} 중간 표현()을 포함하는 줄)은 오차의 절댓값 \ e^x- (1 + x + \frac{\; x^2\ }{2} )\ 가 \ x ~가 작을 때 어떤 상수 곱하기 ~ |x^3|\ 이하임을 의미한다. 이는 테일러 정리의 사용 예시이다. 주어진 함수의 동작은 유한 정의역과 무한 정의역에서 매우 다를 수 있다. 예를 들어, (x+1)^8 = x^8 + O(x^7) \quad \text{ for } x\ge 1 반면 (x+1)^8 = 1 + 8x + O(x^2) \quad \text{ for } |x|\le 1.
# 다변수 예시
x \sin y = O(x) \quad \text{ for }x\ge 1,y\text{ any real number} 3a^2+7ab+2b^2+a+3b+14 \ll a^2+b^2 \ll a^2 \quad \text{ for all } a\ge b\ge 1 \frac{xy}{x^2+y^2} = O(1) \quad \text{ for all real } x,y \text{ that are not both } 0 x^{it} = O(1) \quad \text{ for } x\ne 0,t\in \mathbb{R}. 여기서는 두 변수의 복소변수 함수가 있다. 일반적으로 모든 유계 함수는 O(1)이다. (x+y)^{10} = O(x^{10}) \quad \text{ for }x\ge 1, -2\le y\le 2. 마지막 예는 다른 변수에 대해 유한 및 무한 정의역이 혼합된 경우를 보여준다. 이 모든 예에서 경계는 두 변수 모두에서 균일하다. 때로는 다변수 표현에서 한 변수가 다른 변수보다 더 중요하며, 빅-O 기호 또는 \ll 기호에 첨자를 사용하여 암시된 상수 M이 하나 이상의 변수에 의존한다는 것을 표현할 수 있다. 예를 들어, 다음 표현을 고려해 보자. (1+x)^b = 1 + O_b(x) \quad \text{ for } 0 \le x\le 1, b\text{ any real number.} 이는 각 실수 b에 대해 b에 의존하는 상수 M_b가 존재하여 모든 0\le x\le 1에 대해 다음이 성립한다는 것을 의미한다. |(1+x)^b-1| \le M_b \cdot x. 이 특정 진술은 일반 이항 정리에서 비롯된다. 테일러 급수 이론에서 흔히 볼 수 있는 또 다른 예는 e^x = 1 + x + O_r(x^2) \quad \text{ for all } |x|\le r, r\text{ being any real number.} 여기서 암시된 상수는 정의역의 크기에 따라 달라진다. 첨자 표기법은 이 페이지의 다른 모든 표기법에 적용된다.
# 속성

## 곱
: f_1 = O(g_1) \text{ and } f_2 = O(g_2) \Rightarrow f_1 f_2 = O(g_1 g_2) :f\cdot O(g) = O(|f| g)
## 합
만약 f_1 = O(g_1) 이고 f_2= O(g_2) 이면 f_1 + f_2 = O(\max(g_1, g_2)) 이다. 따라서 만약 f_1 = O(g) 이고 f_2 = O(g) 이면 f_1+f_2 = O(g) 이다.
## 상수로 곱하기
k가 0이 아닌 상수라고 하자. 그러면 O(|k| \cdot g) = O(g)이다. 다시 말해, f = O(g)이면 k \cdot f = O(g)이다.
## 추이적 속성
만약 f=O(g)이고 g=O(h)이면 f=O(h)이다. 양의 정수 n의 함수 f가 다른 함수들의 유한 합으로 쓰여질 수 있다면, 가장 빠르게 성장하는 함수가 f(n)의 차수를 결정한다. 예를 들어, :f(n) = 9 \log n + 5 (\log n)^4 + 3n^2 + 2n^3 = O(n^3) \qquad\text{for } n\ge 1 . 무한으로 향하는 성장에 대한 몇 가지 일반적인 규칙. 아래의 두 번째 및 세 번째 속성은 로피탈의 정리를 사용하여 엄밀하게 증명할 수 있다.
## 큰 거듭제곱이 작은 거듭제곱을 지배한다
b>a\ge 0 인 경우, n^a = O(n^b).
## 거듭제곱이 로그를 지배한다
임의의 양수 a,b에 대해, (\log n)^a = O_{a,b}(n^b), a가 아무리 크고 b가 아무리 작더라도. 여기서 암시된 상수는 a와 b 모두에 의존한다.
## 지수가 거듭제곱을 지배한다
임의의 양수 a,b에 대해, n^a = O_{a,b}(e^{bn}), a가 아무리 크고 b가 아무리 작더라도. 어떤 c에 대해서도 n^c보다 빠르게 성장하는 함수를 초다항식(superpolynomial)이라고 한다. c>1인 형태의 어떤 지수 함수 c^n보다 느리게 성장하는 함수를 준지수식(subexponential)이라고 한다. 알고리즘은 초다항식적이면서 준지수적일 수 있다. 이러한 예로는 소인수분해의 알려진 가장 빠른 알고리즘과 함수 n^{\log n}이 있다. 로그 안의 n의 어떤 거듭제곱도 무시할 수 있다. 임의의 양수 c에 대해 O(\log n) 표기법은 O(\log (n^c))와 정확히 같은 의미이다. 왜냐하면 \log(n^c)=c\log n이기 때문이다. 마찬가지로, 다른 상수 밑을 가진 로그는 빅-O 표기법에 대해 동등하다. 반면에, 다른 밑을 가진 지수는 동일한 차수가 아니다. 예를 들어, 2^n과 3^n은 동일한 차수가 아니다.
## 더 복잡한 표현
더 복잡한 사용에서는 O(\cdot) 가 방정식의 여러 위치, 심지어 각 변에 여러 번 나타날 수도 있다. 예를 들어, n 이 양의 정수일 때 다음이 성립한다. \begin{align} (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{align} 이러한 진술의 의미는 다음과 같다. 왼쪽 변의 각 O(\cdot) 를 만족하는 어떤 함수들에 대해, 오른쪽 변의 각 O(\cdot) 를 만족하는 어떤 함수들이 존재하여, 이 모든 함수들을 방정식에 대입하면 양변이 같아진다는 것이다. 예를 들어, 위 세 번째 방정식은 " f(n)=O(1)을 만족하는 어떤 함수에 대해, n^{f(n)}=g(n) 을 만족하는 어떤 함수 g(n)=O(e^n) 가 존재한다"는 의미이다. " g(n)=O(e^n) "라는 진술의 암시된 상수는 " f(n)=O(1)"라는 표현의 암시된 상수에 의존할 수 있다. 몇 가지 추가 예시: \begin{align} 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{align}
## 비노그라도프의 \gg와 커누스의 빅 오메가
f, g가 모두 양의 함수인 경우, 비노그라도프는 f(x) \gg g(x) 표기법을 도입했으며, 이는 g(x) = O(f(x))와 동일한 의미이다. 비노그라도프의 두 표기법은 양의 함수 f,g에 대해 시각적 대칭을 즐긴다. f(x) \ll g(x) \Longleftrightarrow g(x) \gg f(x). 1976년, 도널드 커누스는 다음과 같이 정의했다. :f(x)=\Omega(g(x))\Longleftrightarrow g(x)=O(f(x)) 이는 비노그라도프의 f(x) \gg g(x)와 같은 의미를 갖는다. 훨씬 이전에 하디와 리틀우드는 \Omega를 다르게 정의했지만, 이는 더 이상 거의 사용되지 않는다(이비치(Ivić)의 책은 예외 중 하나이다). 더 강한 속성을 설명하기 위해 \Omega-기호를 사용한 것을 정당화하며, 커누스는 다음과 같이 썼다. "내가 지금까지 컴퓨터 과학에서 본 모든 응용 프로그램에 대해 더 강한 요구 사항...이 훨씬 더 적절하다." 커누스는 또한 "하디와 리틀우드의 \Omega 정의를 변경했지만, 그들의 정의가 널리 사용되지 않고, 그들의 정의가 적용되는 비교적 드문 경우에 그들이 말하고 싶은 것을 표현할 다른 방법이 있기 때문에 그렇게 하는 것이 정당하다고 생각한다."고 썼다.s2cid=5230246 실제로 커누스의 빅 \Omega 는 오늘날 하디-리틀우드의 빅 \Omega 보다 훨씬 더 널리 사용되며, 컴퓨터 과학과 조합론에서 일반적인 특징이다.
## 하디의 ≍와 커누스의 빅 세타
해석적 수론에서 표기법 f(x) \asymp g(x)는 f(x)=O(g(x))와 g(x)=O(f(x)) 모두를 의미한다. 이 표기법은 원래 하디에게서 비롯되었다. 동일한 개념에 대한 커누스의 표기법은 f(x) = \Theta(g(x))이다. 대략적으로 말하면, 이 진술들은 f(x)와 g(x)가 동일한 차수를 가진다는 것을 주장한다. 이 표기법들은 양의 상수 M,N이 존재하여 N g(x) \le f(x) \le M g(x) f,g의 공통 정의역의 모든 x에 대해 성립한다는 것을 의미한다. 함수가 양의 정수 또는 양의 실수에서 정의될 때, 빅-O와 마찬가지로 저자들은 종종 진술 f(x) = \Omega(g(x)) 및 f(x)=\Theta(g(x))를 충분히 큰 모든 x에 대해, 즉 어떤 지점 x_0 이후의 모든 x에 대해 성립하는 것으로 해석한다. 때로는 이를 진술에 x\to\infty를 추가하여 나타내기도 한다. 예를 들어, 2n^2 - 10n = \Theta(n^2) 는 정의역이 n\ge 6일 때는 참이지만, 함수가 n=5에서 0이므로 정의역이 모든 양의 정수일 때는 거짓이다.
### 추가 예시
n^3 + 20n^2 +n+12 \asymp n^3 \quad \text{ for all } n\ge 1. (1+x)^8 = x^8 + \Theta(x^7) \quad \text{ for all } x\ge 1. 표기법 f(n) = e^{\Omega(n)} \quad \text{ for all } n\ge 1, 은 양의 상수 M이 존재하여 모든 n\ge 1에 대해 f(n) \ge e^{Mn}임을 의미한다. 대조적으로, f(n) = e^{-O(n)} \quad \text{ for all } n\ge 1, 은 양의 상수 M이 존재하여 모든 n\ge 1에 대해 f(n) \ge e^{-Mn}임을 의미하고 f(n) = e^{\Theta(n)} \quad \text{ for all } n\ge 1, 은 양의 상수 M,N이 존재하여 모든 n\ge 1에 대해 e^{M n} \le f(n) \le e^{N n}임을 의미한다. 임의의 정의역 D에 대해, f(x) = g(x)+O(1) \Longleftrightarrow e^{f(x)} \asymp e^{g(x)}, 각 진술은 D의 모든 x에 대해 성립한다.
# 일반적인 함수의 차수
시간 복잡도#일반적인 시간 복잡도 표 알고리즘의 실행 시간을 분석할 때 일반적으로 접하게 되는 함수 클래스 목록이다. 각 경우에 c는 양의 상수이고 n은 무한히 증가한다. 느리게 성장하는 함수가 일반적으로 먼저 나열된다. {| class="wikitable" |- !표기법 !! 이름 !! 예시 |- |O(1) || 상수 || 정렬된 숫자 배열에서 중앙값 찾기; (-1)^n 계산; 상수 크기 순람표 사용 |- |O(\alpha (n)) || 역 아커만 함수 || 서로소 집합 자료 구조의 연산당 상각 복잡도 |- |O(\log \log n) || 이중 로그 || 균일하게 분포된 값의 정렬된 배열에서 보간 탐색을 사용하여 항목을 찾는 데 걸리는 평균 비교 횟수 |- |O(\log n) || 로그 || 이진 탐색 또는 균형 잡힌 검색 트리를 사용하여 정렬된 배열에서 항목 찾기, 이항 힙의 모든 연산 |- |O((\log n)^c)
c>1 || 다항 로그 || 행렬 체인 순서는 병렬 RAM에서 다항 로그 시간에 해결될 수 있다. |- |O(n^c)
0 || 분수 거듭제곱 || K-d 트리 검색 |- |O(n) || 선형 || 정렬되지 않은 목록이나 정렬되지 않은 배열에서 항목 찾기; 리플 캐리를 사용하여 두 개의 n비트 정수 더하기 |- |O(n\log^* n) || n 로그-스타 n || Seidel의 알고리즘을 사용하여 단순 다각형의 삼각화 수행, 여기서 \log^*(n) = \begin{cases} 0, & \text{if }n \leq 1 \\\ 1 + \log^*(\log n), & \text{if }n>1 \end{cases} |- |O(n\log n) = O(\log n!) || 선형 로그, 로그 선형, 준선형, 또는 "n\log n" || 고속 푸리에 변환 수행; 가장 빠른 비교 정렬; 힙 정렬 및 합병 정렬 |- |O(n^2) || 이차 || 학교식 곱셈으로 두 개의 n자리 숫자 곱하기; 버블 정렬, 선택 정렬 및 삽입 정렬과 같은 간단한 정렬 알고리즘; 퀵 정렬, 셸 정렬 및 트리 정렬과 같이 일반적으로 더 빠른 정렬 알고리즘의 (최악의 경우) 경계 |- |O(n^c) || 다항 또는 대수 || 트리 인접 문법 구문 분석; 이분 그래프의 최대 부합; LU 분해로 행렬식 찾기 |- |L_n[\alpha,c] = e^{(c + o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha
0 1 || 지수 || 동적 계획법을 사용하여 외판원 문제의 (정확한) 해 찾기; 무차별 대입 검색을 사용하여 두 논리적 진술이 동등한지 결정 |- |O(n!) || 계승 || 무차별 대입 검색을 통해 외판원 문제 해결; 부분 순서 집합의 모든 제한 없는 순열 생성; 라플라스 전개로 행렬식 찾기; 집합의 모든 분할 열거 |} 진술 f(n) = O(n!)은 점근적 복잡성에 대한 더 간단한 공식을 유도하기 위해 때때로 f(n) = O\left(n^n\right)로 약화된다. 이러한 예시 중 많은 경우, 실행 시간은 실제로 \Theta(g(n)) 이며, 이는 더 많은 정확성을 전달한다.
# 스몰-o 표기법
충분히 큰 x에 대해 g(x)>0인 실수 변수 x의 실수 또는 복소수 값 함수에 대해 다음과 같이 쓴다. :f(x) = o(g(x)) \quad \text{ as } x \to \infty 만약 \lim_{x\to\infty} \frac{f(x)}{g(x)} = 0. 즉, 모든 양의 상수 ε에 대해 상수 x_0가 존재하여 다음을 만족한다. :|f(x)| \leq \varepsilon g(x) \quad \text{ for all } x \geq x_0. 직관적으로, 이것은 g(x)가 f(x)보다 훨씬 빠르게 성장하거나, 동등하게 f(x)가 g(x)보다 훨씬 느리게 성장한다는 것을 의미한다. 예를 들어, 다음을 가진다. : 200x = o(x^2) and 1/x = o(1), both as x \to \infty . x의 큰 값에 대한 함수의 동작에 관심이 있을 때, 스몰-o 표기법은 해당 빅-O 표기법보다 더 강한 진술을 한다. g의 스몰-o인 모든 함수는 어떤 구간 [a,\infty)에서 g의 빅-O이기도 하지만, g의 빅-O인 모든 함수가 g의 스몰-o인 것은 아니다. 예를 들어, 2x^2 = O(x^2)이지만 2x^2 \neq o(x^2) for x\ge 1. 스몰-o는 여러 산술 연산을 따른다. 예를 들어, : c가 0이 아닌 상수이고 f = o(g)이면 c \cdot f = o(g)이고, : f = o(F)이고 g = o(G)이면 f \cdot g = o(F \cdot G). : f = o(F)이고 g = o(G)이면 f+g=o(F+G) 또한 추이성 관계를 만족한다. : f = o(g)이고 g = o(h)이면 f = o(h). 스몰-o는 유한한 경우로도 일반화될 수 있다. f(x) = o(g(x)) \quad \text{ as } x \to x_0 만약 \lim_{x\to x_0} \frac{f(x)}{g(x)} = 0. 다시 말해, \lim_{x\to x_0} \alpha(x) = 0인 어떤 \alpha(x)에 대해 f(x) = \alpha(x)g(x)이다. 이 정의는 테일러 급수를 사용하여 극한을 계산하는 데 특히 유용하다. 예를 들어: \sin x = x - \frac{x^3}{3!} + \ldots = x + o(x^2) \text{ as } x\to 0, 따라서 \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와 관련된 관계는 점근 표기법이다. \sim. 실수 값 함수 f,g에 대해, 표현식 f(x) \sim g(x)\quad \text{ as }x\to\infty 은 다음을 의미한다. \lim_{x\to\infty} \frac{f(x)}{g(x)}=1. f(x) \sim g(x)가 f(x) = (1+o(1)) g(x)와 동등하다는 것을 관찰함으로써 이를 스몰-o와 연결할 수 있다. 여기서 o(1)은 x\to\infty일 때 0으로 수렴하는 함수를 나타낸다. 이를 "f(x)는 g(x)에 점근한다"라고 읽는다. 동일한 (유한 또는 무한) 정의역에서 0이 아닌 함수에 대해, \sim 는 동치 관계를 형성한다. \sim 표기법을 사용하는 가장 유명한 정리 중 하나는 스털링 근사이다. n! \sim \bigg(\frac{n}{e}\bigg)^n \sqrt{2\pi n} \quad \text{ as }n\to\infty. 정수론에서 유명한 소수 정리는 다음을 나타낸다. \pi(x) \sim \frac{x}{\log x} \quad \text{ as }x\to\infty, 여기서 \pi(x)는 x 이하인 소수의 개수이고 \log는 x의 자연로그이다. 스몰-o와 마찬가지로, 유한 극한(양측 또는 일측)을 사용하는 버전도 있다. 예를 들어 \sin x \sim x \quad \text{ as }x\to 0. 추가 예시: x^a=o_{a,b} (e^{bx}) \quad \text{ as }x\to\infty, \text{ for any positive constants }a,b, f(x)=g(x)+o(1) \quad \Longleftrightarrow\quad e^{f(x)}\sim e^{g(x)} \quad (x\to\infty). \sum_{n=1}^\infty \frac{1}{n^s} \sim \frac{1}{s-1}\quad (x\to\infty). 마지막 점근성은 리만 제타 함수의 기본적인 속성이다.
## 커누스의 스몰 오메가 (\omega)
결과적으로 양수인 실수 값 함수 f, g에 대해, 표기법 f(x) = \omega(g(x)) \quad \text{ as } x\to\infty 은 다음을 의미한다. \lim_{x\to\infty} \frac{f(x)}{g(x)} = \infty. 다시 말해, g(x)=o(f(x)) 이다. 대략적으로 말하면, 이것은 f(x)가 g(x)보다 훨씬 빠르게 성장한다는 것을 의미한다.
## 하디-리틀우드의 Ω 표기법
하디-리틀우드의 Ω1914년 G.H. 하디와 J.E. 리틀우드는 새로운 기호 \ \Omega를 도입했으며,archive-date=2018-12-12 이는 다음과 같이 정의된다. : f(x) = \Omega\bigl(\ g(x)\ \bigr) \quad as \quad x \to \infty \quad if \quad \limsup_{x \to \infty}\ \left|\frac{\ f(x)\ }{ g(x) }\right| > 0 ~. 따라서 ~ f(x) = \Omega\bigl(\ g(x)\ \bigr) ~는 ~ f(x) = o\bigl(\ g(x)\ \bigr) ~의 부정이다. 1916년에 동일한 저자들은 \ \Omega_R\ 과 \ \Omega_L\ 이라는 두 개의 새로운 기호를 다음과 같이 정의했다.doi=10.1007/BF02422942 : f(x) = \Omega_R\bigl(\ g(x)\ \bigr) \quad as \quad x \to \infty \quad if \quad \limsup_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) } > 0\ ; : f(x)=\Omega_L\bigl(\ g(x)\ \bigr) \quad as \quad x \to \infty \quad if \quad ~ \liminf_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) }0 \, \exists n_0 \, \forall n > n_0\colon |f(n)| \leq k\, g(n) | \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 |- | f(n) = O(g(n)) 또는 f(n) \ll g(n) (비노그라도프 표기법) | 빅 O; 빅 오; 빅 오미크론 | |f|는 (상수 인자 k까지) g에 의해 위로 유계이다. | \exists k > 0 \, \forall n\in D\colon |f(n)| \leq k\, g(n) | \sup_{n \in D} \frac{\left|f(n)\right|}{g(n)} 0 \, \exists k_2>0 \, \forall n\in D\colon k_1 \, g(n) \leq f(n) \leq k_2 \, g(n) | f(n) = O(g(n)) and g(n) = O(f(n)) |- | f(n)\sim g(n) as n\to a , where a is finite, \infty or -\infty | 점근 동치 | f는 점근적으로 g와 같다. | \forall \varepsilon > 0 \, \exists n_0 \, \forall n > n_0\colon \left| \frac{f(n)}{g(n)} - 1 \right| 0 \, \forall n\in D\colon f(n) \geq k\, g(n) | \inf_{n \in D} \frac{f(n)}{g(n)} > 0 |- | f(n) = \omega(g(n)) as n\to a, where a can be finite, \infty or -\infty | 스몰 오메가; 리틀 오메가 | f는 점근적으로 g를 지배한다. | \forall k > 0 \, \exists n_0 \, \forall n > n_0 \colon f(n) > k\, g(n) ( a=\infty의 경우) | \lim_{n \to a} \frac{f(n)}{g(n)} = \infty |- #| f(n) = \Omega(g(n)) | 정수론의 빅 오메가 (하디-리틀우드) | |f|는 점근적으로 g에 의해 지배되지 않는다. | \exists k>0 \, \forall n_0 \, \exists n > n_0\colon |f(n)| \geq k\, g(n) | \limsup_{n \to \infty} \frac{\left|f(n)\right|}{g(n)} > 0 |} 극한 정의는 극한의 근방에서 g(n) > 0을 가정한다. 극한이 \infty일 때는 충분히 큰 n에 대해 g(n)>0임을 의미한다. 컴퓨터 과학 및 조합론은 빅 O, 빅 세타 \Theta, 스몰 o, 스몰 오메가 \omega 및 커누스의 빅 오메가 \Omega 표기법을 사용한다. 해석적 수론은 종종 빅 O, 스몰 o, 하디의 \asymp, 하디-리틀우드의 빅 오메가 \Omega (+, − 또는 ± 첨자 유무), 비노그라도프의 \ll 및 \gg 표기법 및 \sim 표기법을 사용한다. Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, « Notation », page xxiii. American Mathematical Society, Providence RI, 2015. 스몰 오메가 \omega 표기법은 해석학이나 정수론에서 자주 사용되지 않는다. for example it is omitted in: url-status=live
## 다른 표기법을 사용한 근사의 품질
알고리즘 분석 비공식적으로, 특히 컴퓨터 과학에서 빅-O 표기법은 주어진 맥락에서 빅-세타 \Theta 표기법이 더 사실적으로 적절할 수 있는 점근적으로 정확한 경계를 설명하는 데 다소 다르게 사용될 수 있다.p=57 예를 들어, 함수 T(n)=73n^3+22n^2+58를 고려할 때, 다음은 모두 일반적으로 허용되지만, 더 느슨한 경계(아래 1번)보다 더 엄격한 경계(아래 2, 3, 4번)가 일반적으로 훨씬 선호된다. #T(n)=O(n^{100}) #T(n)=O(n^{3}) #T(n)=\Theta(n^3) #T(n)\sim 73n^3 as n\to\infty. 이 세 진술은 모두 참이지만, 각 진술에 포함된 정보는 점진적으로 더 많다. 그러나 일부 분야에서는 빅-O 표기법(위 목록의 2번)이 빅-세타 표기법(위 목록의 3번)보다 더 일반적으로 사용될 수 있다. 예를 들어, T(n)이 입력 크기 n에 대한 새로 개발된 알고리즘의 실행 시간을 나타내는 경우, 알고리즘의 개발자와 사용자는 하한 또는 점근적 동작에 대한 명시적인 진술 없이 실행되는 데 걸리는 시간에 상한을 두는 것을 더 선호할 수 있다.
## 바흐만-란다우 표기법의 확장
컴퓨터 과학에서 때때로 사용되는 또 다른 표기법은 다항 로그 인자를 숨기는 \tilde{O}(소프트-O로 읽음)이다. 두 가지 정의가 사용되고 있다. 일부 저자는 f(n) = \tilde{O}(g(n))을 어떤 k에 대해 f(n)=O(g(n)\log^k n)의 약어로 사용하는 반면, 다른 저자는 f(n)=O(g(n)\log^k g(n))의 약어로 사용한다.p=74–75 g(n)이 n에 대한 다항식일 때는 차이가 없지만, 후자의 정의는 예를 들어 n2^n = \tilde O(2^n)라고 말할 수 있게 하는 반면, 전자의 정의는 어떤 상수 k에 대해 \log^k n = \tilde O(1)을 허용한다. 일부 저자는 후자의 정의와 동일한 목적으로 O*를 사용한다.url-status=live See sect.2.3, p.551. 본질적으로 이는 빅-O 표기법으로, 로그 인자를 무시한다. 왜냐하면 다른 초-로그 함수들의 성장률 효과가 큰 입력 매개변수에 대한 성장률 폭발을 나타내며, 이는 로그 성장 인자(들)에 의해 기여된 더 미세한 효과보다 나쁜 실행 시간 성능을 예측하는 데 더 중요하기 때문이다. 이 표기법은 종종 당면한 문제에 대해 너무 엄격하게 제한된 성장률 내에서의 "사소한 시비"를 피하기 위해 사용된다(왜냐하면 \log^k n = o(n^\varepsilon) 어떤 상수 k와 어떤 \varepsilon>0. 또한 다음과 같이 정의된 L 표기법 :L_n[\alpha,c] = e^{(c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha, 은 \log n 관점에서 다항식과 지수 함수 사이에 있는 함수에 편리하다.
# 일반화 및 관련 용도
노름 벡터 공간에서 값을 취하는 함수로의 일반화는 간단하다(절댓값을 노름으로 대체). 여기서 f와 g는 같은 공간에서 값을 취할 필요는 없다. 임의의 위상군에서 값을 취하는 함수 g로의 일반화도 가능하다. "극한 과정" x\to x_0는 임의의 필터 기저를 도입함으로써 일반화될 수도 있다. 즉, 유향 그물 f와 g로 일반화될 수 있다. o 표기법은 매우 일반적인 공간에서 미분과 미분가능성을 정의하는 데 사용될 수 있으며, 또한 함수들의 (점근적) 동등성을 정의하는 데도 사용될 수 있다. : f\sim g \iff (f-g) \in o(g) 이는 동치 관계이며 위에서 언급한 "f는 \Theta(g)" 관계보다 더 제한적인 개념이다. (만약 f와 g가 양의 실수 값 함수라면 \lim f/g = 1로 축소된다.) 예를 들어, 2x=\Theta(x)는 참이지만 2x-x \ne o(x) 는 거짓이다.
# 역사
보아-레이몬드, 바흐만-란다우, 하디, 비노그라도프, 커누스 표기법의 역사를 간략하게 설명한다. 1870년, 파울 뒤 부아-레이몬드(Paul du Bois-Reymond)url=https://link.springer.com/article/10.1007/BF02420041는 f(x) \succ \phi(x) , f(x) \sim g(x) , f(x) \prec \phi(x)를 각각 다음과 같이 정의했다. \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. 이들은 널리 채택되지 않았고 오늘날에는 사용되지 않는다. 첫 번째와 세 번째는 대칭성을 가진다. f(x) \prec \phi(x)는 \phi(x) \succ f(x)와 동일한 의미이다. 나중에 란다우는 \sim 를 f(x)/\phi(x)의 극한이 1과 같다는 좁은 의미로 채택했다. 이 표기법들은 오늘날에는 사용되지 않는다. 기호 O는 1894년 정수론학자 파울 바흐만이 그의 책 "Analytische Zahlentheorie" (해석적 수론) 2권에서 처음 도입했다.url=https://archive.org/stream/dieanalytischeza00bachuoft#page/402/mode/2up 정수론학자 에드문트 란다우가 이를 채택했고, 1909년에 o 표기법을 도입하는 데 영감을 얻었다. 따라서 둘 다 현재 란다우 기호라고 불린다. 이 표기법들은 1950년대에 점근 해석을 위해 응용 수학에서 사용되었다.isbn=978-0-486-60318-6. 기호 \Omega(“~의 o가 아님”이라는 의미에서)는 1914년 하디와 리틀우드에 의해 도입되었다. 하디와 리틀우드는 또한 1916년에 \Omega_R(“오른쪽”)과 \Omega_L(“왼쪽”) 기호를 도입했다. 이 \Omega 표기법은 적어도 1950년대부터 정수론에서 다소 일반적으로 사용되었다.E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951) \sim 기호는 이전에 다른 의미로 사용되었지만, 1909년 란다우와 1910년 하디에 의해 현대적인 정의가 주어졌다. 하디는 그의 논문의 같은 페이지 바로 위에서 \asymp 기호를 정의했으며, 여기서 f(x)\asymp g(x)는 f(x)=O(g(x))와 g(x)=O(f(x))가 모두 만족됨을 의미한다. 이 표기법은 현재도 해석적 수론에서 사용되고 있다.chapter=1.6. Some notations 하디는 그의 논문에서 \mathbin{\,\asymp\;\;\;\;\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!-} 기호를 제안했는데, 여기서 f \mathbin{\,\asymp\;\;\;\;\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!-} g는 어떤 상수 K\not=0에 대해 f\sim Kg임을 의미한다 (이는 보아-레이몬드의 f\sim g 표기법에 해당한다). 1930년대, 비노그라도프는 f(x) \ll g(x)와 g(x) \gg f(x) 표기법을 대중화시켰는데, 이 둘은 모두 f(x)=O(g(x))를 의미한다. 이 표기법은 해석적 수론에서 표준이 되었다. 1970년대에 도널드 커누스가 빅-O를 컴퓨터 과학에서 대중화시켰고, 하디의 f(x)\asymp g(x)에 대해 f(x)=\Theta(g(x))라는 다른 표기법을 제안했으며, 하디와 리틀우드 오메가 표기법에 대해 다른 정의를 제안했다. 하디는 \preccurlyeq 기호를 도입했고, 1910년 논문 "Orders of Infinity"에서 보아-레이몬드의 \prec (및 이미 언급된 다른 기호들)를 옹호했지만, 세 편의 논문(1910–1913)에서만 사용했다. 그의 거의 400편에 달하는 나머지 논문과 책에서는 란다우 기호 O와 o를 일관되게 사용했다.publisher=Clarendon Press, Oxford 하디의 기호 \preccurlyeq와 \mathbin{\,\asymp\;\;\;\;\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!-}는 더 이상 사용되지 않는다.
# 표기법 문제

## 화살표
수학에서 x\to\infty 와 같은 표현은 극한의 존재를 나타낸다. 빅-O 표기법과 관련 표기법인 \Omega, \Theta, \gg, \ll, \asymp에는 스몰-o, \sim, \omega 표기법과 달리 암시된 극한이 없다. f(x)=O(g(x)) \;\; (x\to\infty)와 같은 표기법은 기호의 남용으로 간주될 수 있다.
## 등호
어떤 이들은 f(x)=O(g(x))를 기호의 남용으로 간주한다. 등호의 사용이 이 진술이 가지지 않는 대칭성을 암시하여 오해의 소지가 있기 때문이다. 드 브라윈이 말했듯이, O(x)=O(x^2)는 참이지만 O(x^2)=O(x)는 참이 아니다.url-status=live 커누스는 이러한 진술을 "단방향 등식"이라고 설명한다. 왜냐하면 양변을 뒤집을 수 있다면, "우리는 n=O(n^2)와 n^2=O(n^2)라는 항등식으로부터 n=n^2와 같은 터무니없는 것을 추론할 수 있기 때문"이다.url-status=live 다른 편지에서 커누스는 또한 다음과 같이 지적했다.url-status=live (Unabridged version date=2008-05-13) text= 등호는 그러한 표기법에 대해 대칭적이지 않다. [이 표기법에서] 수학자들은 관습적으로 '=' 기호를 영어에서 'is'라는 단어를 사용하듯이 사용한다. 아리스토텔레스는 남자이지만, 남자가 반드시 아리스토텔레스는 아니다. 이러한 이유로 일부는 집합론적 표기법을 사용하고 f(x) \in O(g(x)) 라고 쓰도록 옹호한다. "f(x)는 O(g(x))의 원소이다" 또는 "f(x)는 O(g(x)) 집합에 있다"Snd라고 읽으며, O(g(x))를 h(x)=O(g(x))를 만족하는 모든 함수 h(x)의 클래스로 생각한다. 그러나 등호의 사용은 관례적이며 다음과 같은 더 복잡한 표현에서 더 편리하다. f(x) = g(x) + O(h(x)) = O(k(x)). 정수론에서 널리 사용되는 비노그라도프 표기법 \ll과 \gg는 이러한 결함이 없다. 이는 빅-O가 등식보다는 부등식을 나타냄을 더 명확하게 보여주기 때문이다. 또한 빅-O 표기법이 부족한 대칭성을 즐긴다. f(x)\ll g(x)는 g(x)\gg f(x)와 동일한 의미이다. 조합론과 컴퓨터 과학에서는 이러한 표기법이 거의 보이지 않는다.
## 조판
빅-O는 이탤릭체 대문자 "OSpace+double"로 조판되며, 다음 예시와 같다: O(n^2).Donald E. Knuth, The art of computer programming. Vol. 1. Fundamental algorithms, third edition, Addison Wesley Longman, 1997. Section 1.2.11.1.Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd ed.), Addison-Wesley, 1994. Section 9.2, p. 443. TeX에서는 수학 모드 안에서 단순히 'O'를 입력하면 생성된다. 그리스어 이름의 바흐만-란다우 표기법과 달리 특별한 기호가 필요하지 않다. 그러나 일부 저자는 대신 필기체 변형 \mathcal{O}를 사용한다.Sivaram Ambikasaran and Eric Darve, An \mathcal O (N \log N) Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices, J. Scientific Computing **57** (2013), no. 3, 477–501.Saket Saurabh and Meirav Zehavi, (k,n-k)-Max-Cut: An \mathcal{O}^*(2^p)-Time Algorithm and a Polynomial Kernel, Algorithmica **80** (2018), no. 12, 3844–3860. 빅-O는 원래 "order of"("Ordnung", Bachmann 1894)를 의미하며, 따라서 라틴 문자이다. 바흐만도 란다우도 이를 "Omicron"이라고 부른 적이 없다. 이 기호는 훨씬 나중에(1976년) 커누스에 의해 대문자 오미크론으로 간주되었는데, 아마도 Omega 기호에 대한 그의 정의와 관련이 있을 것이다. 숫자 0은 사용해서는 안 된다.