똑똑한 코드 작성을 위한 실전 알고리즘

41

1

장

문제 해결

그림

1-9

런타임 성능 비교

[그림

1

-

9

]는 다섯 가지 접근의 런타임 성능에 관한 세부사항을 나타낸다.

●

mutable_two()

,

double_two()

,

largest_two()

의 성능은 나머지 두 접근에 비해 서로 유사하다. 세

접근이 꽤 예측 가능해 보이는 직선 궤적 위에 있어, 마치 모두 같은 ‘종류’에 속한 것처럼 보인다.

●

tournament_two()

는 가장 비효율적이고 다른 것들과 눈에 띄게 다르게 움직인다. 데이터 포인트가 너

무 적다는 점을 감안할 때, 더 비효율적으로 ‘상향 곡선’을 그릴지 혹은 직선으로 갈지는 분명하지 않다.

●

sorting_two()

는

tournament_two()

보다 괜찮아 보이지만 나머지 세 접근보다는 느리다. 곡선이 더

위로 휘어질지 혹은 곧게 진행할지 알 수 없다.

이러한 선이 만들어진 이유를 이해하려면 알고리즘의 고유한

복잡성

complexity

을 설명하는 두 가

지 기본 개념을 배워야 한다. 다음 절에서 이어서 알아보자.

1.7

시간 복잡도와 공간 복잡도

프로그래밍 언어마다 차이가 있고 자바나 파이썬 등 일부 언어는 인터프리터에 의해 실행

되므로 기본 연산이 실행된 횟수를 계산하기 어려울 수 있다. 하지만 이를 계산해보면, 알

고리즘에 의해 기본 연산이 수행된 횟수가 문제 인스턴스