알고리즘 분석 방법

- 알고리즘의 분석

• 시간복잡도 분석: 입력 크기에 따라 단위연산이 몇번 수행되는지 결정하는 절차
• 표현 척도
      - 단위연산: 비교, 지정 …
      - 입력 크기: 배열 크기, 리스트의 길이, 행렬에서 행과 열의 크기 …

 

- 알고리즘 분석 방법의 종류

• 모든 경우 분석: (입력 크기에만 종속) 입력값과 무관하게 결과값 일정 => 적용 한정적
• 최악 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최대
• 평균 경우 분석: (입력 크기와 입력 값에 종속) 평균
• 최선 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최소

 

- [예시] 배열 덧셈 알고리즘

: 배열에 있는 모든 수를 더해라

           case1) 단위연산: 덧셈

                      입력 크기: 배열의 크기 n

                      모든 경우 분석: 루프가 n번 반복, 따라서 T(n)=n

           case2) 단위연산: 지정문 (for루프의 첨자 지정문 i++ 포함)

                     입력 크기: 배열의 크기 n

                     모든 경우 분석: 루프가 n번 반복, 따라서 T(n)=n+n+1

                     result: n번, i++: n번, 루프 밖: 1번

 

- [예시] 교환 정렬

: 비내림차순으로 n개의 키를 정렬

           case1) 단위연산: 조건문 (S[j] S[i] 비교)

                     입력 크기: 정렬할 항목 수 n

                     모든 경우 분석: T(n)= (n-1) + … + 1 = n-1n2

           case2) 단위연산: 교환하는 연산

                     입력 크기: 정렬할 항목 수 n

                     최악 경우 분석(입력에 종속적이라):

                                조건문이 항상 참이 되는 경우 = 거꾸로 정렬된 경우

                                T(n)= n-1n2

 

- 순차 검색 알고리즘의 최악 경우 시간복잡도 분석

           단위 연산: 배열 아이템과 키 x 와의 비교 연산 ( S[location] != x )

           입력 크기: n

           - 최악 경우 W(n) = n

           - 최상(선) 경우 B(n) = 1

           - 평균 경우 A(n) = n+12

           - 입력 배열의 값에 따라 검색하는 횟수가 달라짐 => 모든 경우 분석 불가

           + 확률까지 생각한 평균 경우 분석 (배열의 아이템이 모두 다르다고 가정)

                     경우1) x가 배열 안에 있다고 가정

                                  x가 k번째에 있을 확률 = 1/n

                     경우2) x가 배열 안에 없는 경우도 고려

                                   x가 S안에 있을 확률 p, x가 k번째에 있을 확률 = p/n

        

- 알고리즘 분석에 대한 고찰

           평균이 가장 정확한 방법

           최악, 평균, 최선 중 선택? case by case, 최악도 많이 씀(평균은 최악보다 복잡함)

 

- 정확도 분석 = 정확성 분석

           어떠한 입력에 대해서도 정답을 출력하며 멈추는 알고리즘