이상학의 개발블로그

[학교-알고리즘] 분할 정복(Divide and Conquer) - 이진 검색과 병합 정렬(MergeSort) 본문

교육/강의

[학교-알고리즘] 분할 정복(Divide and Conquer) - 이진 검색과 병합 정렬(MergeSort)

학학이 2016. 4. 15. 01:31

분할 정복(Divide and Conquer)

  1. step : Divide, 문제를 하나 또는 둘 이상의 인스턴스로 나눈다.
  2. step : Conquer, 나눠진 문제가 충분히 작고 해결가능 하다면 해결하고, 그렇지 않으면 다시 나눈다.
  3. step : Combine, 필요하다면, 나눠진 문제들을 다시 하나로 합친다.


이진 검색의 분할 정복

    • step 0 : If x = S[mid], find x and quit
    • step 1  : Divide, 배열을 두개의 하위 배열로 나눈다.
      If x > S[mid], 오른쪽 배열을 선택하고 다시 찾는다.
      If x < S[mid], 왼쪽 배열을 선택하고 다시 찾는다.
    • step 2 : Conquer, x가 어느쪽 배열에 있는지 결정한다.

이전에 이진 검색의 슈도코드를 구현했다. 

이번에는 분할 정복 방식의 이진 검색을 해보겠다. 기존의 방법과 다르게 재귀적인 모양이 나타난다.


분할 정복 이진 검색 슈도코드

~~


병합 정렬의 분할 정복

    • step 1 : Divide, 배열을 두개의 하위 배열로 나눈다.
    • step 2 : Conquer, 각 배열이 충분히 작다면, 정렬한다. 그렇지 않으면 재귀로 다시 나눈다.
    • step 3 : Combine, 나눠진 단일 배열을 합병하면서 정렬한다.

병합 정렬 슈도코드

~~


Best case time complexity of Merge

    • 입력 크기 : h, m, 각 배열의 크기
    • 기본 연산 : 서브 배열 U[i] 와 V[j]의 크기 비교
=> Best(h,m) = min(h,m) h 또는 m의 선형 시간, 즉 작은 배열이 기준이 되어서 비교하는 경우 가장 시간 복잡도가 좋다. 하나가 먼저 끝나는 경우


Worst case time complexity of Merge

모든 i, j 마다 비교하는 경우 

ex )  U | 5, 7, ...., 100 |

V | 10, 12, .... 103 |        이런 경우 U의 100 때문에 계속 비교를 하게 된다.

=> Worst(h,m) = h+m-1  // 맨 마지막은 비교하지 않아서 -1


Worst case time complexity of MergeSort

계산해야 함. 복잡함. 

 이렇게 나온다


Comments