Page 34 -

이렇게 분류하는 것이 일반적이지만, 여기에 있는 것이 전부는 아니다. 실제로 알고리즘을 상세히 분
석하려면 지난 수 세기 동안 개발된 수많은 수학 도구들을 알고 있어야 한다. factors.py(프로그램
1.3.9), primesieve.py(프로그램 1.4.3), euclid.py(프로그램 2.3.1)와 같은 프로그램들의 실행 시
간을 이해하려면 확고한 정수론 기반을 갖고 있어야 한다. hashst.py(프로그램 4.4.3)와 bst.py(프
로그램 4.4.4)와 같은 알고리즘을 이해하려면 신중히 수학적으로 분석해야 한다. sqrt.py(프로그램
1.3.6)와 markov.py(프로그램 1.6.3) 프로그램은 수치해석 컴퓨팅의 대표적인 사례로서, 실행 시간은 4
원하는 결과에 접근하는 비율에 따라 달라진다. gambler.py(프로그램 1.3.8)와 percolation.py(프로

그램 2.4.6) 및 이의 변형들과 같은 몬테카를로 시뮬레이션은 상세한 수학적 모델이 없다. 알고리즘과 데이터 구조
그럼에도 불구하고 우리가 작성할 프로그램들 상당수는 [표 4.1.3]에 정리한 증가도로 정확히 설명할

수 있는 성능 특성을 가지고 있다. 따라서 합병 정렬의 실행 시간 증가도는 선형 로그 함수라고 이야
기하듯이 간단히 상위 수준에서 나타낼 수 있다. 더 간단히 표현하면 합병 정렬은 선형 로그라고 이
야기할 수도 있다. 대부분 실행 시간 증가도는 이와 같이 이야기하거나 합병 정렬은 삽입 정렬보다
빠르다는 형태로 이야기한다. 물론 이렇게 이야기할 때는 프로그램이 아니라 알고리즘을 언급하는
것이다.

예측 그저 프로그램을 실행해보면 실행 시간을 측정할 수 있지만, 문제 크기가 클 때는 좋은 방법이
아니다. 비유하자면 로켓이 제대로 발사될지 알아보기 위해 로켓을 발사해보거나, 폭탄의 파괴력을
알아보기 위해 폭발시켜보거나, 다리가 제대로 세워질지 알아보기 위해 다리를 세워보는 것과 마찬

가지다.
실행 시간의 증가도를 알면 실제로 해결해야 문제를 처리하기 위해 우리가 가진 모든 자원을 투자할
수 있도록 해결 방법에 대해 결정할 수 있게 해준다. 일반적으로 프로그램의 실행 시간 증가도에 대

한 가설을 검증하고 그 결과는 다음과 같은 형태로 활용한다.

큰 문제의 해결 가능성 추정 실행 시간에 신경 써야 한다면 우 표 4.1.4 실행 시간이 몇 초 걸리는 프로그램의
리는 작성하는 프로그램에 대한 “이 프로그램이 이 입력 데이 증가도에 따른 실행 시간 영향
터를 적절한 시간 안에 처리할 수 있을까?”하는 질문에 답을 증가도 문제 크기가 100배 커질
때의 예상 소요 시간
해보아야 한다. 예를 들어 문제 크기 n을 단 몇 초 만에 처리하
선형 몇 초
는 삼차 증가도를 가진 알고리즘은 문제 크기가 100배로 커지
면 처리하는 데 시간이 몇 주 걸릴 것이다. 문제 크기가 100배 선형 로그 몇 분
3
커지면 처리 시간이 백만(100 ) 배 늘어나므로 백만 초, 즉 몇 이차 몇 시간
n
주 걸리게 되는 것이다. 만약 100 크기의 문제를 해결해야 한 삼차 몇 주
다면 더 나은 알고리즘을 찾아야 한다. 알고리즘의 실행 시간 지수 무한 시간
증가도를 알면 프로그램이 해결할 수 있는 문제 크기의 한계를
정확히 알 수 있다. 성능을 연구하는 주된 이유는 해결할 수 있는 문제 크기의 한계를 알아내기 위한
것이다. 성능을 모르고서는 프로그램을 실행하는 데 얼마나 많은 시간이 걸릴지 알 수 없지만, 성능
을 이해하면 간단한 계산만으로도 실행 비용을 추정할 수 있다.

487