알고리즘의 분석

경험적 분석과 수학적 분석

 - 경험적 분석 : 알고리즘을 프로그래밍 언어로 구현한 뒤에 이를 실행 시간을 비교해 보는 것

 - 수학적 분석 : 알고리즘을 프로그래밍 언어로 구현함이 없이 단지 알고리즘 자체만을 가지고 수학적 분석을 하는 것

 

최악의 경우와 최선의 경우

 - 최악의 경우 : 알고리즘을 수행하는데 가장 많은 시간과 공간을 필요로 하는 경우

 - 최선의 경우 : 가장 작은 시간과 공간을 필요로 하는 경우

 (- 평균의 경우 : 평균적인 시간과 공간을 필요로 하는 경우)

 

 최악의 경우는 알고리즘의 성능을 표현하는데 많이 사용된다. 아무리 시간이 오래 걸린다고 해도 이 최악의 경우는 넘지 않는 다는 것을 보증하는 셈이므로 그렇다. 실제로도 알고리즘은 최악의 경우 보다 빠른 속도로 실행되게 된다.

 

알고리즘 분석의 단계

 - 첫단계 : 알고리즘을 판단할 수 있는 입력자료를 결정하는 것 / 여러가지 종류의 임의의 자료를 같은 알고리즘에 대해 계속 적용시키다 보면 어느정도의 실행 시간의 범위가 정해진다.

 - 두번째 단계 : 알고리즘을 구성하는 동작들을 추상적이고 기본적인 동작들로 분해하여 그 동작들의 수행 시간을 계산하여 보는 것이다. 예를들어, 정렬 알고리즘을 생각한다면 정렬 알고리즘은 기본적인 동작들로 비교와 교환이 있다. 이 비교와 교환에 대한 cpu의 동작 시간을 구하여 조합하여 보면 알고리즘이 수행하는 데 필요한 시간을 구할 수 있다.

 - 세번째 단계 : 수학적인 알고리즘 분석을 한다.

 

알고리즘의 유형

 - 알고리즘 분석의 결과는 입력되는 자료의 수 N에 대하여 수행시간을 함수 관계로 표현한 것이다.

  1 : 입력 자료의 수에 관계 없이 일정한 실행시간을 갖는다.

       프로그램에서 대부분의 명령들은 한 번만 실행되거나, 단지 몇 번만 실행이 된다. 전체적인 프로그램이 이런 경우라면 실행시간은 상수가 된다. 이 유형은 알고리즘의 설계시 도전해 볼만한 것이다.

 

  logN : 입력자료수 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형이다. 이 유형의 알고리즘도 굉장히 바람직한 실행시간을 갖는다. 예를 들어, 성능이 좋은 검색 알고리즘은 대부분 log N의 수행시간을 갖는다.

 

  N : 입력자료의 수에 따라 선형적으로 실행시간이 걸리는 경우. 이는 입력 자료 각각에 일정 정도의 동일한 처리를 할 때 나타나는 경우이다. N이 두 배로 늘어나는 실행 시간도 두배로 늘어난다. 이 유형도 납득할 만한 실행 시간을 갖는다.

 

  NlogN : 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타난다. N이 두 배로 늘어나는 실행 시간은 두 배보다 약간 더 많이 늘어난다. 예를들어 성능이 좋은 정렬 알고리즘의 실행시간은 NlogN에 비례한다.

 

 N^2 : 이 유형은 이중 루프 내에서 입력자료를 처리하는 경우에 나타난다. N 값이 큰 값이 되면 실행시간은 감당하지 못할 정도로 커지게 된다. 그래서 이 유형의 알고리즘은 많은 양의 입력자료에 대해서는 사용이 부적절하다. N이 두배로 늘어난다면, 실행시간은 네 배로 늘어난다.

 

 N^3 : 이 유형은 앞의 유형과 비슷하게 입력 자료를 삼중 루프내에서 처리하는 경우에 나타난다. N의 값이 커짐에 따라 실행시간은 훨씬 더 커지게 된다. 역시 이 휴형의 알고리즘은 다량의 입력 자료에 대해서는 부적절하며, 문제가 있는 알고리즘이 된다. N이 두배로 늘어난다면 실행시간은 여덟배로 늘어난다.

 

 2^N :  입력자료의 수가 늘어남에 따라 급격히 실행 시간이 늘어난다. 이 유형은 흔하지는 않지만 가끔씩 알고리즘을 처음 개발할 때 보인다. 하지만 이런 알고리즘은 대부분 더 좋은 성능의 알고리즘으로 개선된다.