점근 표기법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

점근 표기법은 함수들의 성장률을 비교하는 데 사용되는 수학적 표기법이다. 주로 알고리즘의 효율성을 분석하는 데 활용되며, 빅 오(O), 빅 오메가(Ω), 빅 세타(Θ), 스몰 오(o), 스몰 오메가(ω) 등의 기호를 사용하여 함수의 상한, 하한, 또는 정확한 성장률을 나타낸다. 이러한 표기법들은 함수의 복잡도를 나타내며, 컴퓨터 과학, 특히 계산 복잡도 이론, 알고리즘, 암호학 등에서 알고리즘의 계산 시간을 평가하는 데 널리 사용된다.

점근 표기법

개요

종류	점근 표기법
분야	알고리즘 계산 복잡도 이론
관련 개념	점근적 분석 최악의 경우 평균적인 경우 Ω 표기법 Θ 표기법 o 표기법 ω 표기법

상세 정보

목적	함수의 점근적 증가율 설명
정의	함수의 상한을 나타내는 방법 (빅 오 표기법의 경우)
표기법	O(f(n))
n0	상수 n0이 존재하여 n > n0일 때 \|g(n)\| <= C\|f(n)\|을 만족하는 상수 C가 존재
g(n)	알고리즘의 실행 시간 또는 사용하는 메모리 양
f(n)	g(n)의 상한을 나타내는 함수

예시

예시 1	만약 g(n) = 3n^2 + 5n + 10이면 g(n) = O(n^2)이다.
설명	n이 충분히 커지면 n^2이 n과 상수항보다 훨씬 빠르게 증가하므로 g(n)의 증가율은 n^2에 의해 제한된다.

수학적 정의

빅 오 표기법	함수 g(n)이 O(f(n))에 속한다는 것은, 충분히 큰 n에 대해 \|g(n)\| <= C\|f(n)\|을 만족하는 양의 상수 C가 존재한다는 것을 의미한다.
빅 오메가 표기법	함수 g(n)이 Ω(f(n))에 속한다는 것은, 충분히 큰 n에 대해 \|g(n)\| >= C\|f(n)\|을 만족하는 양의 상수 C가 존재한다는 것을 의미한다.
빅 세타 표기법	함수 g(n)이 Θ(f(n))에 속한다는 것은, 충분히 큰 n에 대해 C1\|f(n)\| <= \|g(n)\| <= C2\|f(n)\|을 만족하는 양의 상수 C1, C2가 존재한다는 것을 의미한다.
작은 오 표기법	함수 g(n)이 o(f(n))에 속한다는 것은, 임의의 양의 상수 C에 대해 충분히 큰 n이 존재하여 \|g(n)\| < C\|f(n)\|을 만족한다는 것을 의미한다.
작은 오메가 표기법	함수 g(n)이 ω(f(n))에 속한다는 것은, 임의의 양의 상수 C에 대해 충분히 큰 n이 존재하여 \|g(n)\| > C\|f(n)\|을 만족한다는 것을 의미한다.

같이 보기

관련 항목	알고리즘 시간 복잡도 공간 복잡도 최적화
관련 인물	폴 바흐만 에드문트 란다우 도널드 크누스

참고 문헌

참고 서적	Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
참고 논문	Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic ϑ-functions (G. H. Hardy, J. E. Littlewood, 1914)

📚 더 읽어볼만한 페이지

알고리즘 분석 - 계산 복잡도
계산 복잡도는 알고리즘의 효율성을 평가하는 척도로, 시간, 공간 등의 자원을 고려하며, 입력 크기의 함수로 표현되고, 빅 오 표기법을 사용하여 알고리즘의 예상 성능을 파악하는 데 중요한 역할을 한다.
알고리즘 분석 - 비결정적 알고리즘
비결정적 알고리즘은 계산 과정에서 여러 선택지를 가질 수 있는 비결정론적 튜링 기계 또는 비결정성을 활용하는 프로그래밍 패러다임인 비결정론적 프로그래밍과 관련된 알고리즘을 포괄적으로 지칭한다.
점근 해석 - 마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다.
점근 해석 - 섭동 이론
섭동 이론은 정확히 풀리는 문제에 작은 변화가 있을 때 급수로 표현하여 근사해를 구하는 방법으로, 초기 해에 보정항을 더하는 방식으로 고전역학, 양자역학 등 다양한 분야에서 활용되며 섭동 형태와 적용 차수에 따라 구분된다.
수학 표기법 - 기수법
기수법은 수를 나타내는 방법 또는 체계로, 십진법을 비롯한 다양한 종류가 존재하며, 일진법, 명수법, 위치값 기수법 등으로 분류되고, 가장 널리 사용되는 십진법은 힌두-아라비아 숫자 체계를 기반으로 위치값 기수법의 발전과 0의 도입으로 수학적 계산의 효율성을 높였다.
수학 표기법 - 중위 표기법
중위 표기법은 사람이 이해하기 쉬운 연산자 표기 방식이지만, 컴퓨터가 구문 분석하기 어렵고 연산 순서를 위해 괄호나 연산자 우선순위 규칙이 필요하다.

1. 개요
2. 정의
- 2.1. 표기법 문제
3. 여러 가지 점근 표기법
4. 성질
5. 다변수 점근 표기법
6. 일반적인 함수의 증가량
7. 역사
8. 활용 예시

2. 정의

함수 f(x)와 g(x)에 대해, f(x)가 O(g(x))라는 것은 상한 점근에 관한 다음 정의와 같다.

* $x>x_0$ 를 만족하며 충분히 큰 모든 $x$ 에 대하여 $|f(x)| \le M |g(x)|$ 가 성립하도록 하는 양의 실수 $M$ 과 실수 $x_0$ 가 존재한다.
* $|x - a| < \delta$ 를 만족하는 $x$ 에 대하여 $|f(x)| \le \; M |g(x)|$ 가 성립하도록 하는 양수 $\delta$ 와 $M$ 이 존재한다.
* $\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty.$

이를 $f(x) = O(g(x))$ 혹은 $f(x) \in O(g(x))$ 로 표기하기도 한다.

예시로, 두 다항식 f, g를 다음과 같이 정의한다.

: $f(x) = 6x^4 -2x^3 +5$
: $g(x) = x^4$

이때 $f(x) = O(g(x)) \mbox{ or } O(x^4)$ 이 된다. 증명은 다음과 같다.

: $|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^3 + 5$ ( $x > 1$ 일 때)
: $|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4$ ( $x^3 < x^4$ 와 같은 방법)
: $|6x^4 - 2x^3 + 5| \le 13x^4$
: $|6x^4 - 2x^3 + 5| \le 13 |x^4|$

컴퓨터 과학에서는 좀 더 제한적인 정의가 사용되는데, f와 g는 모두 자연수의 무제한 부분 집합에서 비음의 실수로 가는 함수여야 한다. 그러면 $f(x) = O(g(x))$ 는 양의 정수 $M$ 과 $n_0$ 가 존재하여 모든 $n \ge n_0$ 에 대해 $|f(n)| \le M |g(n)|$ 가 성립함을 의미한다.

점근 표기법은 수학과 컴퓨터 과학에서 주로 사용되며, 알고리즘 분석 등에 유용하다.

$f(x)=O(g(x))$ 는 x가 충분히 클 때 함수 f가 함수 g''에 비례하거나 그 이하로 억제됨을 나타낸다.

2.1. 표기법 문제

$f(x) = O(g(x))$ 라는 표현에서 등호는 일반적인 등호와는 다른 의미를 가진다. 예를 들어, $O(x) = O(x^2)$ 로 표기할 수는 있지만, $O(x^2) = O(x)$ 와 같이 쓰는 것은 잘못된 표기이다. 이는 기호의 남용으로 볼 수 있다.

이러한 문제를 방지하기 위해, $O(g(x))$ 를 해당하는 함수들의 집합으로 정의하고, $f(x) \in O(g(x))$ 과 같이 표기하기도 한다. 이는 기호의 원래 정의와 잘 부합한다.

3. 여러 가지 점근 표기법

👆

좌우로 밀어서 보기

표기법	설명	수학적 정의
$f(n) \in O(g(n))$	상한 점근	\lim_{n \to \infty} \left>\frac{f(n)}{g(n)}\right\| < \infty
$f(n) \in o(g(n))$		$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$
$f(n) \in \Omega(g(n))$	하한 점근	\lim_{n \to \infty} \left>\frac{f(n)}{g(n)}\right\| > 0
$f(n) \in \omega(g(n))$		$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$
$f(n) \in \Theta(g(n))$	상한/하한 점근	0 < \lim_{n \to \infty} \left>\frac{f(n)}{g(n)}\right\| < \infty

Õ 표기법은 O 표기법의 일종으로,

\tilde{O} (g(n))

는

O(g(n) \, \log^k g(n))

(

k

는 임의의 상수)를 의미한다. 이 표기법은 함수의 로그 증가 비율을 무시하는 의미를 가지고 있다.

4. 성질

* 추이율: $f(n) = O(g(n))$ 이고 $g(n) = O(h(n))$ 이면 $f(n) = O(h(n))$ 이다.
* 합: $O(f(n)) + O(f(n)) = O(f(n))$ 이다.
* 곱: $O(f(n)) O(g(n)) = O(f(n)g(n))$ 이고, $f(n) O(g(n)) = O(f(n)g(n))$ 이다.
* 상수 배: $c \neq 0$ 인 상수 $c$ 에 대해, $O(cf(n)) = O(f(n))$ 이다.

5. 다변수 점근 표기법

Big O^영어 (그리고 작은 o, Ω 등)는 여러 변수와 함께 사용할 수 있다. $f$ 와 $g$ 가 $\R^n$ 의 어떤 부분 집합에서 정의된 두 함수라고 가정할 때, 다음과 같이 정의한다.

: $f(\mathbf{x})$ 는 $\mathbf{x}\to\infty$ 일 때 $O(g(\mathbf{x}))$ 이다.

이것은 상수 $M$ 과 $C > 0$ 가 존재하여 $x_i \geq M$ 을 만족하는 모든 $\mathbf{x}$ 에 대해 $|f(\mathbf{x})| \le C |g(\mathbf{x})|$ 가 성립하는 것을 의미한다. 어떤 $i$ 에 대해 $x_i \geq M$ 이라는 조건은 $\|\mathbf{x}\|_{\infty} \ge M$ 으로 쓸 수 있으며, 여기서 $\|\mathbf{x}\|_{\infty}$ 는 체비쇼프 노름을 나타낸다.

예를 들어,
: $f(n,m) = n^2 + m^3 + O(n+m) \quad (n,m\to\infty)$
라는 명제는 상수 C와 M이 존재하여
: $|f(n,m) - (n^2 + m^3)| \le C |n+m|$
$m \geq M$ 또는 $n \geq M$ 중 하나라도 성립할 때마다 위 식이 성립함을 뜻한다.

이 정의는 $\mathbf{x}$ 의 모든 좌표가 무한대로 증가하는 것을 허용한다. 특히,
: $f(n,m) = O(n^m) \quad (n,m\to\infty)$
(즉, $\exists C \,\exists M \,\forall n \,\forall m\,\cdots$ )라는 명제는
: $\forall m\colon~f(n,m) = O(n^m) \quad (n\to\infty)$
(즉, $\forall m \, \exists C \, \exists M \, \forall n \, \cdots$ )와는 상당히 다르다.

6. 일반적인 함수의 증가량

알고리즘의 실행 시간을 분석할 때 일반적으로 발생하는 함수 클래스는 다음과 같다. 각 경우에 c는 양의 상수이고, n은 무한대로 증가한다. 일반적으로 느리게 증가하는 함수가 먼저 나열된다.

👆

좌우로 밀어서 보기

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

컴퓨터 과학, 특히 계산 복잡도 이론, 알고리즘, 암호학에서는 알고리즘의 계산 시간을 평가하기 위해 O-표기법을 자주 사용한다.

알고리즘의 계산량 평가에 자주 사용되는 O-표기법 함수의 종류는 다음과 같다.

이들 중에서도 특히 중요한 것에는 개별 명칭(다항 시간 등)이 붙어 있다.

아래에서 n은 알고리즘에 입력되는 데이터의 비트 수를 나타낸다.

주의해야 할 것은 알고리즘에 정수 N을 입력할 때이다. N의 비트 수 n은 대략 log₂ N이므로, 예를 들어 "다항 시간"이라고 할 때, 이는 N의 다항식이 아닌 n의 다항식을 나타낸다.

👆

좌우로 밀어서 보기

표기법	이름	알고리즘 예시
$O\left(1\right)$	상수 시간	(정수의) 짝수/홀수 판별
$O\left(\log^* n\right)$	반복 로그	Hopcroft와 Ullman에 의한 분리 집합 자료 구조의 탐색 알고리즘
$O\left(\log n\right)$	로그	정렬된 배열에서의 이진 탐색
$O\left({n^c}\right), 0< \exist c<1$	분수 지수 함수	kd 트리에서의 탐색
$O\left(n\right)$	선형 함수	정렬되지 않은 배열에서의 탐색, 이산 웨이블릿 변환
$O\left(n\log n\right)$	준선형, 선형 로그	힙 정렬, 고속 푸리에 변환
$O\left({n^2}\right)$	제곱 시간	삽입 정렬, 이산 푸리에 변환
$O\left({n^c}\right), \exist c\ge 1$	다항 시간	워셜-플로이드 알고리즘
$O{(2^n)}$	지수 시간 (exponential, geometric이라고도 함)	(현재 가장 빠른) 외판원 문제의 (엄밀 해) 해법
$O\left(n!\right)$	팩토리얼 함수	두 논리식의 동형 판별, 외판원 문제의 (가능한) 해의 열거
$O\left(2^{c^n}\right) \exist c>0$	이중 지수 시간	AC단일화자의 완비 집합 탐색

7. 역사

폴 바흐만이 1894년 그의 저서 《해석적 수론》(Analytische Zahlentheorie)의 두 번째 권에서 빅오 표기법을 처음 소개했다. 에드문트 란다우는 이를 채택하고 1909년 리틀오 표기법을 도입하는 데 영감을 주었다. 이 두 표기법은 현재 란다우 기호라고도 불린다.

1914년 G.H. 하디와 J.E. 리틀우드는 새로운 기호 $\Omega$ 를 도입했다. 이들은 1916년에 $\Omega_R$ 과 $\Omega_L$ 기호를 도입했는데, 이는 현대 기호 $\Omega_+$ 및 $\Omega_-$ 의 전신이다.

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

하디와 리틀우드가 처음 정의한 $\Omega$ 표기법은 현재 사용되는 정의와 약간 다르다. 오늘날의 정의에서는 $\Omega(g)$ 가 O-표기법의 정의에서 크고 작음을 반전시킨 것이지만, 하디 등의 정의에서는 $\Omega(g)$ 는 o(g)를 만족하지 않는 것으로 정의되었다.

👆

좌우로 밀어서 보기

표기법	의미	비공식적인 정의	형식적인 정의
$f(n) \in O(g(n))$ $f(n) = O(g(n))$ $f(n) \preceq g(n)$ $f(n) \ll g(n)$	$f$ 는 점근적으로(상수배를 제외하고) $g$ 에 의해 위에서 억제된다	k에 대해, 충분히 큰 n에서 $>f(n)\| \leq k\cdot g(n)$	\exists k>0 \; \exists n_0 \; \forall n>n_0 \;>f(n)\| \leq k\cdot \|g(n)\|
$f(n) \in \Omega(g(n))$ $f(n) = \Omega(g(n))$ $f(n) \succeq g(n)$ $f(n) \gg g(n)$	두 가지 정의:	HL의 정의:	HL의 정의:
$f(n) \in \Theta(g(n))$ $f(n) = \Theta(g(n))$ $f(n) \asymp g(n)$	$f$ 는 점근적으로 $g$ 에 의해 위와 아래 모두에서 억제된다	k₁, k₂에 대해, 충분히 큰 n에서 $k_1\cdot g(n) \leq>f(n)\| \leq k_2\cdot g(n)$	$\exists k_1>0 \; \exists k_2>0 \; \exists n_0 \; \forall n>n_0 \; k_1\cdot g(n) \leq f(n) \leq k_2\cdot g(n)$
$f(n) \in o(g(n))$ $f(n) = o(g(n))$ $f(n) \prec g(n)$	$f$ 는 점근적으로 $g$ 에 의해 지배된다	k를 고정할 때마다 충분히 큰 n을 취하면 $>f(n)\| \le k\cdot\|g(n)\|$	\forall k>0 \; \exists n_0 \; \forall n>n_0 \;>f(n)\| \le k\cdot \|g(n)\|
$f(n) \in \omega(g(n))$ $f(n) = \omega(g(n))$ $f(n) \succ g(n)$	$f$ 는 점근적으로 $g$ 를 지배한다	k를 고정할 때마다 충분히 큰 n을 취하면 $>f(n)\| \ge k\cdot\|g(n)\|$	\forall k>0 \; \exists n_0 \; \forall n>n_0 \;>f(n)\| \ge k\cdot \|g(n)\|
$f(n)\sim g(n)\!$	$f$ 는 점근적으로 $g$ 와 같다	$f(n)/g(n) \to 1$	\forall \varepsilon>0\;\exists n_0\;\forall n>n_0\;\left>{f(n) \over g(n)}-1\right\|<\varepsilon

8. 활용 예시

버블 정렬은 n개의 요소로 이루어진 열을 정렬할 때 O^영어( n² )만큼 시간이 걸린다. 퀵 정렬을 사용하면 평균 시간을 O^영어( n log n)으로 줄일 수 있지만, 최악의 경우에는 O^영어( n² )만큼 걸릴 수 있다.

n차 정방 행렬의 고유값을 구하는 알고리즘은 적어도 행렬에 포함된 n²개의 요소를 읽어야 한다. 따라서 고유값 알고리즘의 시간 복잡도는 최소 Ω(n²)이다. 즉, 일반적인 행렬의 고유값을 n²보다 더 빨리 계산하는 알고리즘은 없다.