열혈 자료구조 - 1-2. 알고리즘의 성능 분석 방법(1)

수학과 관련해서 기본적으로 알고 있어야 하는 부분

- 지수, 로그에 관한 기본적인 지식이 있어야 이해할 수 있음

- x축을 데이터의 개수, y축을 데이터를 처리하는데 걸리는 시간이라고 가정하고 설명

- 알고리즘, 자료구조별로 데이터 별 처리하는데 걸리는 시간을 보고 판단해야 함

 

 알고리즘을 평가하는 요소

- 시간 복잡도 : 얼마나 빠른가, CPU에게 얼마나 부담을 주는가

- 공간 복잡도 : 얼마나 메모리를 적게 쓰는가

- 시간 복잡도를 더 중요하게 평가

    -> 메모리는 쓰고 지우는 것을 반복해 부족한 경우는 거의 없기 때문에 접근을 하면서 시간을 얼마나 쓰는지를 더 중요하게 생각하게 됨

- 공간 복잡도는 보조적인 평가 요소라는 느낌을 가짐

 

복잡도의 평가 방법

- 시간 복잡도

    -> 중심이 되는 특정 연산의 횟수를 세어 CPU가 얼마나 많은 일을 하는지를 측정

    -> 데이터 수에 대한 연산횟수에 대한 함수를 구함

    -> 함수를 보게되면 데이터에 따른 연산 횟수를 직관적으로 볼 수 있음

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

    -> 데이터의 수가 적은 경우 수행 속도는 큰 의미가 없음

    -> 데이터 수가 적을 경우에는 일반적으로 만족되는 결과가 나오기 때문

    -> 데이터의 수에 따른 수행 속도의 변화 정도(패턴)를 기준으로 함

    -> 위와 같은 경우 데이터가 n보다 적은 경우에는 B를 선택하고 많은 경우는 A를 선택한다고 생각하는 것이 일반적

    -> 하지만 데이터가 n보다 적은 경우는 큰 의미를 갖지 않음