정의
실행 시간은 알고리즘이 입력 데이터를 처리하고 결과를 산출하는 데 소요되는 시간량을 의미한다. 일반적으로 컴퓨터 과학에서는 이 시간을 이론적 모델(예: 입력 크기 n에 대한 함수)로 표현하며, 실제 하드웨어의 시계 사이클이나 초 단위와는 구분한다.
측정 방법
- 입력 크기와 함수 관계: 알고리즘의 실행 시간 *T(n)*은 입력의 크기 n에 대한 함수로 나타낸다.
- 점근적 표기법:
- Θ(Theta): 상한과 하한이 모두 존재하는 경우, *T(n)*와 동일한 성장률을 갖는 함수를 나타낸다.
- O(Big‑O): 상한을 나타내며, 최악의 경우 실행 시간을 제한한다.
- Ω(Big‑Omega): 하한을 나타내며, 최선의 경우 실행 시간을 보장한다.
- 실험적 측정: 실제 구현을 대상으로 프로파일링 툴이나 타이머 함수를 사용해 경과 시간을 측정한다. 이때 CPU 클럭, 메모리 접근, 캐시 효과 등 하드웨어 환경이 영향을 미칠 수 있다.
주요 고려 사항
- 시간 복잡도 vs. 실행 시간: 시간 복잡도는 알고리즘의 이론적 성장률을 나타내는 반면, 실제 실행 시간은 구현 방식, 컴파일러 최적화, 하드웨어 사양 등에 따라 달라진다.
- 입력 특성: 최악, 평균, 최선의 경우를 구분하여 분석한다. 예를 들어, 퀵소트는 평균적으로 Θ(n log n)이라지만 최악의 경우 O(n²)이다.
- 상수 요인: 점근적 표기에서는 무시되는 상수와 낮은 차수 항도 실제 실행 시간에 큰 영향을 미칠 수 있다.
예시
| 알고리즘 | 입력 크기 n | 대표적 실행 시간 |
|---|---|---|
| 선형 탐색 | n | Θ(n) |
| 이진 탐색 | n | Θ(log n) |
| 병합 정렬 | n | Θ(n log n) |
| 버블 정렬 | n | Θ(n²) |
학술적 의의
실행 시간 분석은 알고리즘 설계 단계에서 효율성을 예측하고, 시스템 설계 시 자원 배분과 성능 목표를 설정하는 데 필수적인 도구이다. 또한, 동일 기능을 수행하는 여러 알고리즘 중 최적의 선택을 지원한다.
