알고리즘의 실행 비용(시간 복잡도)을 추정하는 방법은 여러 가지가 있으며, 그중 하나가 바로 연산 횟수(operation count)를 세는 방법입니다. 이 방법에서는 덧셈, 뺄셈, 비교 등 다양한 연산 중 하나를 기준으로 선택한 뒤, 해당 연산이 알고리즘 전체에서 몇 번 수행되는지 확인함으로써 시간 복잡도를 추정할 수 있습니다.
이 방법의 성공 여부는 시간 복잡도에 가장 큰 영향을 미치는 핵심 연산을 얼마나 정확히 식별하느냐에 달려 있습니다. 모든 연산을 세는 것이 아니라, 전체 실행 시간을 지배하는 대표 연산 하나만 골라 집계해야 한다는 점이 중요합니다.
예제: 배열에서 최댓값의 인덱스 찾기
크기가 n인 배열 arr[0..n-1]이 주어졌다고 가정해 보겠습니다. 이 배열에서 가장 큰 원소의 인덱스를 찾는 알고리즘의 비용을 추정하려면, 배열의 각 원소 쌍 사이에서 수행되는 비교(comparison) 연산의 횟수를 세면 됩니다.
여기서 주의할 점은 오직 한 가지 연산만 선택한다는 것입니다. 이 알고리즘에는 반복 변수 i를 증가시키는 연산이나 인덱스 변수에 값을 할당하는 연산 등 다른 연산들도 존재하지만, 이들은 비용 계산 대상에서 제외됩니다.
알고리즘 의사 코드
getMax(arr, n):
index := 0
max := arr[0]
for i in range 1 to n - 1, do
if arr[i] > max, then
max := arr[i]
index := i
end if
done
return index핵심 포인트: 최대 수행 횟수를 기준으로 삼아야 한다
비용을 추정할 때는 가장 많이 수행되는 연산을 기준으로 선택해야 합니다. 예를 들어 버블 정렬(bubble sort) 알고리즘에서 교환(swap) 연산의 횟수를 센다고 가정해 봅시다. 이 경우 해당 연산이 언제 최대치가 되는지 반드시 고려해야 하며, 그 최대 상황을 기준으로 분석해야 가장 정확한 상한(worst case) 결과를 얻을 수 있습니다.
요약하자면, 연산 횟수 계산법은 다음 세 단계로 진행됩니다.
- 1단계: 알고리즘의 시간 복잡도를 지배하는 핵심 연산 하나를 선택합니다.
- 2단계: 입력 크기 n에 따라 해당 연산이 몇 번 수행되는지 계산합니다.
- 3단계: 최악의 경우(연산 횟수가 최대가 되는 경우)를 기준으로 비용을 분석합니다.