Page 37 -

들어 이 코드 부분의 실행 시간 증가도는 mn이다.
지금까지 다양한 문제점을 이야기했지만, 모든 프로그램의 실행 시간 증가도는 모든 프로그래머가

알아야 할 중요한 지식이며, 우리가 지금까지 설명한 기법들은 폭넓게 적용할 수 있다. 원칙적으로
이 기법들을 이용해 아주 세세하고 정확히 실행 시간을 예측할 수 있다고 커누스 교수는 간파했다.
일반적으로 컴퓨터 시스템은 아주 복잡하므로 세밀한 성능 분석은 전문가에게 맡기는 편이 좋지만,
지금까지 설명한 기법들은 모든 프로그램의 실행 시간을 예측하는 데 효과적으로 사용할 수 있다. 실
험 로켓이 바다에 떨어질지, 도시에 떨어질지 로켓 과학자가 예측해야 하는 것처럼, 또한, 실험 약물
이 환자를 죽일지, 살릴지 예측해야 하는 것처럼, 프로그램을 실행하는 데 몇 초가 걸릴지, 몇 년이
걸릴지 프로그램을 사용하는 모든 과학자와 엔지니어가 예측할 수 있어야 한다.

성능 보장 이따금 어떤 프로그램은 주어진 입력 크기에 무관하게 일정 시간 이내에 실행을 완료해야
하는 경우가 있다. 그러한 성능을 보장하기 위해 컴퓨터 이론가들은 극단적으로 비관적인 입장을 취
한다. 즉, 최악의 경우에 실행 시간이 어떻게 될 것인지 예측하는 것이다.
예를 들어 원자핵 반응기, 공조기, 혹은 자동차의 제동 장치를 작동시키는 소프트웨어에서는 이러한

보수적인 방법이 적절할 것이다. 이런 경우에는 소프트웨어가 주어진 시간 안에 작업을 완료하지 않
으면 재앙이 초래되므로, 제한 시간 안에 작업을 완료할 수 있음을 보장해야 한다. 일반적으로 과학
자들은 자연 세계를 연구할 때 최악의 경우를 가정하지 않는다. 생물학에서 최악의 경우는 인류의 멸
종일 것이며, 물리학에서 최악의 경우는 우주의 종말일 것이다. 그러나 자연적으로 발생하지 않고 다
른(악의성을 가질 수 있는) 사용자가 입력한 데이터를 처리하는 컴퓨터 시스템에서는 최악의 경우를
고려해야 한다. 예를 들어 성능 보장 알고리즘을 사용하지 않는 웹사이트는 해커가 웹 서비스를 아주
느리게 실행되도록 만들기 위해 보내는 악의적인 요청을 무한히 보내는 서비스 거부(denial-of-service)

공격을 받을 수 있다.
성능 보장은 과학적인 방법으로 검증하기 어렵다. 예를 들어 합병 정렬 알고리즘이 선형 로그 증가도
로 실행된다는 가설은 검증할 수 없다. 검증해야 하는 경우의 수가 너무 많기 때문이다. 합병 정렬이
느리게 실행되는 입력 값을 제시해 가설을 부정할 수는 있지만, 이게 참인지 어떻게 입증할 수 있을
까? 검증은 실험적인 방법이 아니라 수학적 모델을 이용해 검증해야 한다.

관련된 정보를 가능한 한 많이 찾아내는 것은 알고리즘 분석가의 일이고, 그 지식을 이용해 당면한
문제를 효율적으로 해결하기 위해 프로그램을 개발하는 것은 애플리케이션 프로그래머의 일이다. 예
를 들어 문제를 해결하는 2차원 알고리즘을 사용하고 있지만, 선형 로그 증가도로 실행된다고 보장

된 알고리즘을 알고 난 후 여러분은 선형 로그 알고리즘을 선호하게 될 것이다. 드문 경우이지만 해
결해야 할 특정 입력에 대해서 더 빠르게 실행되거나 선형 로그 알고리즘이 구현하기 너무 복잡한 때
는 2차원 알고리즘을 선호할 수도 있다.
이상적으로 우리는 최악의 입력에 대해서도 적절히 작동하며 우리가 주로 처리하는 입력에 대해 좋

은 성능을 발휘하는 깔끔하고 짧은 코드를 구현할 수 있게 해주는 알고리즘을 원한다. 우리가 이번
장에서 살펴보는 대부분의 고전적인 알고리즘들은 이런 특징을 가지고 있어서 다양한 애플리케이션

490