 Divide and Conquer (분할정복) 알고리즘(Algorithm)  Divide and Conquer (분할정복) 2019년 봄학기 강원대학교 컴퓨터과학전공 문양세

Divide-and-Conquer? 유래: 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략 오스트리아-러시아 연합군 > 프랑스군 (15,000명 이상 많음)  전체적인 전력은 연합군이 프랑스군에 비해 우수함 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔  Divide 둘로 나뉜 연합군을 한 부분씩 정복(격파)함  Conquer

Divide-and-Conquer 설계 전략 통합(Combine): (필요하다면) 해결된 해답을 모은다.  이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다.

행렬곱셈 (Matrix Multiplication) 강의 순서 Divide and Conquer 이진검색 (Binary Search) 합병정렬 (Merge Sort) The Master Theorem 빠른정렬 (Quick Sort) 행렬곱셈 (Matrix Multiplication)

이진 검색: 재귀 알고리즘 (1/3) 문제: 크기가 n인 정렬된 배열 S에 x가 있는지를 결정하라. Divide and Conquer 문제: 크기가 n인 정렬된 배열 S에 x가 있는지를 결정하라. 입력: 자연수 n, 정렬된 배열 S[1..n], 찾고자 하는 항목 x 출력: locationout - x가 S의 어디에 있는지의 위치, 만약 x가 S에 없다면 0 설계전략: x가 배열의 중간에 위치한 항목과 같으면, “빙고, 찾았다!” 그렇지 않으면: 분할: 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택하고, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택한다. 정복: 선택된 반쪽 배열에서 x를 찾는다. 통합: (필요 없음)

이진 검색: 재귀 알고리즘 (2/3) index location (index low, index high) { Divide and Conquer index location (index low, index high) { index mid; if (low > high) return 0; // 찾지 못했음 else { mid = (low + high) / 2 // 정수 나눗셈 (나머지 버림) if (x == S[mid]) return mid; // 찾았음 else if (x < S[mid]) return location(low, mid-1); // 왼쪽 반 선택 else return location(mid+1, high);// 오른쪽 반 선택 } … locationout = location(1, n); ...

이진 검색: 재귀 알고리즘 (3/3) Divide and Conquer

이진 검색: 알고리즘 고찰 (1/2) 알고리즘에서 함수의 파라미터와 지역변수는 무엇인가? Divide and Conquer 알고리즘에서 함수의 파라미터와 지역변수는 무엇인가? 입력 파라미터 n, S, x는 전역변수인가, 지역변수인가? 입력 파라미터 n, S, x는 알고리즘 수행 중 변하지 않는 값이다. 따라서 함수를 재귀호출(recursive call)할 때 마다 이러한 변하지 않는 파라미터를 가지고 다니는 것은 극심한 낭비이다.  왜?

이진 검색: 알고리즘 고찰 (2/2) Divide and Conquer 꼬리 재귀호출(tail recursion): 재귀 알고리즘에서 모든 재귀호출이 알고리즘의 마지막(꼬리) 부분에서 이루어지는 경우 꼬리 재귀호출 알고리즘은 반복 알고리즘(iterative algorithm)으로 변환하기가 수월하다. ( 강의노트 03 참조) 재귀 알고리즘 vs. 반복 알고리즘 재귀 알고리즘은 재귀 호출할 때마다 그 당시의 상태를 활성 레코드(activation records) 스택에 저장해 놓아야 한다. 반면에, 반복 알고리즘은 그럴 필요가 없기 때문에 일반적으로 더 효율적이다(빠르다). 그렇다고 반복 알고리즘의 계산복잡도가 재귀 알고리즘보다 좋다는 의미는 아니다. 반복 알고리즘이 상수적(constant factor)으로만 빠르다는 말이다. 일부 언어는 컴파일러가 자동으로 재귀 프로그램을 반복 프로그램으로 바꾸어 준다.

이진 검색: 최악의 경우 시간 복잡도 (1/7) 단위연산: x와 S[mid]의 비교 Divide and Conquer 단위연산: x와 S[mid]의 비교 입력 크기: 배열의 크기 n (= high - low + 1) 단위 연산으로 설정한 조건문을 함수 호출마다 각각 두 번(==, <) 수행하나, 사실상 비교는 한번 이루어진다고 봐도 된다. 그 이유는: (1) 어셈블리 언어로는 하나의 조건 명령으로 충분히 구현할 수 있기 때문이기도 하고; (2) x를 찾기 전까지는 항상 두 개의 조건 문을 수행하므로 하나로 묶어서 한 단위로 취급을 해도 되기 때문이기도 하다. 이와 같이 단위연산은 최대한 효율적으로(빠르게) 구현된다고 일반적으로 가정하여, 하나의 단위로 취급해도 된다.

이진 검색: 최악의 경우 시간 복잡도 (2/7) 경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 ½인 경우 Divide and Conquer 경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 ½인 경우 시간 복잡도를 나타내 주는 점화식(recurrence)은 다음과 같다. n > 1 이고, n = 2k(k  1) 이 식의 해는 왼편의 과정으로 구할 수 있다.

이진 검색: 최악의 경우 시간 복잡도 (3/7) 앞서 분석한 시간 복잡도가 바른지 확인해 보자. 증명: 수학적 귀납법: Divide and Conquer 앞서 분석한 시간 복잡도가 바른지 확인해 보자. 증명: 수학적 귀납법: Induction basis: n = 1이면, W(1) = 1 = lg 1 + 1. Induction hypothesis: 2의 거듭제곱(power)인 양의 정수 n에 대해서, W(n) = lg n + 1라고 가정한다. Induction step: W(2n) = lg(2n) + 1임을 보이면 된다. 점화식(재현식)을 사용하면,

이진 검색: 최악의 경우 시간 복잡도 (4/7) 경우 2: 일반적인 경우 – 반쪽 배열의 크기는 이 됨 Divide and Conquer 경우 2: 일반적인 경우 – 반쪽 배열의 크기는 이 됨 n에 대해서 가운데 첨자는 이 되는데, 이 때 각 부분배열의 크기는 다음과 같다. 위의 표에 의하면 알고리즘이 다음 단계에 찾아야 할 항목의 개수는 기껏해야 개가 된다. 따라서 다음과 같은 점화식으로 표현할 수 있다. N 왼쪽 부분배열의 크기 mid 오른쪽 부분배열의 크기 짝수 n/2 - 1 1 n/2 홀수 (n-1)/2

이진 검색: 최악의 경우 시간 복잡도 (5/7) 앞서 제시된 점화식의 해가 이 됨을 증명한다. 증명 방법: 수학적 귀납법 Divide and Conquer 앞서 제시된 점화식의 해가 이 됨을 증명한다. 증명 방법: 수학적 귀납법 Induction basis: n = 1이면, 다음이 성립한다. Induction hypothesis: n > 1이고, 1 < k < n인 모든 k에 대해서, 가 성립한다고 가정한다.

이진 검색: 최악의 경우 시간 복잡도 (6/7) Induction step: 1) n이 짝수이면 (즉, ), 다음이 성립한다. Divide and Conquer Induction step: 1) n이 짝수이면 (즉, ), 다음이 성립한다.

이진 검색: 최악의 경우 시간 복잡도 (7/7) 따라서, 모든 n에 대해서 이 성립한다. Divide and Conquer Induction step: 2) n이 홀수이면 (즉, ), 다음이 성립한다. 따라서, 모든 n에 대해서 이 성립한다.

행렬곱셈 (Matrix Multiplication) 강의 순서 Divide and Conquer 이진검색 (Binary Search) 합병정렬 (Merge Sort) The Master Theorem 빠른정렬 (Quick Sort) 행렬곱셈 (Matrix Multiplication)

합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오. Divide and Conquer 문제: n개의 정수를 (비내림차순으로) 정렬하시오. 입력: 정수 n, 크기가 n인 배열 S[1..n] 출력: (비내림차순으로) 정렬된 배열 S[1..n] 보기: 27, 10, 12, 20, 25, 13, 15, 22  다음 페이지 참조

합병정렬 (2/2) Divide and Conquer

합병정렬: 알고리즘 void mergesort (int n, keytype S[]) { Divide and Conquer 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); } mergesort2

합병정렬: 합병 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오. Divide and Conquer 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오. 입력: (1) 양의 정수 h, m, (2) 정렬된 배열 U[1..h], V[1..m] 출력: U와 V에 있는 키들을 하나의 배열에 정렬한 S[1..h+m]

합병정렬: 합병 알고리즘 (1/2) Divide and Conquer void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]) { index i, j, k; i = 1; j = 1; k = 1; while (i <= h && j <= m) { if (U[i] < V[j]) { S[k] = U[i]; i++; } else { S[k] = V[j]; j++; } k++; if(i > h) copy V[j] through V[m] to S[k] through S[h+m]; else copy U[i] through U[h] to S[k] through S[h+m]; 버블과 합병정렬 비교

합병정렬: 합병 알고리즘 (2/2) 최악의 경우 시간 복잡도 분석 단위연산: U[i]와 V[j]의 비교 Divide and Conquer 최악의 경우 시간 복잡도 분석 단위연산: 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.

합병정렬: 최악의 경우 시간 복잡도 (1/2) 단위연산: 합병 알고리즘 merge에서 발생하는 비교 Divide and Conquer 단위연산: 합병 알고리즘 merge에서 발생하는 비교 입력크기: 배열 S에 들어 있는 항목의 개수 n 분석: 최악의 경우 수행시간은 W(h+m) = W(h) + W(m) + h + m - 1이 된다. 여기서 W(h)는 U를 정렬하는데 걸리는 시간, W(m)은 V를 정렬하는데 걸리는 시간, 그리고 h + m - 1은 합병하는데 걸리는 시간이다. 정수 n을 2k(k  1)이라고 가정하면, h = m = n/2 이 된다. 따라서 최악의 경우 점화식은 다음와 같다. 이 점화식의 해는 다음에 소개할 Master Theorem을 적용하면, 다음과 같다.

합병정렬: 최악의 경우 시간 복잡도 (2/2) n이 2의 거듭제곱(power)의 형태가 아닌 경우의 점화식은 다음과 같다. Divide and Conquer n이 2의 거듭제곱(power)의 형태가 아닌 경우의 점화식은 다음과 같다. 그러나, 이 점화식의 정확한 해를 구하기는 복잡하다. 그런데, 앞의 이진검색 알고리즘의 분석에서도 보았듯이, n = 2k라고 가정해서 해를 구하면, 이 점화식의 해와 같은 카테고리의 시간복잡도를 얻게 된다. 따라서 앞으로 이와 비슷한 점화식의 해를 구할 때, n = 2k라고 가정해서 구해도 점근적으로는 같은 해를 얻게 된다.

합병정렬: 공간 복잡도 (1/4) Divide and Conquer 입력을 저장하는데 필요한 저장장소 이외에 추가적인 저장장소를 사용하지 않고 정렬하는 알고리즘을 제자리정렬(in-place sort) 알고리즘이라고 한다. 앞서의 합병정렬 알고리즘은 제자리정렬 알고리즘이 아니다. 왜냐하면 입력인 배열 S이외에 두 개의 배열 U와 V를 추가로 만들어서 사용하기 때문이다.

합병정렬: 공간 복잡도 (2/4) 그러면 합병정렬은 얼마만큼의 추가적인 저장장소가 필요할까? Divide and Conquer 그러면 합병정렬은 얼마만큼의 추가적인 저장장소가 필요할까? 함수 mergesort를 호출할 때마다 크기가 S의 반이 되는 U와 V가 추가적으로 필요하다. 함수 merge에서는 U와 V가 주소로 전달이 되어 그냥 사용되므로 추가적인 저장장소를 만들지 않는다. 따라서, mergesort를 재귀호출할 때마다 얼마만큼의 추가적인 저장장소가 만들어져야 하는지를 계산해 보면 된다. 처음 S의 크기가 n이면, 추가적으로 필요한 U와 V의 저장장소 크기의 합은 n이 된다. 다음 재귀 호출에는 n/2, 그 다음에는 n/4 등으로 추가적인 저장장소가 필요하다. 이들 저장장소의 크기를 합하면, 이 된다. (다음 페이지 참조) 결론적으로 합병정렬 알고리즘의 공간복잡도는 이라 할 수 있다.

합병정렬: 공간 복잡도 (3/4) Divide and Conquer

합병정렬: 공간 복잡도 (4/4) Divide and Conquer 추가적으로 필요한 저장장소가 n이 되도록, 즉, 공간복잡도가 n이 되도록 알고리즘을 향상시킬 수 있다(다음 절의 알고리즘). 그러나, 합병정렬 알고리즘이 (공간 복잡도가 O(1))인 제자리정렬 알고리즘이 될 수는 없다.

합병정렬: 공간 복잡도 향상 알고리즘 (1/3) 문제: n개의 정수를 (비내림차순으로) 정렬하시오. Divide and Conquer 문제: n개의 정수를 (비내림차순으로) 정렬하시오. 입력: 정수 n, 크기가 n인 배열 S[1..n] 출력: (비내림차순으로) 정렬된 배열 S[1..n] void mergesort2 (index low, index high) { index mid; if (low < high) { mid = (low + high) / 2; mergesort2(low, mid); mergesort2(mid+1, high); merge2(low, mid, high); } ... mergesort2(1, n); mergesort

합병정렬: 공간 복잡도 향상 알고리즘 (2/3) 합병(merge2) Divide and Conquer 합병(merge2) 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오. 입력: (1) 첨자 low, mid, high, (2) 부분 배열 S[low..high] (단, S[low..mid]와 S[mid+1..high]는 이미 각각 정렬이 완료되어 있음) 출력: 정렬이 완료된 부분배열 S[low..high]

합병정렬: 공간 복잡도 향상 알고리즘 (3/3) Divide and Conquer void merge2(index low, index mid, index high) { index i, j, k; keytype U[low..high]; // 합병하는데 필요한 지역 배열 i = low; j = mid + 1; k = low; while (i <= mid && j <= high) { if (S[i] < S[j]) { U[k] = S[i]; i++; } else { U[k] = S[j]; j++; } k++; if(i > mid) copy S[j] through S[high] to U[k] through U[high]; else copy S[i] through S[mid] to U[k] through U[high]; copy U[low] through U[high] to S[low] through S[high]; merge2() 함수는 어느 한 순간에 하나만 호출된다. 재귀 호출이 아님에 유의한다.

행렬곱셈 (Matrix Multiplication) 강의 순서 Divide and Conquer 이진검색 (Binary Search) 합병정렬 (Merge Sort) The Master Theorem 빠른정렬 (Quick Sort) 행렬곱셈 (Matrix Multiplication)

with a≥1, integer b>1, real c>0, d≥0. Then: The Master Theorem Divide and Conquer Consider a function f(n) that, for all n=bk for all kZ+, satisfies the recurrence relation: (n=bk 일 때, 다음 점화 관계가 성립하면) f(n) = af(n/b) + cnd with a≥1, integer b>1, real c>0, d≥0. Then: Proof of the theorem is …. omitted.

Master Theorem Examples (1/3) Divide and Conquer Complexity of fast multiplication was: T(n)=3T(n/2)+(n) Thus, a=3, b=2, d=1. So a > bd, so case 3 of the master theorem applies, so: which is O(n1.58…).

Master Theorem Examples (2/3) Divide and Conquer 예제: Binary Search 이진 탐색의 복잡도는 얼마인가(비교 수를 추정하라)? 이진 탐색의 점화 관계: T(n) = T(n/2)+c (n 이 짝수라 가정) 매스터 정리로 보면, a = 1, b = 2, d = 0으로서, a = 1 = bd인 두 번째 경우에 해당한다. 결국, 다음과 같은 과정에 의해 O(logn)이 된다.

Master Theorem Examples (3/3) Divide and Conquer 예제: Merge Sort 합병 정렬의 복잡도는 얼마인가(비교 수를 추정하라)? 이진 탐색의 점화 관계: T(n) = 2T(n/2)+cn (n 이 짝수라 가정) 매스터 정리로 보면, a = 2, b = 2, d = 1로서, a = 2 = bd인 두 번째 경우에 해당한다. 결국, 다음과 같은 과정에 의해 O(nlogn)이 된다.

행렬곱셈 (Matrix Multiplication) 강의 순서 Divide and Conquer 이진검색 (Binary Search) 합병정렬 (Merge Sort) The Master Theorem 빠른정렬 (Quick Sort) 행렬곱셈 (Matrix Multiplication)

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

빠른정렬(Quick Sort) – 개요 (2/3) Divide and Conquer 주어진 배열을 두 개로 분할하고, 각각을 정렬한다.  합병정렬과 동일? 다른점 1: 합병정렬은 그냥 두 부분으로 나누는 반면에, 빠른정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다. 다른점 2: 각 부분 정렬이 끝난 후, 합병정렬은 “합병”이란 후처리 작업이 필요하나, 빠른정렬은 필요로 하지 않는다.

빠른정렬(Quick Sort) – 개요 (3/3) Divide and Conquer 예제: 15, 22, 13, 27, 12, 10, 20, 25

빠른정렬 – 정렬 알고리즘 문제: n개의 정수를 (비내림차순으로) 정렬 Divide and Conquer 문제: n개의 정수를 (비내림차순으로) 정렬 입력: 정수 n > 0, 크기가 n인 배열 S[1..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); }

빠른정렬 – 분할 알고리즘 (1/3) 문제: 빠른정렬을 하기 위해서 배열 S를 둘로 쪼갠다. Divide and Conquer 문제: 빠른정렬을 하기 위해서 배열 S를 둘로 쪼갠다. 입력: (1) 첨자 low, high (2) 첨자 low에서 high까지의 S의 부분배열 출력: (1) S의 부분배열을 분할한 기준점 pivotpoint (2) 기준점에 의해 분할된 S의 부분배열 (좌우로 이동된 부분배열) 알고리즘: (the next page)

빠른정렬 – 분할 알고리즘 (2/3) Divide and Conquer 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 증가하고 교환 j++; exchange S[i] and S[j]; } pivotpoint = j; exchange S[low] and S[pivotpoint]; // pivotitem 값을 pivotpoint에 넣는다

if(S[i] > pivotitem) if(S[i] < pivotitem) 빠른정렬 – 분할 알고리즘 (3/3) Divide and Conquer low j i high < pivotitem > pivotitem to be investigated if(S[i] > pivotitem) low j i high < pivotitem > pivotitem to be investigated if(S[i] < pivotitem) low j i high < pivotitem > pivotitem to be investigated

빠른정렬 – 분할 알고리즘 예제 i j S[1] S[2] S[3] S[4] S[5] S[6] S[7] S[8] 비고 - 2 3 Divide and Conquer i j S[1] S[2] S[3] S[4] S[5] S[6] S[7] S[8] 비고 - 2 3 4 5 6 7 8 1 12 23 34 15 22 13 27 12 10 20 25 15 13 22 27 12 10 20 25 15 13 12 27 22 10 20 25 15 13 12 10 22 27 20 25 10 13 12 15 22 27 20 25 초기값 최종값

빠른정렬 – 알고리즘 분석 (Worst Case) (1/5) Divide and Conquer 분할 알고리즘의 모든 경우를 고려한 시간복잡도 분석 단위연산: S[i]와 key와의 비교 입력크기: 부분배열이 가지고 있는 항목의 수, n = high - low + 1 분석: 배열의 첫번째 항목만 제외하고 모든 항목을 한번씩 비교하므로, T(n) = n – 1이다.  n개 항목에 대한 분할에서는 기본적으로 n – 1번의 비교가 이루어짐

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

빠른정렬 – 알고리즘 분석 (Worst Case) (3/5) Divide and Conquer 이 점화식을 풀면, 다음과 같다. 이미 정렬이 되어 있는 경우 알고리즘의 시간복잡도는 n(n–1)/2이 된다. 그러면, 시간이 더 많이 걸리는 경우는 없을까? 사실, 이 경우가 최악이며, 따라서 이 보다 더 많은 시간이 걸릴 수 없다는 사실을 수학적으로 엄밀하게 증명한다.

빠른정렬 – 알고리즘 분석 (Worst Case) (4/5) - skip Divide and Conquer 모든 정수 n에 대해서, 임을 증명하시오. 증명: (수학적귀납법) 귀납출발점: n = 0일 때, 귀납가정: 0  k < n인 모든 k에 대해서, 귀납단계:

빠른정렬 – 알고리즘 분석 (Worst Case) (5/5) – skip Divide and Conquer 여기서 p가 n - 1일 때 최대값을 가진다. 따라서 가 되고, 결과적으로 가 된다. 따라서 최악의 경우 시간복잡도는 다음과 같다.

빠른정렬 – 알고리즘 분석 (Average Case) (1/4) Divide and Conquer 결국, 빠른정렬의 Worst Case Complexity는 로, 합병정렬에 비해 좋지 못하다. 그런데, 왜 “빠른”정렬이라고 했을까? 이는 다음에 계산되는 Average Case Complexity 때문이다.

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

빠른정렬 – 알고리즘 분석 (Average Case) (3/4) – skip Divide and Conquer 분석(계속): 양변을 n을 곱하면, n대신 n - 1을 대입하면, (1)에서 (2)를 빼면, 간단히 정리하면, 여기서, 라 하면, 다음과 같은 점화식을 얻을 수 있다. 그러면, 다음 관계가 성립한다.

빠른정렬 – 알고리즘 분석 (Average Case) (4/4) – skip Divide and Conquer 분석(계속): 따라서, 해는 다음과 같다. 여기에서 오른쪽 항은 무시해도 될 만큼 작으므로 무시한다. 그런데, ln n = logen이고, 이므로, 해는 an  2 ln n이다. 따라서, A(n)은 다음과 같다.

행렬곱셈 (Matrix Multiplication) 강의 순서 Divide and Conquer 이진검색 (Binary Search) 합병정렬 (Merge Sort) The Master Theorem 빠른정렬 (Quick Sort) 행렬곱셈 (Matrix Multiplication)

행렬 개요 (1/4) 행렬이 뭐였더라? Hmmm… 행렬이란 Matrix여… 이거  Divide and Conquer 행렬이 뭐였더라? Hmmm… 행렬이란 Matrix여… 이거  행렬에 대한 지식을 모두 반납한 학생들을 위해 몇 가지 기본 사항만 잠시 리뷰해 볼까요?

행렬 개요 (2/4) 행렬은 수의 사각형 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다. Divide and Conquer 행렬은 수의 사각형 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다. 행과 열의 개수가 같은 nxn 행렬을 정방행렬이라 한다. 두 행렬이 같은 수의 행과 열을 가지며 각 위치의 해당 원소의 값이 같으면 “두 행렬은 같다”고 정의한다.

행렬 개요 (3/4) Divide and Conquer 행렬의 합: A+B = C = [ci,j] = [ai,j+bi,j] where A = [ai,j] and B = [bi,j]

행렬 개요 (4/4) Divide and Conquer 행렬의 곱:

행렬곱셈 – 단순 알고리즘 (1/3) 문제: n  n 크기의 행렬의 곱을 구하시오. Divide and Conquer 문제: n  n 크기의 행렬의 곱을 구하시오. 입력: 양수 n, n  n 크기의 행렬 A와 B 출력: 행렬 A와 B의 곱인 C 알고리즘: void matrixmult (int n, const number A[][], const number B[][], number C[][]) { index i, j, k; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { C[i][j] = 0; for (k = 1; k <= n; k++) C[i][j] = C[i][j] + A[i][k] * B[k][j]; }

행렬곱셈 – 단순 알고리즘 (2/3) 곱셈 연산의 시간복잡도 분석 단위연산: 가장 안쪽의 루프에 있는 곱셈하는 연산 Divide and Conquer 곱셈 연산의 시간복잡도 분석 단위연산: 가장 안쪽의 루프에 있는 곱셈하는 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 총 곱셈의 횟수는 다음과 같다.

행렬곱셈 – 단순 알고리즘 (3/3) 덧셈(뺄셈) 연산의 시간복잡도 분석 Divide and Conquer 덧셈(뺄셈) 연산의 시간복잡도 분석 단위연산: 가장 안쪽의 루프에 있는 덧셈(뺄셈)하는 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 총 덧셈의 횟수는 다음과 같다. k=1일 때는 덧셈이 필요 없기 때문

행렬곱셈 – 재귀 알고리즘 (1/3) 두 2  2 행렬 A와 B의 곱(product) C: Divide and Conquer 두 2  2 행렬 A와 B의 곱(product) C: n이 2의 거듭제곱이고, 각 행렬을 4개 부분행렬(submatrix)로 나눈다고 가정하자. 두 n  n 행렬 A와 B의 곱 C:

행렬곱셈 – 재귀 알고리즘 (2/3) 문제: n이 2의 거듭제곱일 때, n  n 크기의 행렬의 곱을 구하시오. 알고리즘: Divide and Conquer 문제: n이 2의 거듭제곱일 때, n  n 크기의 행렬의 곱을 구하시오. 알고리즘: matrix recurmat(int n, matrix A, matrix B) { if (n == 1) return (c11 = a11 * b11); else { A를 4개의 부분행렬 A11, A12, A21, A22로 분할; B를 4개의 부분행렬 B11, B12, B21, B22로 분할; C11 = recurmat(n/2, A11, B11) + recurmat(n/2, A12, B21); C12 = recurmat(n/2, A11, B12) + recurmat(n/2, A12, B22); C21 = recurmat(n/2, A21, B11) + recurmat(n/2, A22, B21); C22 = recurmat(n/2, A21, B12) + recurmat(n/2, A22, B22); return C; // C는 C11, C12, C21, C22로 구성된 nn 행렬 }

행렬곱셈 – 재귀 알고리즘 (3/3) 시간복잡도 분석 (곱셈) Divide and Conquer 시간복잡도 분석 (곱셈) Master Theorem에 따라 상기 점화식의 해는 다음과 같이 구할 수 있다.

쉬트라쎈 방법 – 2x2 행렬 (1/2) 문제: 두 2  2 행렬 A와 B의 곱(product) C, Divide and Conquer 문제: 두 2  2 행렬 A와 B의 곱(product) C, 쉬트라쎈(Strassen)의 해: Why? 앉아서 꼼꼼히 따져보세요.

쉬트라쎈 방법 – 2x2 행렬 (2/2) 시간복잡도 분석: 단순 곱셈 방법: 8번의 곱셈과 4번의 덧셈이 필요함 Divide and Conquer 시간복잡도 분석: 단순 곱셈 방법: 8번의 곱셈과 4번의 덧셈이 필요함 쉬트라쎈 방법: 7번의 곱셈과 18번의 덧셈/뺄셈이 필요함  언뜻 봐서는 전혀 좋아지지 않았다!  그러나 행렬의 크기가 커지면 쉬트라쎈의 방법의 가치가 드러난다.

쉬트라쎈 방법 – nxn 행렬 (1/7) Divide and Conquer 문제: n이 2의 거듭제곱이고, 각 행렬을 4개의 부분행렬(submatrix)로 나눈다고 가정하자. 두 n  n 행렬 A와 B의 곱 C: 쉬트라쎈(Strassen)의 해:

쉬트라쎈 방법 – nxn 행렬 (2/7) 문제: n이 2의 거듭제곱일 때, n  n 크기의 두 행렬의 곱을 구하시오. Divide and Conquer 문제: n이 2의 거듭제곱일 때, n  n 크기의 두 행렬의 곱을 구하시오. 입력: 정수 n, n  n 크기의 행렬 A와 B 출력: 행렬 A와 B의 곱인 C 알고리즘: void strassen (int n, nxn matrix A, nxn matrix B, nxn matrix& C) { if (n <= threshold) 단순한 알고리즘을 사용하여 C = A * B를 계산; else { A를 4개의 부분행렬 A11, A12, A21, A22로 분할; B를 4개의 부분행렬 B11, B12, B21, B22로 분할; 쉬트라쎈의 방법을 사용하여 C = A * B를 계산; // 재귀 호출의 예: strassen(n/2, A11+A12, B11+B22, M1) } Threshold? 단순 알고리즘보다 쉬트라쎈 알고리즘이 더 좋을 것이라 예상되는 지점

쉬트라쎈 방법 – nxn 행렬 (3/7) 곱셈 연산의 시간복잡도 분석 단위연산: 곱셈하는 연산 입력크기: 행과 열의 수, n Divide and Conquer 곱셈 연산의 시간복잡도 분석 단위연산: 곱셈하는 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: threshold를 1이라고 하자 (참고: threshold는 복잡도 차수에 전혀 영향을 미치지 않는다.) 점화식을 다음과 같이 구할 수 있다. Why? 하나의 nxn 곱셈이 일곱 개의 (n/2)x(n/2) 곱셈으로 바뀌었기 때문

쉬트라쎈 방법 – nxn 행렬 (4/7) 곱셈 연산의 시간복잡도 분석 (계속) 점화식을 전개하면 다음과 같다. Divide and Conquer 곱셈 연산의 시간복잡도 분석 (계속) 점화식을 전개하면 다음과 같다. 상기 결과는 귀납법에 의해서 증명이 가능하다. (Try it!) 또한, 상기 점화식은 Master Theorem 1번을 이용하면 간단히 해를 구할 수 있다. (Also, try it!)

쉬트라쎈 방법 – nxn 행렬 (5/7) 덧셈(뺄셈) 연산의 시간복잡도 분석 단위연산: 덧셈/뺄셈하는 연산 Divide and Conquer 덧셈(뺄셈) 연산의 시간복잡도 분석 단위연산: 덧셈/뺄셈하는 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 앞서와 마찬가지로 threshold를 1이라 한다. 점화식을 다음과 같이 구할 수 있다. Why? nxn 곱셈이 일곱 개의 (n/2)x(n/2) 곱셈으로 바뀌었고, 18번의 (n/2)x(n/2) 행렬 덧셈이 필요한데, 각각은 (n/2)^2 번의 덧셈을 필요로 하기 때문

덧셈(뺄셈) 연산의 시간복잡도 분석 (계속) 쉬트라쎈 방법 – nxn 행렬 (6/7) Divide and Conquer 덧셈(뺄셈) 연산의 시간복잡도 분석 (계속) 점화식은 다음과 같다. Master Theorem을 사용하면 상기 점화식의 해는 다음과 같이 구할 수 있다.

쉬트라쎈 방법 – nxn 행렬 (7/7) Strassen은 행렬 곱셈의 복잡도를 에서 으로 낮추었다. Divide and Conquer Strassen은 행렬 곱셈의 복잡도를 에서 으로 낮추었다. 이후에 곱셈의 복잡도를 까지 낮춘 알고리즘이 개발되었다. 그렇다면, 과연 얼마까지 복잡도를 낮출 수 있을까? 두 행렬을 곱하기 위한 문제에 대해서 시간복잡도가 이 되는 알고리즘을 만들어 낸 사람은 아무도 없다. 게다가 그러한 알고리즘을 만들 수 없다고 증명한 사람도 아무도 없다.

Homework#3 Divide and Conquer