시간복잡도(Time Complexity) 정리

Time Complexity

알고리즘의 시간복잡도(Time Complexity)란 함수가 입력된 값을 처리하는데 걸리는 시간을 측정한 값을 의미함.

일반적으로 Big O 기호를 사용하여 표혐함.

이때, 시간 복잡도의 입력값 크기는 점근적(asymptotically)으로 증가해서 결국 무한대까지갈 수 있음.

시간 복잡도의 측정방법은 알고리즘이 수행하는 기본적인 연산이 몇 개 인지를 세어서 확인함.

표기기호

Big O(O) : 상한(upper bound)을 의미함.

Big Omega(Ω) : 하한(lower bound)을 의미함.

Big Theta(Θ) : Big O 와 Big Omega가 같을 때를 의미함.

일반적인 시간복잡도 정리표

명칭	복잡도 수준	실행시간(T(n))	실행시간 예	예제 알고리즘
constant time(상수시간)		O(1)	10	정수가 홀수인지 짝수인지 결정하기. Determining if an integer (represented in binary) is even or odd
inverse Ackermann time		O(α(n))		Amortized time per operation using a disjoint set
iterated logarithmic time		O(log* n)		Distributed coloring of cycles
log-logarithmic		O(log log n)		Amortized time per operation using a bounded priority queue[2]
logarithmic time(로그시간)	DLOGTIME	O(log n)	log n, log(n2)	이진검색 Binary search
polylogarithmic time		poly(log n)	(log n)2
fractional power		O(nc) where 0 < c < 1	n1/2, n2/3	Searching in a kd-tree
linear time(선형시간)		O(n)	n	정렬되지 않은 배열에서 가장 작은 항목을 찾기 Finding the smallest item in an unsorted array
"n log star n" time		O(n log* n)		Seidel's polygon triangulation algorithm.
linearithmic time		O(n log n)	n log n, log n!	Fastest possible comparison sort
quadratic time(N의 2차)		O(n2)	n2	버블 정렬, 삽입정렬 Bubble sort; Insertion sort
cubic time(N의 3차 )		O(n3)	n3	Naive multiplication of two n×n matrices. Calculating partial correlation.
polynomial time(다항시간)	P	2O(log n) = poly(n)	n, n log n, n10	Karmarkar's algorithm for linear programming; AKS primality test
quasi-polynomial time	QP	2poly(log n)	nlog log n, nlog n	Best-known O(log2 n)-approximation algorithm for the directedSteiner tree problem.
sub-exponential time (first definition)	SUBEXP	O(2nε) for allε > 0	O(2log nlog log n)	Assuming complexity theoretic conjectures, BPP is contained in SUBEXP.[3]
sub-exponential time (second definition)		2o(n)	2n1/3	Best-known algorithm for integer factorization and graph isomorphism
exponential time(지수형)	E	2O(n)	1.1n, 10n	동적 프로그래밍을 이용해서 외판원 순회문제를 풀때. Solving the traveling salesman problem using dynamic programming
factorial time		O(n!)	n!	Solving the traveling salesman problem via brute-force search
exponential time(지수형)	EXPTIME	2poly(n)	2n, 2n2
double exponential time	2-EXPTIME	22poly(n)	22n	Deciding the truth of a given statement in Presburger arithmetic

수학 연산의 계산복잡도

기본 연산

연산	입력	출력	알고리즘	복잡도
덧셈	Two n-digit numbers	One n+1-digit number	Schoolbook addition with carry	Θ(n)
뺄셈	Two n-digit numbers	One n+1-digit number	Schoolbook subtraction with borrow	Θ(n)
곱셈	Two n-digit numbers	One 2n-digit number	Schoolbook long multiplication	O(n2)
			Karatsuba algorithm	O(n1.585)
			3-way Toom–Cook multiplication	O(n1.465)
			k-way Toom–Cook multiplication	O(nlog (2k − 1)/logk)
			Mixed-level Toom–Cook (Knuth 4.3.3-T)[2]	O(n 2√2 log n logn)
			Schönhage–Strassen algorithm	O(n log n log logn)
			Fürer's algorithm[3]	O(n log n 2log* n)
나눗셈	Two n-digit numbers	One n-digit number	Schoolbook long division	O(n2)
			Newton–Raphson division	O(M(n))
Square root	One n-digit number	One n-digit number	Newton's method	O(M(n))
Modular exponentiation	Two n-digit numbers and a k-bit exponent	One n-digit number	Repeated multiplication and reduction	O(2kM(n))
			Exponentiation by squaring	O(k M(n))
			Exponentiation with Montgomery reduction	O(k M(n))

대수함수

연산	입력	출력	알고리즘	복잡도
다항식 연산	One polynomial of degree n with fixed-size polynomial coefficients	One fixed-size number	Direct evaluation	Θ(n)
			Horner's method	Θ(n)
Polynomial gcd (overZ[x] or F[x])	Two polynomials of degree n with fixed-size polynomial coefficients	One polynomial of degree at most n	Euclidean algorithm	O(n2)
			Fast Euclidean algorithm [5]	O(n (log n)2 log log n)

기타 함수들

Algorithm	Applicability	Complexity
Taylor series; repeated argument reduction (e.g. exp(2x) = [exp(x)]2) and direct summation	exp, log, sin, cos	O(n1/2 M(n))
Taylor series; FFT-based acceleration	exp, log, sin, cos	O(n1/3 (log n)2 M(n))
Taylor series; binary splitting + bit burst method[7]	exp, log, sin, cos	O((log n)2 M(n))
Arithmetic-geometric mean iteration	log	O(log n M(n))

Function	Input	Algorithm	Complexity
Gamma function	n-digit number	Series approximation of the incomplete gamma function	O(n1/2 (log n)2 M(n))
	Fixed rational number	Hypergeometric series	O((log n)2 M(n))
	m/24, m an integer	Arithmetic-geometric mean iteration	O(log n M(n))
Hypergeometric function pFq	n-digit number	(As described in Borwein & Borwein)	O(n1/2 (log n)2 M(n))
	Fixed rational number	Hypergeometric series	O((log n)2 M(n))

수학적 상수들

Constant	Algorithm	Complexity
Golden ratio, φ	Newton's method	O(M(n))
Square root of 2, √2	Newton's method	O(M(n))
Euler's number, e	Binary splitting of the Taylor series for the exponential function	O(log n M(n))
	Newton inversion of the natural logarithm	O(log n M(n))
Pi, π	Binary splitting of the arctan series in Machin's formula	O((log n)2 M(n))
	Salamin–Brent algorithm	O(log n M(n))
Euler's constant, γ	Sweeney's method (approximation in terms of the exponential integral)	O((log n)2 M(n))

정수론

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two n-digit numbers	One number with at most ndigits	Euclidean algorithm	O(n2)
			Binary GCD algorithm	O(n2)
			Left/right k-ary binary GCD algorithm[8]	O(n2/ log n)
			Stehlé–Zimmermann algorithm[9]	O(log n M(n))
			Schönhage controlled Euclidean descent algorithm[10]	O(log n M(n))
Jacobi symbol	Two n-digit numbers	0, −1, or 1
			Schönhage controlled Euclidean descent algorithm[11]	O(log n M(n))
			Stehlé–Zimmermann algorithm[12]	O(log n M(n))
Factorial	A fixed-size number m	One O(m log m)-digit number	Bottom-up multiplication	O(m2 log m)
			Binary splitting	O(log m M(m log m))
			Exponentiation of the prime factors of m	O(log log m M(m logm)),[13] O(M(m log m))[1]

행렬연산

Operation	Input	Output	Algorithm	Complexity
Matrix multiplication	Two n×n matrices	One n×n matrix	Schoolbook matrix multiplication	O(n3)
			Strassen algorithm	O(n2.807)
			Coppersmith–Winograd algorithm	O(n2.376)
			Williams algorithm[14]	O(n2.373)
Matrix multiplication	One n×m matrix &  one m×p matrix	One n×p matrix	Schoolbook matrix multiplication	O(nmp)
Matrix inversion*	One n×n matrix	One n×n matrix	Gauss–Jordan elimination	O(n3)
			Strassen algorithm	O(n2.807)
			Coppersmith–Winograd algorithm	O(n2.376)
			Williams algorithm	O(n2.373)
Determinant	One n×n matrix	One number	Laplace expansion	O(n!)
			LU decomposition	O(n3)
			Bareiss algorithm	O(n3)
			Fast matrix multiplication[citation needed]	O(n2.373)
Back Substitution	Triangular matrix	n solutions	Back substitution	O(n2)[15]

참고자료

1. The Art of Computer Programming 기초알고리즘 1, 한빛미디어

2. http://en.wikipedia.org/wiki/Time_complexity

3. http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

4. http://en.wikipedia.org/wiki/Big_O_notation