Page 27 -

가설 컴퓨터 과학 초창기에 도널드 커누스 교수는 프로그램의 실행 시간을 이해하기 어렵게 만드는
요소들이 많이 있지만, 이론적으로는 어떤 프로그램을 실행하는 데 걸리는 시간을 정확히 예측할 수
있게 해주는 정확한 모델을 만드는 것이 가능한데, 그러려면 다음과 같은 것들이 필요하다.

• 프로그램을 구석구석 이해하기
• 시스템과 컴퓨터를 자세히 이해하기
• 고급 수학 분석 도구

그러니 이 작업은 전문가에게 맡겨두자. 그러나 프로그래머들은 성능을 대략 예측할 수 있는 방법이
필요하다. 다행히도 경험적인 관찰과 약간의 수학 도구를 사용하면 어느 정도는 예측할 수 있다.

두 배 가설 대부분의 프로그램의 경우 ‘입력의 크기를 두 배로 늘리면 실행 시간이 어떻게 될까?’하는
질문으로 간단히 가설을 세울 수 있다. 설명을 간단히 하기 위해 우리는 이런 가설을 ‘두 배 가설’이라
고 부르겠다. 프로그램을 개발하거나 실무에 적용할 때 이 질문을 해보는 게 아마도 실행 비용을 고

려하는 가장 간단한 방법일 것이다. 이제 과학적 기법을 통해 이 질문에 대답하는 과정을 알아보자.

경험적 분석 입력 크기를 두 배로 늘리고 실행 시간을 측정하면 아주 간단히 두 배 가설을 세울 수 있
다. 예를 들어 doublingtest.py(프로그램 4.1.2)로 threesumpy에 필요한 난수 배열을 생성할 수 있
으므로 각 단계별로 배열 길이는 두 배로 늘리고 threesum.countTriples() 실행 시간의 비율을 이전
단계(즉, 절반 크기)에 대한 비율을 출력한다. 이 프로그램
दп
을 실행함으로써 예측-검증 과정을 반복하게 된다. 이 프
512T
로그램은 처음에는 빠르게 실행되다가 점점 느려진다.

프로그램에서 메시지를 한 줄 출력할 때마다 다음 줄을 출
256T
력할 때까지 시간이 얼마나 걸릴지 궁금할 것이다. 프로그
램을 실행해보면 다음번 메시지가 출력될 때까지 걸리는 128T
시간이 8배씩 늘어나는 것을 쉽게 예상할 수 있다. 이 예 64T
상은 프로그램이 출력하는 Stopwatch 측정 결과로 검증할
௼ӝ 1K 2K 4K 8K
수 있으며, 입력 크기가 두 배로 늘어나면 실행 시간이 8배
그림 4.1.2 표준 그래프
로 늘어난다는 가설에 쉽게 도달할 수 있다. 혹은 실행 시
간을 표준 그래프(그림 4.1.2)로 그려 입력 크기가 늘어남에 따라 실행 시간이 늘어나는 비율을 보거
나, 로그-로그 그래프를 그려볼 수 있다(그림 4.1.3). threesum.py의 경우 로그-로그 그래프는 기울
3
기가 3인 직선으로서, 실행 시간이 cn 형태의 멱법칙(power law)을 만족한다는 가설에 도달하게 한다
([연습문제 4.1.29] 참조).

480