Big-O 표기법

알고리즘의 실행 시간과 메모리 공간은 알고리즘에 입력되는 인수의 개수에 따라 증가한다. 알고리즘의 실행 시간이 다음과 같은 함수라고 가정한다. 여기서, n은 알고리즘에 입력되는 인수의 개수이다.

T(n) = n² + 3n + 1

위의 식에서 n이 매우 크다면 실행 시간은 n² 항의 영향을 가장 많이 받기 때문에 다음 식과 같이 근사적으로 나타낼 수 있다.

T(n) = n² 

이와 같이 실행 시간이나 메모리 공간를 나타낼 때 그것에 가장 많은 영향을 주는 항으로 나타내는 방법을 Big-O 표기법 (Big-O Notation)이라고 한다.

Big-O 표기법의 종류에는 다음과 같은 것들이 있다.

함수	이름
1	Constant
log n	Logarithmic
n	Linear
n log n	Log Linear
n2	Quadratic
n3	Cubic
2n	Exponential