2.5 요약¶
1. 핵심 정리¶
알고리즘 효율 평가
- 시간 효율과 공간 효율은 알고리즘의 우수성을 평가하는 두 가지 주요 지표다.
- 실제 측정으로 알고리즘 효율을 평가할 수 있지만, 측정 환경의 영향을 없애기 어렵고 많은 컴퓨팅 자원이 든다.
- 복잡도 분석은 실제 측정의 단점을 극복한다. 분석 결과는 모든 실행 플랫폼에 적용할 수 있으며, 데이터 크기에 따른 알고리즘 효율을 보여 준다.
시간 복잡도
- 시간 복잡도는 데이터 양이 증가할 때 알고리즘 실행 시간이 증가하는 추세를 측정하여 효율을 효과적으로 평가한다. 다만 입력 데이터가 적거나 시간 복잡도가 같은 경우처럼, 알고리즘 효율의 우열을 정확히 비교할 수 없는 상황도 있다.
- 최악 시간 복잡도는 빅 \(O\) 표기법으로 나타내며 함수의 점근적 상한에 해당한다. \(n\)이 양의 무한대로 향할 때 연산 횟수 \(T(n)\)의 증가 차수를 반영한다.
- 시간 복잡도를 구하는 과정은 두 단계다. 먼저 연산 횟수를 세고, 그다음 점근적 상한을 판단한다.
- 대표적인 시간 복잡도를 낮은 순서대로 나열하면 \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n \log n)\), \(O(n^2)\), \(O(2^n)\), \(O(n!)\) 등이 있다.
- 일부 알고리즘의 시간 복잡도는 고정되어 있지 않고 입력 데이터의 분포에 따라 달라진다. 시간 복잡도는 최악, 최선, 평균 시간 복잡도로 나뉜다. 최선의 경우에 도달하려면 대개 입력 데이터가 엄격한 조건을 만족해야 하므로 최선 시간 복잡도는 거의 쓰지 않는다.
- 평균 시간 복잡도는 무작위 입력 데이터에서의 실행 효율을 반영하므로 실제 응용에서의 알고리즘 성능에 가장 가깝다. 이를 계산하려면 입력 데이터의 분포와 이를 종합한 기댓값을 구해야 한다.
공간 복잡도
- 공간 복잡도는 시간 복잡도와 비슷하게, 데이터 양이 증가할 때 알고리즘이 차지하는 메모리 공간이 증가하는 추세를 측정한다.
- 알고리즘 실행에 쓰이는 메모리 공간은 입력 공간, 임시 공간, 출력 공간으로 나뉜다. 보통 입력 공간은 공간 복잡도 계산에 포함하지 않는다. 임시 공간은 임시 데이터, 스택 프레임 공간, 명령어 공간으로 나뉘며, 스택 프레임 공간은 보통 재귀 함수에서만 공간 복잡도에 영향을 준다.
- 보통 최악 공간 복잡도에만 관심을 둔다. 즉, 가장 불리한 입력 데이터와 실행 시점을 기준으로 공간 복잡도를 계산한다.
- 대표적인 공간 복잡도를 낮은 순서대로 나열하면 \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n^2)\), \(O(2^n)\) 등이 있다.
2. Q & A¶
Q: 꼬리 재귀의 공간 복잡도는 \(O(1)\)인가?
이론적으로 꼬리 재귀 함수의 공간 복잡도는 \(O(1)\)로 최적화할 수 있다. 그러나 Java, Python, C++, Go, C# 등 대다수 프로그래밍 언어는 자동 꼬리 재귀 최적화를 지원하지 않으므로, 보통 공간 복잡도를 \(O(n)\)으로 본다.
Q: 함수와 메서드라는 두 용어는 어떻게 다른가?
함수(function)는 독립적으로 실행할 수 있으며, 모든 인수가 명시적으로 전달된다. 메서드(method)는 객체와 연결되어 있고, 자신을 호출하는 객체에 암묵적으로 전달되며, 클래스 인스턴스에 포함된 데이터를 조작할 수 있다.
몇 가지 흔히 쓰는 프로그래밍 언어를 예로 살펴보자.
- C는 절차적 프로그래밍 언어로 객체 지향 개념이 없으므로 함수만 있다. 다만 구조체(struct)를 만들어 객체 지향 프로그래밍을 흉내 낼 수 있으며, 구조체에 연결된 함수는 다른 언어의 메서드에 해당한다.
- Java와 C#은 객체 지향 프로그래밍 언어로, 코드 블록(메서드)은 보통 클래스의 일부다. 정적 메서드는 클래스에 묶여 있고 특정 인스턴스 변수에 접근할 수 없으므로 함수와 비슷하게 동작한다.
- C++와 Python은 절차적 프로그래밍(함수)과 객체 지향 프로그래밍(메서드)을 모두 지원한다.
Q: ‘대표적인 공간 복잡도 유형’ 그림은 사용 공간의 절대적인 크기를 나타내는가?
아니다. 이 그림은 공간 복잡도를 보여 주므로, 사용 공간의 절대적인 크기가 아니라 증가 추세를 나타낸다.
\(n = 8\)이라고 놓으면 각 곡선의 값이 해당 함수와 일치하지 않을 수 있다. 이는 각 곡선에 상수항을 넣어 값의 범위를 보기 편한 크기로 줄였기 때문이다.
실제로는 각 방법의 ‘상수항’에 해당하는 비용을 보통 알 수 없으므로, \(n = 8\)일 때는 복잡도만으로 최적의 해법을 고르기 어렵다. 반면 \(n = 8^5\)일 때는 증가 추세가 지배적인 영향을 주므로 훨씬 쉽게 선택할 수 있다.
Q 실제 사용 상황에 따라 시간이나 공간을 희생하도록 알고리즘을 설계하기도 하는가?
실제 응용에서는 대부분 공간을 더 사용하여 시간을 줄이는 쪽을 선택한다. 예를 들어 데이터베이스 인덱스에서는 보통 B+ 트리나 해시 인덱스를 구축한다. 메모리 공간을 많이 사용하는 대신 \(O(\log n)\), 나아가 \(O(1)\)의 효율적인 조회가 가능하다.
공간 자원이 귀한 상황에서는 시간을 더 들여 공간을 절약하기도 한다. 예를 들어 임베디드 개발에서는 장치 메모리가 귀하므로, 해시 테이블 대신 배열에서 순차 탐색을 수행할 수 있다. 메모리 사용량을 줄이는 대가로 탐색 속도가 느려진다.