두 알고리즘의 최고차항이 같다면 어느 알고리즘이 더 나은지 얘기하기 어렵다. 다시 얘기하지만, 정답은 세부 사항에 따라 달라진다. 따라서 알고리즘 분석에서는 최고차항이 같은 함수는 계수가 달라도 동등한 것으로 간주한다.
증가 기준(order of growth)은 함수의 성장 동작이 동등하다고 간주되는 함수들의 집합이다. 예를 들어 2n, 100, n+1은 같은 증가 기준에 속하며, 이를 빅오(Big-O) 표기법으로 O(n)이라고 쓴다. 이 집합에 속한 모든 함수는 n이 선형적으로 증가하기 때문에 선형(linear)이라고도 부른다.
최고차항이 n2인 모든 함수는 O(n2)에 속한다. 이들 함수는 2차(quadratic)라고 부른다.
다음 표는 알고리즘 분석에서 가장 자주 등장하는 증가 기준을 성능이 나빠지는 순서로 나타낸 것이다.
|
증가 기준 |
이름 |
|
O(1) |
상수 |
|
O(logb n) |
로그(모든 b에 대해) |
|
O(n) |
선형 |
|
O(n logb n) |
선형 로그 |
|
O(n2) |
2차 |
|
O(n3) |
3차 |
|
O(cn) |
지수(모든 c에 대해) |
로그에서 로그의 밑(b)은 중요하지 않다. 밑이 바꿔도 상수로 곱하는 것과 같으며, 이는 증가 기준을 바꾸는 게 아니다. 마찬가지로 모든 지수 함수는 지수의 밑에 관계없이 같은 증가 기준에 속한다. 지수 함수는 매우 빠르게 성장하므로 지수 알고리즘은 작은 문제에만 유용하다.