05. merge sort, quick sort 증명과 시간복잡도

5. Merge Sort, Quick Sort 증명과 시간복잡도

2024년 1월 9일 화요일

오후 11:03

<Merge Sort 증명>

int sort(int a[], int n)

{

int h;

int b[n];

if(n==1) return;

 

h = n / 2;

copy a[] to b[]

sort(b, h);

sort(b+h, n-h);

 

b의 두 부분을 a에 Merge

return;

}

 

(두 정렬된 배열을 Merge한 배열은, 정렬의 성공 조건 1, 2를 만족한다고 전제한다)

조건 1 증명 : a의 원소가 b로 그대로 복사되므로, 쪼개진 두 b 윈소 집합의 합집합은 a의 원소 집합과 같다. Merge과정에서 두 b원소 집합의 합집합을 a에 복사하므로, 집합 조건은 깨지지 않는다.

조건 2 증명 : 정렬이 끝난 뒤, a[0]<a[1]<...<a[n-1]이 성립하는가? -> 수학적 귀납법으로 증명

• Base : n=1일 때, 할 일이 없다.
• Step : sort(a, 1), sort(a, 2), ..., sort(a, n-1) 이 정렬에 성공한다고 가정한다.

sort(a, n)에서, h<=n-1, n-h<=n-1 이므로, sort(b, h)와 sort(b+h, n-h)는 정렬에 성공한다.

->즉, 재귀 호출이 끝난 후 b[0]<b[1]<...<b[h-1],  b[h]<b[h+1]<...<b[n-1]

Merge과정이 성공적으로 진행되므로, 함수가 끝날 때 a[0]<a[1]<...<a[n-1] 이 성립한다.

 

 

<Merge Sort의 시간복잡도 계산>

분석을 단순화하기 위해 n이 2의 거듭제곱이라 가정하고, 분할 단계에서 크기가 정확히 절반으로 나누어지는 상황을 분석해 보자.

Merge과정의 시간복잡도는 Θ(n)임이 알려져 있다. 이를 통해, 다음 점화식을 얻을 수 있다.

T(n) =   Θ(1)                  , n=1

2T(n/2) + Θ(n)     , n>1

 

따라서

T(n) = n + 2T(n/2) = n + 2(n/2 + 2T(n/4)) = n + 2(n/2 + 2(n/4 + 2T(n/8)) = ...

    = nlogn + 2^lognT(1) = nlogn+n = O(nlogn)

 

 

<Quick Sort의 증명>

int qsort(int a[], int n)

{

int d;

int p = a[0];

a[]가 다음과 같이 되도록 재배열

// a[d] == p

// a[0], a[1], ..., a[d-1] < p

// a[d+1], a[d+2], ... a[n-1] >p

qsort(a, d);

qsort(a+d+1, n-d-1);

return;

}

 

재배열 과정이 집합 조건에 위배되지 않는다고 전제한다.

 

qsort(a, n)이 끝났을 때, a[0]<a[1]<...<a[n-1]이 성립하는가?

Base : n=0 or n=1일 때, 할 일이 없다.

Step : 원소의 개수가 1, 2, ..., n-1개일때 위 조건이 성립한다고 가정한다. 즉, 재귀 호출이 끝난 뒤 (1) a[0]<a[1]<...<a[d-1], a[d+1]<a[d+2]<...<a[n-1]이 성립한다.

그런데 재배열이 성공적으로 이루어졌다면

(2) a[0], a[1], ... a[d-1] < a[d] < a[d+1], a[d+2], ...,a[n-1]이 성립한다.

재배열 과정이 집합 조건에 위배되지 않는다고 가정했으므로, 재귀 호출 이후에도 부등식(2)가 성립한다. 이를 부등식 (1)과 연립하면

a[0]<a[1]<...<a[d-1]<a[d]<a[d+1]<...<a[n-1] 이 성립한다.