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

#1 알고리즘 평가요소

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

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

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

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

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

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

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

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

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

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

- 연산횟수를 센다.

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

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

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

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

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

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

#1 자료구조 기본적 이해

프로그램이란 '데이터를 표현'하고, 그렇게 표현된 '데이터를 처리'하는 것이다.

'데이터 표현'은 '데이터 저장'이며 이를 담당하는 것이 자료구조다.

'데이터를 처리'는 알고리즘이 저장된 데이터를 대상으로 '문제의 해결 방법'을 뜻한다.

그냥 쉽게 말해 데이터를 담는 구조를 다루는 학문이라고보면된다.

[자료구조의 분류표]