Page 25 -

측정 첫 번째 관문은 프로그램의 실행 시간을 정량적으로 측정 % python3 threesum.py < 1kints.txt
하는 것이다. 프로그램의 실제 실행 시간을 측정하는 것은 어렵
ڙٯ ڙٯ ڙٯ
지만, 일반적으로 근삿값으로도 충분하다. 근삿값을 얻어낼 수
있는 도구는 많이 있다. 실제 스톱워치를 사용하거나 Stopwatch
0
데이터 타입(프로그램 3.2.2)을 사용하는 방법이 가장 간단할 것 % python3 threesum.py < 2kints.txt
이다. 다양한 입력 값에 대해 프로그램을 실행하고, 각 입력 값 ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ
ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ
에 대한 시간을 측정하면 된다. ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ
ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ ڙٯ
대부분의 프로그램을 정성적으로 관찰해보면 계산 작업의 난이
2
도를 특징 짓는 문제 규모가 있다는 것을 알 수 있다. 일반적으 391930676 -763182495 371251819
-326747290 802431422 -475684132
로 문제 규모는 입력의 크기나 명령 줄 인수로 받는 값이다. 직
그림 4.1.1 프로그램 실행 시간의 측정
관적으로 생각해보면 실행 시간은 문제 규모에 따라 증가하겠지
만, 얼마나 많이 증가하느냐 하는 질문은 프로그램을 개발하거나 실행할 때마다 생긴다.
또 많은 프로그램들을 관찰하다 보면 실행 시간은 입력 자체에 대해서는 상대적으로 민감하지 않고
주로 문제 규모에 따라 달라진다는 것을 알 수 있다. 이 관계가 성립하지 않는다면 실험을 더 많이 실

행해 입력에 대한 실행 시간의 민감도를 이해하고, 심지어는 제어할 수도 있다. 이 관계가 성립하지
않는 경우가 종종 있으므로 이제는 문제 규모와 실행 시간의 관계를 더욱 잘 정량화하는 방법에 주안
점을 두자.

구체적인 예를 들어 설명하기 위해 먼저 threesum.py(프로그램 4.1.1)를 사용하겠다. 이 프로그램은
숫자 n개를 담은 배열에서 세 숫자의 합이 0이 되는 쌍의 개수를 알아낸다. 이 계산은 그저 예제를
위한 프로그램처럼 생각될 수도 있지만, 이 문제는 계산기하학에서 특히 중요한 여러 핵심적인 계산
작업과 관련되어 있다. 그러니 이 문제를 주의 깊게 살펴볼 필요가 있다. threesum.py의 문제 규모 n
과 실행 시간 사이에 어떤 관계가 있을까?

478