하나의 문제에 대해서 여러 개의 알고리즘이 있을 수 있다.
그중 가장 효율적이고 사용 환경에 최적인 알고리즘을 결정하기 위해서는 알고리즘을 분석하고 평가하여야 한다.
알고리즘 성능 분석 방법
공간 복잡도
- 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간을 의미
- 고정 공간과 가변 공간을 합하여 구함
- 고정 공간 : 프로그램의 저장 공간과 변수 및 상수들을 저장하기 위한 공간
- 가변 공간 : 실행 과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간
시간 복잡도
- 알고리즘을 프로그램으로 실행하여 완료하는데 걸리는 시간
- 프로그램의 컴파일 시간과 실행 시간의 합으로 표현
- 정확한 실행 시간을 추정하기보다는 실행 빈도수를 구하여 사용
- 빅-오(Big Oh) 표기법을 사용하여 O(n)로 표기함
- 상수, 계수를 제외하고 가장 큰 차수만 표기함
- ex) 실행 시간 함수 : 4n+2 → O(n)
ex) 피보나치수열 알고리즘
00 fibonacci(n)
01 if(n<0) then
02 stop;
03 if(n<=1) then
04 return n;
05 f1 ← 0;
06 f2 ← 1;
07 for(i ← 2; i<=n; i ← i+1) do {
08 fn ← f1+f2;
09 f1 ← f2;
10 f2 ← fn;
11 }
12 return fn;
13 end
피보나치수열 알고리즘의 실행 빈도수 : n > 1일 경우
| 행 번호 | 실행 빈도수 | 행 번호 | 실행 빈도수 |
| 1 | 1 | 8 | n-1 |
| 2 | 0 | 9 | n-1 |
| 3 | 1 | 10 | n-1 |
| 4 | 0 | 11 | 0 |
| 5 | 1 | 12 | 1 |
| 6 | 1 | 13 | 0 |
| 7 | n |
실행 빈도수를 계산하면 1+0+1+0+1+1+n+(n-1)+(n-1)+(n-1)+0+1+0 = 4n+2가 된다.
따라서 이 알고리즘의 실행 빈도수, 즉 실행 시간은 n에 따라 정해진다.
이것을 빅-오(Big Oh) 표기법을 사용하여 O(n)으로 표기한다.