2021-10-08 게시 됨2021-10-12 업데이트 됨Lecture Summary / Algorithm

[강의정리] 알고리즘 week4 (merge sort)

Divide-and-Conquer

분할정복식 설계전략
분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눔
정복(Conquer): 나눈 작은 문제를 각각 해결
통합(Convbine): 해결된 해답을 모음
이러한방식을 Top-Down(하향식) 접근 방법이라고 한다

Binary Search(이분검색): 재귀 알고리즘

분할: 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택
정복: 선택된 반쪽 배열에서 X를 찾는다
통합: 필요없음

재귀 알고리즘(recursive algorithm)에서 모든 재귀호출이 알고리즘의 마지막(꼬리) 부분에서 이루어 질 때 꼬리 재귀호출(tail recursion)이라고 함 - 그 알고리즘은 반복 알고리즘(iterative algorithm)으로 변환하기 수월ㅋ

최악의 경우 시간복잡도 분석

단위연산: x와 S[mid]의 비교
입력 크기: 배열의 크기 n(= high - low + 1)
알고리즘에서는 단위연산으로 설정한 조건문을 while루프 내에서 2번 수행하지만, 사실상 비교는 한번만 수행
(1) 어셈블리언어로는 하나의 조건 명령으로 충분히 구현 가능
(2) x를 찾기 전까지는 항상 2개의 조건문을 수행하므로 하나로 묶어서 한 단위로 취급해도 됨

경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 n/2이 되는 경우

시간복잡도를 나타내주는 재현식(recurrence)는 다음과 같다
W(n) = W(n/2)+1, n > 1이고, n = 2^k(k>=1)
W(1) = 1
이식의 해는 다음과 같이 구할 수 있다
W(1) = 1
W(2) = W(1) + 1 = 2
W(4) = w(2) + 1 = 3
W(8) = W(4) + 1 = 4
W(16) = W(8) + 1 = 5
…
W(2^k)=k+1
…
W(n) = lg n + 1

증명: 수학접 귀납법:
귀납 출발점: n=1이면, W(1) = 1 = lg 1 + 1.
귀납 가정: 2의 거듭제곱(power)인 양의 정수 n에 대해서, W(n)=lg n + 1라고 가정
귀납 단계: W(2n) = lg(2n) + 1임을 보이면 된다. 재현식을 사용하면,
W(2n) = W(n) + 1
```
  = lg n + 1 + 1
  = lg n + lg 2 + 1
  = lg(2n) + 1
```

경우 2: 일반적인 경우 - 반쪽 배열의 크기는 [n/2]이 됨

합병정렬(Mergesort)

void mergesort (int n, keytype S[]) {
  const int h = n / 2, m = n - h;
  keytype U[1..h], V[1..m];

  if(n>1) {
    copy S[1] through S[h] to U[1] through U[h];
    copy S[h+1] through S[n] to V[1] through V[m];
    mergesort(h,U);
    mergesort(m,V);
    merge(h,m,U,V,S);
  }
}

시간복잡도 분석

합병 알고리즘의 최악의 경우 시간복잡도 분석

단위연산: U[i]와 V[j]의 비교
입력크기: 2개의 입력 배열에 각각 들어있는 항목의 개수: h와 m
분석: i=h이고, j=m-1인 상태로 루프(loop)에서 빠져 나가는 때가 최악의 경우로서 (V에 있는 처음 m-1개의 항목이 S의 앞부분에 위치하고, U에 있는 h개의 모든 항목이 그 뒤에 위치하는 경우), 이때 단위연산의 실행 횟수는 h + m - 1이다. 따라서 최악의 경우 합병하는 시간복잡도는 W(h, m) = h + m - 1.

합병정렬 알고리즘의 최악의 경우 시간복잡도 분석

단위연산: 합병 알고리즘 merge에서 발생하는 비교
입력크기: 배열 S에 들어 있는 항목의 개수 n
분석: 최악의 경우 수행시간은 W(h,m) = W(h) + W(m) + h + m - 1이 된다. 여기서 W(h)는 U를 정렬하는데 걸리는 시간, W(m)은 V를 정렬하는데 걸리는 시간, 그리고 h + m - 1은 합병하는데 걸리는 시간이다. 정수 n을 2^k(k>=1)이라고 가정하면, h= n/2, m=n/2가 된다. 따라서 최악의 경우 재현식은:
W(n) = 2W(n/2)+n-1 n>1이고, n=2^k(k>=1)
W(1) = 0 왜냐하면 합병이 전혀 이루어지지 않으므로 이 재현식의 해는 아래의 도사정리의 2번을 적용하면
W(n) = O(n lg n)이 된다.

#Algorithm