단계 수(Step Count) 방법이란?
단계 수(Step Count) 방법은 알고리즘을 분석하는 대표적인 기법 중 하나입니다. 이 방법은 알고리즘 내 각 명령문이 실제로 몇 번 실행되는지 횟수를 세고, 그 결과를 바탕으로 알고리즘의 시간 복잡도를 도출합니다.
예를 들어 순차 탐색(Sequential Search) 알고리즘이 있다고 가정해 보겠습니다. 각 명령문이 실행되는 데 각각 c1, c2 … 만큼의 시간이 소요된다면, 이 알고리즘의 시간 복잡도를 아래와 같이 계산할 수 있습니다.
| 알고리즘 | 실행 횟수 | 비용(Cost) |
|---|---|---|
| seqSearch(arr, n, key) i := 0 while i < n, do if arr[i] = key, then break end if done return i | 1 n+1 n 0/1 1 | c1 c2 c3 c4 c5 |
비용(Cost) 계산 과정
이제 최악의 경우(worst case)를 기준으로, 각 명령문의 실행 횟수에 해당 비용을 곱한 뒤 모두 더하면 다음과 같습니다.
Cost = c1 + (n+1)c2 + nc3 + c4 + c5
Cost = c1 + nc2 + c2 + nc3 + c4 + c5
Cost = n(c2 + c3) + c1 + c4 + c5
Cost = n(c2 + c3) + C
시간 복잡도 도출
여기서 상수항 c1 + c4 + c5를 하나의 상수 C로 치환하면, 최종 식은 직선의 방정식 y = mx + b와 동일한 형태가 됩니다. 즉, 입력 크기 n에 대해 비용이 선형적으로 증가하는 선형(linear) 함수임을 알 수 있습니다.
따라서 이 순차 탐색 알고리즘의 시간 복잡도는 O(n)이라고 결론지을 수 있습니다.