Page 35 -

더 빠른 컴퓨터를 사용할 가치 추정 실행 시간에 신경 써야 한다면 우리는 작성하는 프로그램에 대한
“더 빠른 컴퓨터에서 실행한다면 이 문제를 얼마나 더 빨리 해결할 수 있을까?”하는 질문에 답을 해
보아야 한다. 이때도 마찬가지로 실행 시간의 증가도를 알면 필요한 정보를 정확히 알아낼 수 있다.
무어의 법칙으로 알려진 규칙에 따르면 지금으로부터 18개월 후에는 두 배 빠르고 두 배의 메모리
용량을 가진 컴퓨터를 살 수 있고, 5년 후에는 10배 빠르고 10배의 메모리 용량을 가진 컴퓨터를 똑
같은 돈으로 살 수 있다.10배 빠르고 10배나 많은 메모리를 가진 컴퓨터를 사면 10배나 더 큰 문제
를 해결할 수 있을 것이라고 생각하기 쉽지만, 이차나 삼차 표 4.1.5 10배 큰 문제를 10배 빠른 컴퓨터에서 실행할

증가도를 가진 알고리즘을 실행할 때는 그렇지 않다. 금융 모 때 프로그램의 증가도에 따른 실행 시간 영향
델을 매일 실행하는 투자 은행가, 실험 데이터를 분석하는 프 증가도 실행 시간 증가율
로그램을 실행하는 과학자, 혹은 설계를 시뮬레이션하는 엔 선형 1
지니어에게는 완료하는 데 몇 시간씩 걸리는 프로그램을 실 선형 로그 1
행하는 일이 흔하다. 삼차 증가도를 가진 알고리즘을 실행하 이차 10
는 프로그램을 사용하고 있으며 그저 새 컴퓨터가 필요해서
삼차 100
가 아니라 10배 많은 데이터를 처리하기 위해 10배 빠르고
지수 무한대
10배 많은 메모리를 가진 컴퓨터를 산다고 생각해보자. 어림
짐작으로도 시간이 기존보다 100배는 더 걸릴 것이다! 이런
상황에서는 선형이나 선형 로그 증가도를 가진 알고리즘이 필요한 상황이다. 실행 시간이 선형으로
증가하는 경우에만 10배 빠르고 10배나 많은 메모리를 가진 컴퓨터로 동일한 시간에 10배 많은 데이
터를 처리할 수 있다. 다시 말해 알고리즘의 실행 시간 증가도가 이차나 삼차의 경우에는 무어의 법
칙에 따른 성능 향상을 기대할 수 없다.

프로그램의 비교 우리는 늘 프로그램을 개선할 방법을 강구하며, 다양하게 개선한 프로그램의 효율성

을 평가하기 위해 종종 가설을 확장하거나 수정한다. 성능을 예측할 수 있는 능력을 갖게 되면 개발
하는 동안 성능이 더 좋은 방법을 이용해 설계할 수 있다. 대부분의 경우 데이터가 늘어남에 따라 늘
어나는 실행 시간을 더욱 정확히 예측하고 비교하는 가설을 세울 수 있다. 이때 증가도는 특정 알고
리즘을 관련된 모든 알고리즘들과 비교할 수 있게 해주므로 매우 유용하다. 예를 들어 문제를 해결하
는 선형 로그 알고리즘을 설계한 후에는 이 문제를 해결할 수 있는 2차, 혹은 3차 알고리즘에 대해서
는 관심이 떨어지게 된다.

주의할 점 프로그램의 성능을 분석할 때 모순되거나 잘못된 결과가 나오는 경우가 있는데, 이는 모두
우리가 세운 가설이 잘못된 가정에 기반하고 있을 때 발생한다. 새로운 가정에 기반해 새로운 가설을

세울 수 있지만, 가설을 더 구체적으로 세울수록 분석할 때 더 많은 주의가 필요하다.

명령 실행 시간 각 명령을 실행하는 데 늘 똑같은 시간에 걸린다고 가정하는 것은 올바르지 않다. 예
를 들어 최신의 컴퓨터들은 메모리를 효율적으로 접근하기 위해 캐시(cache) 기법을 사용하는데 이때
큰 배열 안에서 멀리 떨어진 요소를 접근할 때 시간이 더 많이 걸린다. doublingtest.py를 오래 실행
하면 threesum.py에서 발생하는 캐시 효과를 발견할 수 있을 것이다. 시간 증가도가 8에 접근하는 듯

488