Page 30 -

3
프로그램의 실행 시간을 분석하는 핵심 포인트는 다음과 같 n /6
다. 대부분의 프로그램에서 실행 시간은 T(n)~cf(n) 관계를
만족하는데, 이때 c는 상수, f(n)은 실행 시간의 증가도(order
166,666,667 n(n 1)(n 2)/6
of growth)라고 하는 함수이다. 잠시 후에 살펴보겠지만 대부
2
3
분의 프로그램에서 f(n)은 log n, n, n log n, n , n 등의 함 166,167,000
수이다(전통적으로 증가도 함수는 상수 계수를 붙이지 않는 4
1,000
다). f(n)이 n의 거듭제곱인 경우가 간혹 있는데, 이때는 실
그림 4.1.5 n이 커질 때의 근삿값
행 시간이 멱법칙을 만족한다고 할 수 있다. threesum.py의
3
경우 이미 실험을 통해 검증한 것처럼 실행 시간의 증가도는 n 이다. 상수 c는 명령을 실행하는 비용 알고리즘과 데이터 구조
과 상세한 빈도수에 따라 달라질 수 있지만, 잠시 후에 설명하는 것처럼 일반적으로 이 값을 알아낼
필요가 없다.

증가도는 간단한지만 실행 시간을 모델링하는 강력한 도구다. 예를 들어 증가도를 알면 두 배 추정을
3
간단히 할 수 있다. threesum.py의 경우 증가도가 n 인 것을 알고 있으므로 다음과 같은 식에 의해 문
제의 크기를 두 배로 늘리면 실행 시간이 8배로 늘어날 것이라고 예상할 수 있다.

3
3
T(2n) / T(n) → c(2n) / (cn ) = 8
이 결과는 경험적 분석으로 알아낸 값과 일치하므로, 모델과 실험이 모두 정확함을 검증한다. 이 예
제를 주의 깊게 살펴보기 바란다. 이와 똑같은 방법을 이용해 여러분이 작성하는 어떠한 프로그램의

성능도 더욱 잘 이해할 수 있기 때문이다.
커누스 교수는 어떠한 프로그램에 대해서도 실행 시간을 예측할 수 있는 정확한 수학적 모델을 만들
수 있음을 입증했으며, 많은 전문가들이 그런 모델을 개발하기 위해 노력을 쏟아왔다. 그러나 여러분

이 작성하는 프로그램의 성능을 이해하기 위해 그런 자세한 모델을 사용할 필요는 없다. 일반적으로
내부 루프 바깥에서 실행되는 명령의 비용은 무시할 수 있으며(내부 루프에서 실행되는 명령의 비용
에 비해 무시할 수 있을 정도로 작기 때문이다), 실행 시간을 추정할 때 상숫값을 알아낼 필요가 없다
(실행 시간을 예측하기 위해 두 배 추정할 때 제거되기 때문이다).

표 4.1.1 프로그램의 실행 시간 분석 예
명령 수 명령 당 실행 시간(초) 빈도 전체 시간
2
3
3
2
6 2×10 -9 n /6 - n /2 + n/3 (2n - 6n + 4n)×10 -9
2
2
4 3×10 -9 n /2 - n/2 (6n - 6n)×10 -9
4 3×10 -9 n (12n)×10 -9
10 1×10 -9 1 10×10 -9

3
총합 (2n - 10n+ 10)×10 -9
3
물결식 ~2n ×10 -9
증가도 n 3

483