Page 36 -

하다가 배열의 크기가 커지면 실행 시간 증가도가 커지는데 이것은 캐시에 의한 영향이다.

사소한 내부 루프 내부 루프가 실행 시간에 늘 지배적인 역할을 하는 것은 아니다. 프로그램 크기가 n
일 때, 명령 실행 빈도를 나타내는 수식의 최고차항을 실행하는 데 걸리는 시간이 낮은 차수의 항목
을 실행하는 데 걸리는 시간을 무시할 수 있는 정도로 크지 않을 수 있다. 내부 루프 바깥에서 무시할
수 없는 상당한 양의 코드를 실행하는 프로그램이 종종 있기 때문이다.
4
시스템 고려 사항 일반적으로 컴퓨터 안에서는 아주 많은 일들이 일어난다. 파이썬은 컴퓨터 자원을

놓고 경쟁하는 많은 애플리케이션 중 하나일 뿐이며, 파이썬 안에서도 실행할 때 성능에 상당한 영향
을 주는 옵션과 컨트롤이 있다. 이렇게 시스템 상태가 주는 영향 때문에 반복해서 동일한 실험 결과 알고리즘과 데이터 구조
가 나와야 하는 과학적 기법과는 달리 실험 결과를 재연할 수 없는 경우가 종종 있다. 시스템에서 일
어나고 있는(우리가 통제할 수 없는) 다른 일들은 원칙적으로는 무시할 수 있을 정도로 아주 작아야
하지만, 그렇지 않은 경우가 종종 있다.

너무 사소한 차이 동일한 작업을 수행하는 서로 다른 프로그램을 비교할 때, 어떤 때는 한 프로그램
이, 다른 때는 다른 프로그램이 더 빠른 경우가 종종 있다. 지금까지 앞에서 설명한 상황에 의해 이런

결과가 생길 수 있다. ‘최고’의 프로그램을 구현하기 위해 프로그래머나 학생들은 여러 구현을 비교하
는 데에 상당한 노력을 기울이곤 하지만, 성능 최적화는 전문가에게 맡기는 편이 좋다.

입력 값 의존성 프로그램의 실행 시간 증가도를 결정할 때, 우리는 지금까지 실행 시간이 입력 값에
상대적으로 무관하다고 가정해왔다. 그러나 이런 가정이 틀릴 때는 잘못된 결과가 나오고 증가도 가
설이 틀리게 된다. 시간 증가도를 예측하기 위해 우리가 사용해온 threesum.py 예제에는 이런 문제
가 없지만, 잠시 후 입력 값에 따라 실행 시간이 달라지는 예를 여러 개 살펴볼 것이다. 물론 입력 값
에 따라 실행 시간이 달라지지 않게 설계하는 것이 좋지만, 다른 방법이 없을 때는 해결 방안을 설계
할 때 주의해야 한다. 그러나 문제에 따라 입력 값에 독립적인 실행 시간을 갖는 알고리즘을 설계하

는 것이 아주 어려울 수도 있다. 예를 들어 게놈을 처리하는 프로그램을 작성할 때, 알고리즘이 다양
한 게놈을 처리할지 어떻게 알 수 있을까? 그러나 자연 과학자들이 게놈을 설명하는 좋은 모델을 찾
고 있으므로, 이런 모델들은 우리 프로그램의 실행 시간을 예측하는 데 값진 기여를 할 수 있다.

다중 문제 파라미터 지금까지 우리는 명령 줄 인수의 값이나 입력 값의 크기 하나만을 파라미터 n으
로 사용해 성능을 측정하는 데 주안점을 두었지만, 성능에 영향을 주는 파라미터가 두 개 인상인 경
우도 적지 않다. 예를 들어 a[]를 길이 m, b[]를 길이 n의 배열이라고 가정할 때, a[i] + b[j]가 0이
되는 쌍을 알아내는 다음 코드를 생각해보자.

for i in range(m):
for j in range(n):
if a[i] + b[j] == 0:
count += 1

이런 경우에 우리는 파라미터 m과 n을 따로 처리해, 한 값을 분석할 때 다른 값은 고정시킨다. 예를

489