2.1 알고리즘 효율 평가¶
알고리즘을 설계할 때는 다음 두 단계의 목표를 차례로 추구한다.
- 문제의 해법 찾기: 알고리즘은 정해진 입력 범위 안에서 문제의 올바른 해를 안정적으로 구해야 한다.
- 최적의 해법 찾기: 같은 문제에도 여러 해법이 있을 수 있으므로, 가능한 한 효율적인 알고리즘을 찾고자 한다.
즉, 문제를 해결할 수 있다는 전제하에 알고리즘 효율은 알고리즘의 우수성을 평가하는 주요 지표가 된다. 여기에는 다음 두 가지 측면이 있다.
- 시간 효율: 알고리즘의 실행 시간이 얼마나 긴가.
- 공간 효율: 알고리즘이 차지하는 메모리 공간이 얼마나 큰가.
간단히 말해, 우리의 목표는 ‘빠르면서도 메모리를 적게 사용하는’ 자료 구조와 알고리즘을 설계하는 것이다. 알고리즘 효율을 효과적으로 평가하는 일도 매우 중요하다. 그래야 여러 알고리즘을 비교하고, 이를 바탕으로 알고리즘을 설계하고 최적화할 수 있기 때문이다.
효율 평가 방법은 크게 실제 측정과 이론적 추정으로 나뉜다.
2.1.1 실제 측정¶
같은 문제를 해결할 수 있는 알고리즘 A와 알고리즘 B가 있으며, 두 알고리즘의 효율을 비교해야 한다고 하자. 가장 직접적인 방법은 컴퓨터에서 두 알고리즘을 실행하고 실행 시간과 메모리 사용량을 관찰해 기록하는 것이다. 이러한 평가 방식은 실제 상황을 반영할 수 있지만 한계도 크다.
한편으로는 측정 환경에 따른 영향을 배제하기 어렵다. 하드웨어 구성은 알고리즘 성능에 영향을 준다. 예를 들어 병렬성이 높은 알고리즘은 멀티코어 CPU에서 실행하기에 더 적합하고, 메모리 연산이 집중된 알고리즘은 고성능 메모리에서 더 좋은 성능을 보인다. 즉, 같은 알고리즘도 컴퓨터에 따라 측정 결과가 다를 수 있다. 따라서 다양한 컴퓨터에서 측정해 평균 효율을 구해야 하지만, 이는 현실적이지 않다.
다른 한편으로는 충분한 측정을 수행하는 데 매우 많은 자원이 든다. 입력 데이터의 양이 달라지면 알고리즘의 효율도 달라진다. 예를 들어 입력 데이터가 적을 때는 알고리즘 A의 실행 시간이 알고리즘 B보다 짧지만, 입력 데이터가 많을 때는 결과가 정반대일 수 있다. 따라서 설득력 있는 결론을 얻으려면 다양한 크기의 입력 데이터를 측정해야 하며, 여기에는 많은 컴퓨팅 자원이 필요하다.
2.1.2 이론적 추정¶
실제 측정에는 큰 한계가 있으므로, 계산만으로 알고리즘 효율을 평가하는 방법을 생각해 볼 수 있다. 이러한 추정 방법을 점근적 복잡도 분석(asymptotic complexity analysis), 줄여서 복잡도 분석이라고 한다.
복잡도 분석은 알고리즘 실행에 필요한 시간 및 공간 자원과 입력 데이터 크기의 관계를 나타낸다. 입력 데이터 크기가 증가할 때 알고리즘 실행에 필요한 시간과 공간이 증가하는 추세를 설명한다. 이 정의는 다소 이해하기 어려우므로 세 가지 핵심으로 나누어 살펴보자.
- ‘시간 및 공간 자원’은 각각 시간 복잡도(time complexity)와 공간 복잡도(space complexity)에 해당한다.
- ‘입력 데이터 크기가 증가할 때’는 복잡도가 알고리즘의 실행 효율과 입력 데이터 크기 사이의 관계를 반영한다는 뜻이다.
- ‘시간과 공간이 증가하는 추세’는 복잡도 분석이 실행 시간이나 사용 공간의 구체적인 값보다 시간 또는 공간이 얼마나 빠르게 증가하는지에 주목한다는 뜻이다.
복잡도 분석은 실제 측정 방법의 단점을 극복한다. 구체적으로 다음과 같은 장점이 있다.
- 실제로 코드를 실행하지 않아도 되므로 에너지를 절약하고 환경 부담을 줄인다.
- 측정 환경에 의존하지 않아 분석 결과를 모든 실행 플랫폼에 적용할 수 있다.
- 데이터 양에 따른 알고리즘 효율, 특히 데이터가 많을 때의 알고리즘 성능을 보여 준다.
참고
복잡도 개념이 아직 혼란스러워도 걱정할 필요 없다. 이후 절에서 자세히 소개한다.
복잡도 분석은 알고리즘 효율을 평가하는 ‘자’와 같다. 이를 통해 알고리즘 실행에 필요한 시간과 공간 자원을 가늠하고 여러 알고리즘의 효율을 비교할 수 있다.
복잡도는 수학적 개념이므로 초보자에게는 추상적으로 느껴지고 배우기도 다소 어려울 수 있다. 이런 관점에서는 복잡도 분석이 맨 처음 소개하기에 적절하지 않을 수도 있다. 그러나 어떤 자료 구조나 알고리즘의 특징을 논할 때는 실행 속도와 공간 사용량에 대한 분석을 피하기 어렵다.
따라서 자료 구조와 알고리즘을 깊이 학습하기 전에, 복잡도 분석을 기초적으로 이해하여 간단한 알고리즘의 복잡도를 분석할 수 있도록 하는 것을 권한다.