[알고리즘] 알고리즘의 분석

시간 복잡도 분석의 종류

- Every-case time complexity analysis (모든 경우)

• 최악의 경우 입력을 분석
• 입력 크기에만 종속
• 입력 값과는 무관하게 결과 값은 항상 일정

- Worst-case (최악의 경우)

• 최악에 경우 입력을 분석

- Average-case (평균의 경우)

• 모든 입력에 대해 분석
• 모든 입력에 대해 단위연산이 수행되는 기대치 (평균)
• 분석이 더 어렵다

- Best-case (최선의 경우)

• 최선의 경우 입력을 분석
• 별로 유용하지 않음

배열 덧셈의 시간복잡도 분석

• 문제 : 크기가 n인 배열 S의 모든 수를 더하라
  • 입력 : 양수 n, 배열 S[1..n]
  • 출력 : 배열 S에 있는 모든 수의 합

• 알고리즘

number sum (int n, const number S[]){
	index i;
    number result;
    
    result = 0;
    for ( i=1; i<=n; i++ )
    	return = result + S[i];
    return result;
}

• 단위 연산 : 덧셈
• 입력 크기 : 배열의 크기 n
• 모든 경우 분석
  • 배열 내용에 상관없이 for-루프가 n번 반복된다.
  • 각 루프마다 덧셈이 1회 수행된다.
  • 따라서 n에 대해서 뎃셈이 수행되는 총 횟수는 T(n) = n 이다.

교환 정렬의 시간복잡도 분석

• 문제 : 비내림차순(오름차순)으로 n개의 키를 정렬
  • 입력 : 양수 n, 배열 S[1...n]
  • 출력 : 비내림차순으로 정렬된 배열

• 알고리즘

void exchangesort (int n, keytype S[]){
	index i, j;
    for ( i=1; i<=n-1; i++ )
    	for ( j=i+1; j<=n; j++ )
        	if ( S[j] < S[i] )
            	exchange S[i] and S[j];
}

1)

• 단위 연산 : 조건문 (S[j]와 S[i]의 비교)
• 입력 크기 : 정렬할 항목의 수
• 모든 경우 분석
  • j-루프가 수행될 때마다 조건문 1번씩 수행
  • 조건문의 총 수행횟수
    - i = 1 : j-루프 n-1 번 수행
    - i = 2 : j-루프 n-2 번 수행
    - i = 3 : j-루프 n-3 번 수행
    - i = n-1 : j-루프 1번 수행
    - 따라서
    $T(n)=(n-1)+(n-2)+$...$+1=[(n-1)n]/2$ = $(1/2)n^2$ => $n^2$

2)

• 단위 연산 : 교환하는 연산 (exchange S[j] and S[i])
• 입력 크기 : 정렬할 항목의 수 n
• 최악의 경우 분석
  • 조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다.
  • 최악의 경우 = 조건문이 항상 참(true)이 되는 경우
    = 입력 배열이 거꾸로 정렬되어 있는 경우
    $T(n)=[(n-1)n]/2$ => $n^2$

순차 검색의 시간복잡도 분석

• 단위 연산 : 배열의 아이템과 키 X와 비교 연산 (S[locaton] != x)
• 입력 크기 : 배열 안에 있는 아이템의 수 n
• 평균의 경우 분석
  • 배열의 아이템이 모두 다르다고 가정한다.
  • 경우 1) x가 배열 S안에 있는 경우만 고려
    • $1<=k<=n$ 에 대해서 x가 배열의 k번째 있을 확률 = $1/n$
    • x가 배열의 k번째에 있다면,
      s를 찾기 위해서 수행하는 단위연산의 횟수 = k
    • 따라서,
      $A(n)=sum^n_{k=1}k*1/n=1/n*sum^n_{k=1}k=(1/n)*[n(n+1)]/2 = (n+1)/2$
  • 경우 2) x가 배열 S안에 없는 경우도 고려
    • x가 배열 S안에 있을 확률을 p라고 하면,
      a) x가 배열의 k번째 있을 확률 = p/n
      b) x가 배열에 없을 확률 = 1-p
    • 따라서,
      $A(n) = sum^n_{k=1}(k*(p/n))+n(1-p)$
      = $(p/n)*(n(n+1))/2)+n(1-p)$
      = $n(1-(p/2))+p/2$
    • $p=1$ -> $A(n)=(n+1)/2$
      $p=1/2$ -> $A(n)=3n/4+1/4$