알고리즘 강의 슬라이드 2 분할정복 강의 슬라이드 #2

Presentation on theme: "알고리즘 강의 슬라이드 2 분할정복 강의 슬라이드 #2"— Presentation transcript:

1 알고리즘 강의 슬라이드 2 분할정복 강의 슬라이드 #2
분할정복 II 강의 슬라이드 #2 도경구역, 알고리즘, 사이텍미디어, 1999

2 분할정복(Divide-and-Conquer)식 설계 전략
통합(Combine): (필요하다면) 해결된 해답을 모은다. 이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다. 알고리즘 강의 슬라이드 2

3 빠른정렬(Quicksort) 1962년에 영국의 호아(C.A.R. Hoare)의 의해서 고안
빠른정렬(Quicksort)란 이름이 오해의 여지가 있음. 왜냐하면 사실 절대적으로 가장 빠른 정렬 알고리즘이라고 할 수는 없기 때문이다. 차라리 “분할교환정렬(partition exchange sort)”라고 부르는 게 더 정확함. 보기: 알고리즘 강의 슬라이드 2

4 빠른정렬 알고리즘 문제: n개의 정수를 비내림차순으로 정렬 입력: 정수 n > 0, 크기가 n인 배열 S[1..n]
알고리즘: void quicksort (index low, index high) { index pivotpoint; if (high > low) { partition(low,high,pivotpoint); quicksort(low,pivotpoint-1); quicksort(pivotpoint+1,high); } 알고리즘 강의 슬라이드 2

5 분할 알고리즘 문제: 빠른정렬을 하기 위해서 배열 S를 둘로 쪼갠다.
알고리즘 강의 슬라이드 2 분할정복 분할 알고리즘 문제: 빠른정렬을 하기 위해서 배열 S를 둘로 쪼갠다. 입력: (1) 첨자 low,high, (2) 첨자 low에서 high까지의 S의 부분배열 출력: 첨자 low에서 high까지의 S의 부분배열의 기준점(pivot point), pivotpoint 알고리즘: void partition (index low, index high, index& pivotpoint) { index i, j; keytype pivotitem; pivotitem = S[low]; //pivotitem을 위한 첫번째 항목을 고른다 j = low; for (i = low + 1; i <= high; i++) if (S[i] < pivotitem) { j++; exchange S[i] and S[j]; } pivotpoint = j; exchange S[low] and S[pivotpoint]; // pivotitem 값을 pivotpoint에 넣는다 알고리즘 강의 슬라이드 2 도경구역, 알고리즘, 사이텍미디어, 1999

6 알고리즘 강의 슬라이드 2

7 분석 분할 알고리즘의 모든 경우를 고려한 시간복잡도 분석 단위연산: S[i]와 key와의 비교
입력크기: 부분배열이 가지고 있는 항목의 수, n = high - low + 1 분석: 배열의 첫번째 항목만 제외하고 모든 항목을 한번씩 비교하므로, T(n) = n - 1이다. 알고리즘 강의 슬라이드 2

8 분석 빠른정렬 알고리즘의 최악의 경우를 고려한 시간복잡도 분석 단위연산: 분할알고리즘의 S[i]와 key와의 비교
입력크기: 배열이 S가 가지고 있는 항목의 수, n 분석: 이미 비내림차순으로 정렬이 되어 있는 배열을 정렬하려는 경우가 최악의 경우가 된다. 왜 그럴까? 비내림차순으로 정렬되어 있으면 첫번째(기준점) 항목보다 작은 항목은 없으므로, 크기가 n인 배열은 크기가 0인 부분배열은 왼쪽에 오고, 크기가 n-1인 부분배열은 오른쪽에 오도록 하여 계속 쪼개진다. 따라서, 그런데, T(0) = 0이므로, 재현식은 다음과 같이 된다. T(n) = T(n - 1) + n - 1, n > 0이면 T(0) = 0 알고리즘 강의 슬라이드 2

9 분석 이 재현식을 풀면, T(n) = T(n - 1) + n - 1 T(n - 1) = T(n - 1) + n - 2
... T(2) = T(1) + 1 T(1) = T(0) + 0 T(0) = 0 가 되므로, 이미 정렬이 되어 있는 경우 빠른정렬 알고리즘의 시간복잡도 는 이 된다는 사실을 알았다. 그러면 시간이 더 많이 걸리는 경우는 있을까? 이 경우가 최악이 경우이며, 따라서 이 보다 더 많은 시간이 걸릴 수가 없다는 사실을 수학적으로 엄밀하게 증명해 보자. 알고리즘 강의 슬라이드 2

10 귀납가정: 0  k < n인 모든 k에 대해서, 귀납단계: pivotpoint 값이 p인 경우 재현식에 의해서
증명: (수학적귀납법) 귀납출발점: n = 0일 때, 귀납가정: 0  k < n인 모든 k에 대해서, 귀납단계: pivotpoint 값이 p인 경우 재현식에 의해서 여기서 p = n 또는 p = 1일 때 최대값을 가진다. 가 된다. 따라서 최악의 경우 시간복잡도는 귀납가정에 의해서 알고리즘 강의 슬라이드 2

11 분석 빠른정렬 알고리즘의 평균의 경우를 고려한 시간복잡도 분석 단위연산: 분할알고리즘의 S[i]와 key와의 비교
입력크기: 배열이 S가 가지고 있는 항목의 수, n 분석: 배열 안에 있는 항목이 어떤 특정 순으로 정렬이 되어 있는 경우는 사실 별로 없다. 그러므로 분할 알고리즘이 주는 기준점 값은 1부터 n사이의 어떤 값도 될 수가 있고, 그 확률은 모두 같다고 봐도 된다. 따라서, 평균의 경우를 고려한 시간복잡도 분석을 해도 된다. 기준점이 p가 될 확률은 이고, 기준점이 p일 때 두 부분배열을 정렬하는데 걸리는 평균기간은 [A(p - 1) + A(n - p)]이고, 분할하는데 걸리는 시간은 n - 1이므로, 평균적인 시간복잡도는 다음과 같이 된다. 알고리즘 강의 슬라이드 2

12 양변을 n으로 곱하면, n대신 n - 1을 대입하면, (1)에서 (2)를 빼면, 간단히 정리하면, 여기서,
라고 하면, 다음과 같은 재현식을 얻을 수가 있다. 그러면, ... 알고리즘 강의 슬라이드 2

13 여기에서 오른쪽 항은 무시해도 될 만큼 작으므로 무시한다. ln n = logen이고,
따라서, 해는 여기에서 오른쪽 항은 무시해도 될 만큼 작으므로 무시한다. ln n = logen이고, 이므로, 해는 an  2 ln n. 따라서, 알고리즘 강의 슬라이드 2

14 분할정복을 사용하지 말아야 하는 경우 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우  시간복잡도: 지수(exponential) 시간 크기가 n인 입력이 거의 n개의 조각으로 분할되며, 분할된 부분의 크기가 n/c인 경우. 여기서 c는 상수이다.  시간복잡도: (nlg n) 알고리즘 강의 슬라이드 2