[자료 구조] 알고리즘 평가 방법

1. 왜!! 우리는 알고리즘 성능 방법을 알아야 하는가???

  - 세상에는 좋은 알고리즘이 많다. 그러나 상황에 맞게 쓰기위해서는 무조건 좋다고 최고가 아니다. 

  예를 들어보면, 세상에서 제일 빠른 알고리즘이 있다고 치자. 그런데 메모리를 1G가를 차지 않다. 그런데 우리는 초소형 장비(메모리10M)에 해당 알고리즘을 사용해야한다. 

  이때 1G가를 차지 하는 알고리즘을 좋다고 할수 있는것인가?? 절때 아닌것이다. 그래서 우리는 가장 최적의 알고리즘을 찾는 방법을 배워야한다. 

2. 알고리즘 평가 항목

  1) 속도

    - 얼마나 빠른가?

- 시간 복잡도(알고리즘 수행시간 분석 결과)로 평가

  2) 메모리

    - 얼마나 메모리를 필요로 하는가?

- 공간복잡도(메모리 사용량에 대한 분석 결과)로 평가

  * 최적의 알고리즘은 "빠른 속도"와 "적은 메모리 사용"을 모두 만족 시키는 알고리즘이다.

  * 현업에서는 서버급 프로그램쪽에서는 메모리가 충분하기에 속도를 최 우선시하고 메모리를 부가적인 문제로 본다.

    그러나 요즘에는 물리적 한계에 직면해서 서서히 메모리최적화가 필요한 시기가 오고있다. 

3. 알고리즘 평가 방법

  1) 속도(시간복잡도) 평가 방법

    (1) 연산 횟수: 얼마나 많은 연상이 이루어지는냐?

    (2) 처리해야할 데이터수 : 얼마나 많이 처리해야하는냐

    - 위를 2개를 식으로 하면 처리할 데이터수를 n으로 했을시 연산 횟수 함수를 T(n)이라고할수있다.

  2) 메모리(공간복잡도) 평가 방법

    - 알고리즘을 구현하기 위해서 메모리를 얼마나 많이 상용하는가?

  3) 예시) 

    (1) 속도 관점)

      - 데이터가 100개 전까지는 A알고리즘이 사용을 추천 

- 데이터가 100개 이상 150 미만일때는 B알고리즘 추천

- 데이터가 200개 이상일떄는 C알고리즘 추천 

    (2) 메모리 관점

- 데이터가 200개 전까지는 A,B,C 어떤 알고리즘을 써도상관 없으나,
         데이터가 200개 이상일땐부터는 A알고리즘을 사용해야한다

  *결론

    - 단순히 빠르다고 특정 알고리즘을 쓰기보다는 현재 상황에 맞게 알고리즘을 사용하는게 최고의 방법이다.