최종 수정 : 24.12.26
성능분석
알고리즘의 성능을 평가하는 기준은 정확성, 명확성, 간결성, 시간복잡도, 공간복잡도 등이 있다. 그러나 알고리즘을 구현한 프로그램을 실행시켜 측정된 시간을 성능 평가의 객관적 기준이 되기는 어렵다. 사용된 컴퓨터의 성능, 사용된 프로그래밍 언어에 따라 수행시간은 달라질 수 있기 때문이다. 주로 공간 복잡도와 시간 복잡도에 대한 분석으로 알고리즘의 성능을 평가한다.
1. 공간 복잡도(space complexity)
프로그램을 실행시켜 완료하는 데까지 소요되는 총 저장 공간을 의미한다.
공간 복잡도 = 고정 공간 + 가변 공간
- 고정 공간은 소스 코드를 저장하기 위한 공간, 사용되는 변수와 상수의 저장 공간이다.
- 가변 공간은 실행 중에 할당되는 자료구조, 변수, 함수의 호출 등에 사용되는 공간이다.
- 공간 복잡도는 최악의 경우나 평균의 경우를 고려하여 필요한 공간을 분석한다.
2 시간 복잡도(time complexity)
프로그램을 실행시켜 완료하는 데까지 걸리는 시간이다. 이는 컴파일 시간과 실행 시간의 합이다.
시간복잡도 + 컴파일 시간 + 실행 시간
- 컴파일 시간은 프로그램의 특성과 큰 관련이 없으므로 거의 고정적인 시간이 소요된다.
- 실행 시간은 컴퓨터의 성능에 따른 영향이 크게 작용하므로 실제 실행 시간 보다 명령문의 실행 빈도수에 따라 실행 시간을 계산한다.
- 실행 빈도수의 계산은 지정문, 조건문, 반복문 내의 제어문과 반환(return)문은 실행 시간 차이가 거의 없으므로 하나의 단위 시간을 갖는 기본 명령문으로 취급하여 계산한다.
3. 연산 시간 표기법
시간 복잡도에 대한 입력의 크기를 함수로 표기하는데, 이를 위해서는 여러 개의 항을 가지는 다항식으로 표기된다. 이를 단순한 함수로 표기하기 위해 점근적 표기법(Asymptotic notation)을 사용한다.
최악의 경우가 중요하므로 Bog-O가 가장 많이 사용된다.
1) big-Oh(O)
- 점근적 상한
- 알고리즘 실행 시간의 '최악의 경우'를 나타낸다.
- f(n) = O(g(n)) 은 "f(n)은 g(n)보다 증가율이 작거나 같다"
2) big-Omega(Ω)
- 점근적 하한
- 알고리즘 실행 시간의 '최선의 경우'를 나타낸다.
- f(n) = Ω(g(n)) 은 "f(n)은 g(n)보다 증가율이 크거나 같다"
3) big-Theta(Θ)
- 위 둘의 교집합이며, 상한과 하한의 일치를 나타낸다.
☞ O(g(n))이면서 동시에 Ω(g(n))인 경우를 의미 - 알고리즘 실행시간의 '평균적인 경우'를 나타낸다.
- f(n) = Θ(g(n)) 은 "f(n)이 g(n)과 같은 증가율을 가진다"
4. 실용적인 복잡도
| 시간 복잡도 | 표기명 | 특징 |
| O(1) | 상수 시간 | ● 입력 크기와 관계없이 일정한 시가이 소요된다. ● 배열의 인덱스 접근, 스택의 push/pop 연산이 해당된다. ● 가장 효율적인 시간 복잡도 |
| O(log n) | 로그 시간 | ● 입력이 증가해도 실행 시간이 완만하게 증가한다. ● 이진 탐색, 균형 잡힌 이진 트리의 검색이 해당된다. ● 큰 입력값에도 효율적 |
| O(n) | 선형 시간 | ● 입력 크기에 비례하여 실행 시간이 증가한다. ● 배열 순회, 선형 검색이 해당된다. ● 모든 요소를 한 번씩 처리해야 할 때 사용 |
| O(n log n) | 선형 로그 시간 | ● 대부분의 효율적인 정렬 알고리즘이 이에 해당한다. ● 퀵 정렬, 병합 정렬, 힙 정력이 대표적 ● 정렬이 필요한 대규모 데이터 처리에 주로 사용 |
| O(n²) | 이차 시간 | ● 입력 크기의 제곱에 비례하여 실행 시간이 증가한다. ● 버블 정렬, 선택 정렬, 삽입 정렬이 해당된다. ● 중첩 반복문에서 주로 발생 |
| O(2ⁿ) | 지수 시간 | ● 입력 크기가 증가할 때마다 실행 시간이 기하급수적으로 증가한다. ● 재귀적 피보나치 수열, 부분집합 생성이 해당된다. ● 일반적으로 실용적이지 않은 시간 복잡도 |
표기법에 대한 대략적 의미는 다음과 같다.
| 표기법 | 의미 |
| f(n) = O(g(n)) | f는 g보다 작거나 같다, f ≤ g |
| f(n) = Ω(g(n)) | f는 g보다 크거나 같다, f ≥ g |
| f(n) = Θ(g(n)) | f는 g와 대략 같다, f = g |
참고
독학사 교재
댓글