#2. 알고리즘의 성능 분석 방법

알고리즘의 성능을 분석하기 위해서는 수학에 대한 기초적인 개념을 먼저 요구한다.

이 두가지 그래프를 봤을 때 x축이 '데이터의 갯수', y축이 '데이터 연산의 횟수(소요 시간)' 으로 본다.

 

예를 들어

A알고리즘은 데이터 처리 방식이 지수함수 그래프를 그린다.

라고 하면 데이터의 갯수에 따라 소요 시간이 급증하는 모양이 될 것이다.

= 안좋은 알고리즘

 

반대로

B알고리즘은 데이터 처리 방식이 로그함수 그래프를 그린다.

라고 한다면 데이터 갯수가 늘어난다고 해도 소요시간이 크게 증가하지 않는 흐름이 될 것이다.

= 사용하기 좋은 알고리즘

 

이정도의 개념을 깔고 간다.

 

알고리즘 평가 요소

1. 시간 복잡도

얼마나 빠른가 / CPU(연산)에 얼마나 부담을 주는가 로 판단한다

 

2. 공간 복잡도

얼마나 메모리를 적게 사용하는가 = 메모리 접근 횟수 등에 따라 연산 시간이 증가한다.

: 결국 시간과 연관된 평가 요소로

 

시간 복잡도가 더 중요한 가중치를 가지고 있다.

 

시간 복잡도의 평가 방법으로는

1. 중심이 되는 특정 연산의 횟수를 세어서 평가

2. 데이터 수에 대한 연산 횟수의 함수 T(n) 을 구함

으로 두가지가 될 것이다.

사실 1번의 경우 우리가 일일이 세어보는 것은 불가능하다.

실제 코딩을 하다보면 데이터 표본/시행 횟수가 천 단위를 가뿐히 넘어가는 경우가 허다하기 때문에

2번의 경우로 시간 복잡도를 평가하게 될 것이다.

 

알고리즘의 수행속도 비교 기준

1. 데이터 수가 적은 경우의 수행속도는 큰 의미가 없다.

이 경우 대부분의 알고리즘은 큰 차이를 보이지 않는다.

연산 속도 등의 중요 기준에서 유의미한 차이는 데이터의 수가 많을 때 나타난다.

 

2. 데이터 수에 따른 수행 속도의 변화 정도를 기준으로 한다.

두 알고리즘을 평가할 때의 기준은,

데이터의 수가 늘어날 때 연산 횟수가 어떤 유형을 보이면서 증가하는지 그의 패턴이 중요하다.

 : 이 때 패턴을 수학식으로 T(n) 으로 표현할 수 있다.