단계수를 결정하려는 동기는 같은 기능을 수행하는 두 프로그램의 시간 복잡도를 비교하거나 인스턴스 특성의 변화에 따른 실행 시간의 증가를 예측할 수 있게 하기 위한 것이다. 하지만 프로그램의 정확한 단계수를 결정하는 것은 매우 어려운 일이다.
[점근적 표기법] 알고리즘의 수행시간을 분석할 때는 항상 입력 크기가 충분히 클 때에 대해 분석하는 것을 점근적 분석이라 하며, 입력의 크기에 따라 증가하는 비율을 점근적 증가율이라 할 때, 이러한 표기법을 점근적 표기법이라 한다. 표기법으로는 O-표기법(big oh), Ω-표기법(Omega), Θ-표기법(theta) 등이 있다.
[균형분기점(break even point)] 만약 두 프로그램의 시간 복잡도가 C1n2 + C2n과 C3n일 때 충분히 큰 n에 대해 C3n의 시간 복잡도를 가진 프로그램의 시간 복잡도가 훨씬 빠른 것을 알 수 있다. C1= 1, C2 = 2, C3 = 100이면 n ≤ 98에 대해 C1n2 + C2n ≤ C3n이 되고, n > 98에 대해 C1n2 + C2n > C3n이 된다. C1, C2, C3의 값이 어떻든지 복잡도가 C3n인 프로그램이 빠를 수 있는 조건이 되는 n이 존재할 것이다. 이러한 n의 값을 균형분기점(break even point)이라 하고 위의 경우에는 균형 분기점이 되는 n은 98이 된다. 만약 이 균형 분기점이 0이라면 C3n의 복잡도를 가진 프로그램이 항상 빠를 것이다.
[O-표기법(big oh)] n ≥ n0 인 모든 n에 대해서 f(n) ≤ c·g(n)을 만족하는 양의 상수 c와 n0이 존재한다면 반드시 f(n) = O(g(n))을 만족하고, f(n)은 g(n)의 big oh라고 읽는다.
[Ω-표기법(Omega)] n ≥ n0 인 모든 n에 대해서 f(n)≥c·g(n)인, 이 조건을 만족하는 두 양의 상수 c와 n0가 존재하기만 하면 f(n) = Ω(g(n))이다.
[Θ-표기법(theta)] n ≥ n0 인 모든 n에 대해서 c1·g(n) ≤ f(n) ≤ c2·g(n)을 만족하는 세 양의 상수 c1, c2와 n0가 존재하기만 하면 f(n) = Θ(g(n))이다.
세타 표기법은 빅오나 오메가 표기법보다 더 정확하여 Ο-표기법처럼 터무니없이 큰 함수를 잡거나 Ω-표기법처럼 터무니없이 작은 함수를 잡는 경우가 없다. 이들 연산 차수에 대한 상대적인 관계는 다음과 같다.
|
O(1)〈 O(log2n)〈 O(n)〈 O(nlog2n)〈 O(n2 )〈 O(n3 )〈 O(2n )〈 O(n!) |