성능 분석

1. 성능 분석

   • 문제에 대한 여러 가지 해결 방법 중 가장 효율적이고 사용 환경에 최적인 알고리즘을 결정하는 방법

2. 알고리즘 분석 기준

   • 정확성
     • 올바른 입력이 들어왔을 때 정해진 시간 내에 올바른 결과를 출력하느냐
   • 명확성
     • 알고리즘이 얼마나 이해하기 쉬고 명확하게 작성되었는가를 판단
   • 수행량
     • 알고리즘의 특성을 나타내는 중요 연산들을 분석
   • 최적성
     • 시스템의 사용 환경에 따라 수행량과 메모리 사용량이 달라지기 때문에 환경에 최적화되어 있는가를 판단

3. 알고리즘 분석 방법

   • 공간 복잡도

     • 고정 공간 + 가변 공간

   • 실행하고 완료하는데 필요한 저장 공간 의미

     • 고정 공간 + 가변 공간
     • 고정 공간 : 프로그램의 크기나 입출력의 횟수에 상관없이 고정적으로 필요한 저장공간 (ex. 변수, 상수)
     • 가변 공간 : 실행 과정에서 사용하는 데이터와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간이다.

   • 시간 복잡도

     • 컴파일 시간 + 실행 시간

     • 실행 빈도수를 계산하여 실행 시간을 구한다.

     • ex) 피보나치수열

       • 피보나치수열은 바로 이전의 두 항의 합으로 다음의 새로운 항이 만들어지는 수열이다. 첫 번째 항을 f0이라 하고 그다음 항을 f1이라고 하면, f0 = 0, f1 = 1이 되고 일반항은 fn = f-1 + fn-2 (단, n >= 2)가 된다.

       • 더보기

         

         표1

         

         표2

         해설

         실행 빈도수를 보면 중괄호나 end는 실행 명령 무이 아니므로 실행 시간을 0으로 계산하고, 7번 행의 for 문은 하나의 실행 단위로, 계산하였다. 표 2에서 총 실행 빈도수를 계산하면 1+0+1+0+1+1+n+(n-1)+(n-1)+(n-1)+0+1+0 = 4n+2 이 된다. 따라서 이 알고리즘의 실행 빈도수, 즉 실행 시간은 n에 따라 정해 진다. 이를 시간 복잡도로 나타낼 때 빅-오(Big Oh) 표기법을 사용하여 O(n)으로 표기한다.

         위의 예에서 실행시간 함수는 4n+2이고, n 값의 변화에 따라 함숫값에 가장 큰 영향을 주는 항, 즉 4n항을 선택한다. 4n항에서 계수는 4는 생략하고 O의 오른쪽 괄호 안에 n을 표시하여 O(n)으로 표기한다.

         알고리즘에 따라 logn, n, nlogn, n2, n3, 2n으로 실행 시간 함수가 있다.