1- 알고리즘 분석

C++로 배우는 자료구조와 알고리즘 학습내용 정리

- 경험적 분석 / 수학적 분석

- 최악의 경우 / 최선의 경우

- 알고리즘 유형

- 알고리즘 성능 표기법

알고리즘을 분석하는 방법에는 경험적 분석 과 수학적 분석이 있다.

분석이란 특정한 문제를 해결할 때 어떠한 알고리즘을 정확히 선택하기 위한 방법이다.

결국 알고리즘이 자원을 어떻게 소모하느냐인데,

이에 대해서는 시간 소모량(걸리는 시간) vs 공간 소모량(메모리) 으로 나눌 수 있다.

일반적으로 공간 소요량보다 시간 소요량을 중요하게 여기는 경우가 많다.

경험적 분석? 

실제 코드 작성 후, 실행하여 시간을 측정한다.

데이터 수를 다르게 하여 함수관계 유추

수학적 분석?

알고리즘 자체를 가지고 수학적인 분석을 함.

최악의 경우 vs 최선의 경우

최악의 경우(Worst Case)? 가장 많은 시간과 자원을 필요로 하는 경우

최선의 경우(Best Case)? 가장 적은 시간과 자원만이 소요되는 경우

알고리즘의 성능 유형

1(상수)

- 입력 자료 수와 상관 없이 동일한 시간이 걸린다.

- 해시 검색 알고리즘 등

logN

- Divede & Conquer 방법 사용 시 (분할 정복)

- 이진 검색, 이진 트리 검색 등

N

- Scan 방법 사용시 (자료를 쭉 읽거나 할 때)

- 선형 검색 등(DB에서 리니어하게 검색하는 것 등)

NlogN

- Divide & Conquer & Merge 방법 사용시

- 병합정렬 등

N의 제곱 

- 이중 루프

- 삽입 정렬, 선택정령 등

N의 삼승

- 삼중 루프

알고리즘 성능 표기법 (Big-Oh)

- 알고리즘의 성능을 객관적으로 표현하는 방법

- 보통 T(N)에서 가장 영향력있느 항이 선택된다.

- ex)  

-> N>=1인 모든 N에 대해 T(N) <= 4N제곱 이기 때문에.