[자료구조] 알고리즘의 분석

• 좋은 알고리즘?

- 수행시간이 적다.

- 사용된 메모리 공간이 적다.

• 알고리즘의 평가 기준

- 공간 복잡도(Space Complexity) : 알고리즘 수행에 필요한 메모리 공간

- 시간 복잡도(Time Complexity) : 알고리즘의 수행 시간

• 공간 복잡도 분석

- 공간 복잡도 : 고정공간(입력값 상관없이 독립적) + 가변공간(입력 크기)

* 고정공간 : 문제의 인스탄스(입출력 크기)에 무관, 일정한 양의 메모리 공간

* 가변공간 : 문제의 인스탄스에 따라 가변적인 메모리 공간

• 공간 복잡도 분석 예

float sum(float list[], int n) {

 float tempsum = 0;

 int i; 

 for(i = 0; i < n; i++) 

tempsum += list[i]; 

 return tempsum; 

}

- 고정공간 : i, n, tempsum

- 가변공간 : list[] -값에 의한 호출(call by value), 참조에 의한 호출(call by reference)는 언어에 따라 달라질 수 있다. 

- 총 공간의 양 : 2*sizeof(int) + sizeof(float) + ?

• 시간 복잡도 분석

- 분석 방법

 * 실험적 수행시간 측정 (machine-dependent estimation)

: 동일한 HW 및 SW 사용

: 알고리즘의 구현 및 테스트 필요

: 제한된 입력에 의한 실험 (입력크기가 큰값이 들어가면 수행시간이 한없이 길어짐)

-> 가급적 사용하지 않음

-> 가장 정확하긴하다.

      EX >

void main( void )
{
     clock_t start, finish;
     double duration;
     start = clock();
     // 수행시갂을 측정하고 하는 코드....
     // .... finish = clock();
     duration = (double)(finish - start) / CLOCKS_PER_SEC;
     printf("%f 초입니다.\n", duration);
 } 

 * 알고리즘에서 수행되는 문장들의 스텝 수를 계산하여 측정(machine-independent estimation)

: 프로그램 구현 없이 알고리즘에서 문장이 수행되는 스텝 수를 계산하여 분석

: 스텝 수의 계산 방법

- s/e(steps/execution) : 각 문장에 대한 스텝 수 계산

- Frequency : 각 문장이 실행되는 빈도 계산

- 각 문장에 대한 총 스텝 수 : (s/e) X (frequency)

EX >

 - n 개의 실수 값들의 합을 계산하는 함수