Page 31 -

이런 추정 기법들은 파이썬 프로그램의 추상적인 세계와 프로그램을 실행하는 컴퓨터의 실세계를 연
결해주기 때문에 중요하다. 추정 기법의 모델에서는 프로그램을 실행하기 위해 사용하는 컴퓨터의
특성이 작용하지 않으므로, 이 분석 기법들은 알고리즘을 시스템으로부터 분리해낸다. threesum.py
3
실행 시간의 증가도가 n 이라는 것은 이 프로그램을 파이썬으로 구현했는지, 혹은 이 프로그램을 랩
톱, 모바일 폰, 슈퍼컴퓨터에서 실행하는지와 무관하며, 숫자 쌍 세 개 모두를 조사한다는 사실에 의
존한다. 컴퓨터와 시스템의 특성은 프로그램 문장과 기계어 명령 간의 관계에 대한 가정 사항 및 두
배 추정으로서 우리가 관찰한 실제 실행 시간에 모두 요약되어 있다. 우리가 사용하는 알고리즘이 증

가도를 결정한다. 알고리즘의 성능을 이해하고 이 지식을 모든 컴퓨터에 적용할 수 있으므로 알고리
즘과 시스템의 분리는 아주 강력한 개념이다. 사실 고전 알고리즘의 성능은 수십 년 전에 분석되었지
만, 이 지식은 오늘날의 컴퓨터에도 여전히 적용된다.

지금까지 설명한 경험적 혹은 수학적 분석을 통해 일정한 가정 사항들(각 명령은 실행할 때마다 매번
동일한 시간이 걸린다거나, 실행 시간이 일정한 형태를 취한다는 등)에 기반해 모델을 만들 수 있다.
상세한 모델을 만들 필요가 있는 프로그램은 많지 않지만, 여러분이 작성하는 모든 프로그램이 실행하
는 데 시간이 얼마나 걸릴지 개략적으로 예측할 수 있어야 한다. 실행 비용에 주의하라. 먼저 실험이나
수학적 분석 혹은 이 둘을 모두 이용해 두 배 추정해보는 편이 좋다. 두 배 추정을 통해 얻은 정보는 상
당히 유용하며, 아마 여러분은 프로그램을 실행할 때마다 두 배 추정을 해보고 검증하게 될 것이다. 실
제로 프로그램이 끝날 때까지 기다리는 동안 이렇게 시간을 보내는 것도 아주 좋은 방법이다!

증가도의 종류 파이썬 프로그램을 작성할 때 우리는 그저 기본적인 구조체(문장, 조건문, 반복문, 함
수 호출)를 몇 가지 사용할 뿐이므로, 우리 프로그램의 증가도는 주로 [표 4.1.2]에 요약된 함수 중
하나로 나타난다. 각 함수들 뒤에는 두 배 추정 증가치가 나오는데, 프로그램을 실행해 검증할 수 있
다. 다음 소절에서 간단히 설명하겠지만, 여러분은 이런 증가도를 보이는 프로그램들을 이미 실행해
왔다.

상수 실행 시간 증가도가 상수인 프로그램은 작업을 완료하기 위해 언제나 고정된 수의 문장을 실행
하므로 실행 시간이 문제의 크기에 따라 변하지 않는다. helloworld.py(프로그램 1.1.1)와 leapyear.
py(프로그램 1.2.5) 등 1장에서 만들어 본 프로그램들이 이 범주에 속하는데, 이 프로그램들은 그저

문장들을 한 번씩 실행할 뿐이다.
표준 산술 데이터 타입에 적용되는 파이썬 연산은 모두 일정한 시간이 걸린다. 다시 말해, 큰 숫자
에 연산을 적용한다고 해도 작은 숫자에 연산을 적용하는 경우보다 실행 시간이 오래 걸리지 않는다

(한가지 예외가 있는데, 아주 많은 숫자로 이루어진 정수에 적용하는 시간은 일정한 시간보다 더 걸
릴 수 있다. 자세한 내용은 이번 절 뒤에 나오는 Q&A 절을 참조하라). 파이썬 math 모듈의 함수들도
일정한 시간이 걸린다. 여기서 ‘일정한 시간’이라고 말한 것에 주의하라. 예를 들어 math.atan2()는
math.hypot()보다 시간이 걸릴 수 있다.

로그 함수 실행 시간이 로그 함수로 늘어나는 프로그램은 불변 시간 프로그램보다 그다지 느리지 않
다. 문제 크기의 로그 함수에 따라 실행 시간이 늘어나는 프로그램의 대표적인 예로는 정렬된 배열

484