1-2 알고리즘 성능분석

알고리즘 성능은 어케 분석하는가

 

#1 알고리즘 평가요소

우선 알고리즘을 평가하는 두가지 요소는 다음과 같다.

- 어떠한 알고리즘이 어떠한 상황에서 더 빠르고 더 느린가

- 어떠한 알고리즘이 어떠한 상황에서 메모리를 더 적게 더 많게  쓰는가

 

즉 '속도'와 '메모리 사용량'으로 평가하는데 

 

'속도'에 해당하는 알고리즘의 수행시간 분석결과를 '시간복잡도'라 한다. ( Time Complexity )

'메모리 사용량'에 대한 분석결과를 '공간복잡도'라 한다. ( Space Complexity )

 

일반적으로 알고리즘 평가할 때 중요도는

실행 '속도' > '메모리 사용량' 으로 속도에 관심을 더 둔다.

 

그럼 '속도'를 어떻게 측정하는가

---

#2 알고리즘 수행속도 평가방법

- 연산횟수를 센다.

- 처리해야할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.

 

이때 당연히 연산횟수가 적어야 빠른 알고리즘이다.

 

그리고 함수 T(n)을 구성하는 이유는

데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있기 때문이다.

 

즉 함수T(n)으로 구성하면 표든 그래프든 변화 정도를 한눈에 파악할 수 있다.

이는 둘 이상의 알고리즘을 비교하기가 용이해진다는 장점이 있다.

알고리즘을 서로 비교하기 쉬워짐