[algorithm] 분할정복 알고리즘(2)

• 전형적인 분할정복 방법이 적용된 알고리즘
  • 분할
    • 배열을 동일한 크기의 두 개의 부분배열로 분할하고
    • 입력 크기 n인 배열을 크기 n/2인 두 부분배열로 분할한다.
  • 정복
    • 각각의 부분배열을 순환적으로 정렬한 후
    • 두 부분배열을 정렬한다.
  • 결합
    • 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦
    • 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만든다.
• 합병정렬 Merge()

Merge(B[], C[], n, m){
	i=j=k=0;
    while(i<n && j<m){
    	if(B[i] <= C[j]) A[k++] = B[i++];
        else A[k++] = C[j++];
    }
    for(;i<n; i++) A[k++] = B[i];
    for(;j<m; j++) A[k++] = C[j];
    return A[0 .. n+m-1];
}

•  
  • 합병 함수 Merge() 수행시간
    • Θ(n)
  • 입력 데이터 개수 n만큼의 추가 저장 장소(B[]+C[])가 필요
  • T(n) = 2T(n/2) + Θ(n)
    
    • T(n) = O(nlogn)
• 선택문제
  • n개의 원소가 임의의 순서로 저장된 배열 A[0 .. n-1] 에서 i번째로 작은 원소를 찾는 문제
    • i=1 -> 최소값, ..., i=n/2 -> 중간값, ..., i=n -> 최대값
  • 직관적인 방법
    • 오름차순으로 정렬한 후 i번째 원소를 찾는 방법 -> O(nlogn)
    • 최소값을 찾는 과정을 i 번 반복(i-1번째 까지는 최소값을 찾은 후 삭제)  -> O(in)
  • 최솟값 찾기
    • 각 데이터를 하나씩 모두 비교하는 방법
      • n개의 데이터에 대해서 적어도 (n-1)번 비교가 필요 -> O(n)
  • 최솟값과 최댓값 모두 찾기
    • 방법1: 최솟값 찾은 후 최댓값 찾기
      • n개의 데이터에서 최솟값을 찾는데 (n-1)번 비교 + (n-1)개의 데이터에서 최댓값을 찾는데 (n-2)번 비교
        ==> 2n-3번의 비교 : O(n)
    • 방법2: 모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값과 비교
  • i번째로 작은 원소 찾기
    • 퀵정렬의 분할 함수 Partition()을 순환적으로 적용하는 방법
      • i=p -> 피벗이 찾고자 하는 i번째 원소
      • i<p -> 왼쪽 부분배열에 대해 순환적용
      • i>p -> 오른쪽 부분배열에 대해 순환적용
    • 분할
      • 피벗을 기준으로 주어진 배열을 두 부분배열로 분할하고 i가 피벗의 인덱스 p와 같으면 피벗의 값을 반환하고 종료
    • 정복
      • 인덱스 i가 포함된 부분배열에 대해 알고리즘을 순환적으로 호출하여 적용
    • 결합
      • 필요없음
  • 성능분석
    • 최악의 경우 = 퀵정렬의 최악의 경우
      • 분할함수 Partition()이 항상 하나의 부분배열만 생성하는 경우
      • 오름차순을 정렬된 상태에서 최댓값(i=n)을 찾는 경우
        • 분할함수를 호출할 때마다 피벗 인덱스는 1씩 증가
        • Partition()를 O(n)번 호출 => O(n^2)
      • 해결방법 -> 항상 일정한 비율의 두 부분배열로 분할 -> 최악의 경우에도 O(n)
    • 평균적인 경우 -> O(n)
    • 최선 O(n), 최악 O(n)
      • 일정한 비율의 두 부분배열로 분할되도록 특정 성질을 만족하는 값을 피벗으로 선택
      • 피벗 선택 방법
        • 크기 n인 배열의 원소를 5개씩 묶어서 n/5개의 그룹을 만듦
          • 5의 배수가 되지 않아 그룹을 형성하지 못한 채 남는 원소는 그대로 남겨둠
          • 각 그룹에 대해서 중간값을 찾음
          • n/5개의 중간값을 대상으로 다시 중간값을 찾음
    • 선택문제 알고리즘 분류 정리
      • 퀵 정렬의 Partition() 이용 -> 최악 O(n^2), 평균 O(n)
      • "중간값들의 중간값"이용 -> 최악 O(n), 평균 O(n)