자료구조 및 알고리즘 2 - contd.

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다.

 

 

 

 

1. 재귀 이진 탐색

 

앞서 반복문을 통한 이진탐색을 보았는데

아래는 재귀를 통한 이진탐색입니다.

// binary search with Recursion
int binarySearch(int a[], int n, int target)
{	
	// Base
    if(n < 1) return -1;
    
    int l, r, m;
    l = 0;
    r = n - 1;
    m = (l + r) / 2;
    
    // Step
    if(a[m] == target)
    	return m;
    else if(a[m] > target)
    	return binarySearch(a, m - 1, target);
    else
    	return m + binarySearch(a + m + 1, n - m, target);
 }

 

 

 

 

 

1.1 Induction 즉 귀납을 통해 해당 함수의 완전성을 증명

 

주장 : 만약 어떤 i 에 대해서 a[i] = target 이라면 위 함수는 i 를 return 한다.

Base : n = 0 인 경우 "어떤 i 에 대해서 a[i] = target" 이 성립할 방법이 없고, 함수는 항상 -1 을 return 한다.

Step : binarySearch(a, m, target) 이 성립한다고 했을 때, binarySearch(a, n, target) 이 성립함을 증명한다.

• case 1 : a[m] = target 인 경우, m 을 return 하니 성립
• case 2 : a[m] > target 인 경우, a[m], a[m+1], ..., a[n] 중에는 target과 같은 값이 없다. 따라서 a[i] = target 인 경우가 있다면 i 는 0, 1, ... , m-1 중 하나이다. 이때 binarySearch(a, m, target) 이 성립하니, 위 주장이 성립한다.
• case 3 : a[m] < target 인 경우,  0, 1, ... , m-1 중에는 target과 같은 값이 없다. 따라서 a[i] = target 인 경우가 있다면 i 는 a[m], a[m+1], ..., a[n] 중 하나이다. 이때 새로운 a 를 a + m + 1 로 정의한다면 i 는 0, 1, ... , m-1 중 하나이다. 이때 binarySearch(a, m, target) 이 성립하니, 위 주장이 성립한다.

 

 

 

 

 

1.2 Time Complexity

 

시간 복잡도를 계산 해보겠습니다. T(n) 은 binarySearch() 를 돌리는 데 걸리는 시간입니다.

T(n) = 1 + T(n/2) = 1 + 1 + T(n/4) = ... = O(logn)

 

log2n 은 n에서 1까지 2를 몇 번 나눠야 하는지를 보여줍니다. 즉 binarySearch에서 array의 길이는 한 번 진행할 때 마다 반으로 줄어드니 원래 길이가 n인 array에 대해 1이 될때까지 logn번 수행해야합니다. 따라서 시간 복잡도는 O(logn)입니다.

 

 

 

 

 

 

 

 

2. 선택 정렬(* Selection Sort)

 

주어진 배열에서 가장 작은 값을 가장 앞에 값과 바꿔서 정렬하는 방법입니다.

// sort with for loop
void selectionSort(int a[], int n)
{
	int i, j;
    for(i = 0; i < n - 1; i++)
    {
    	int min = i;
    	for(j = 1; j < n; j++)
        {
        	if(a[min] > a[j])
            	min = j;
        }
        swap(a[i], a[min]);
    }
}

 

 

 

 

 

 

2.1 Invariant 를 이용해 해당 함수의 완전성을 증명

 

Invariant : k번째 loop 가 끝났을 때 a[0] < a[1] < ... < a[k] 이고 a[k] < a[i], ∀i > k, i < n - 1 이다.

Base : k = 0 일 때는 그냥 참

Step : k = n 일 때 성립하면 k = n + 1 일 때 성립해야한다.

• k = n 일 때 :  a[0] < a[1] < ... < a[k] 이고 a[k] < a[i], ∀i > k, i < n - 1 이다. 여기에서 한 번의 loop가 더 돌면 생기는 변화는 다음과 같다. a[i], ∀i > k, i < n - 1 중 가장 작은 값이 a[k+1] 이 된다. 따라서 a[0] < a[1] < ... < a[k] < a[k+1] 이고 a[k+1] 은 a[i], ∀i > k, i < n - 1 중 가장 작은 값이니, a[k+1] < a[i],  ∀i > k + 1, i < n - 1즉 Invariant 가 깨지지 않는다.

 

 

 

 

 

2.2 재귀 선택 정렬

// selection sort with Recursion
void selectionSort(int a[], int n)
{
	if(n <= 1) return;
    
    int i, min;
    min = 0;
    for(i = 1; i < n; i++)
    {
    	if(a[min] > a[i])
        	min = i;
    }
    swap(a[min], a[0]);
    selectionSort(a + 1, n - 1);
}

 

 

 

 

 

 

2.3 Induction 을 통해 위 함수의 완전성을 증명

 

주장 : sorting 이 끝난 후 배열의 저장된 n 만큼의 값들은 오름차순으로 정렬되어야 합니다.

Base : n = 0 or 1 일 때, n = 0 or 1 이면 정렬할 요소가 없으므로 그냥 return 합니다.

Step : n = k 일 때 해당 주장이 성립한다고 가정했을 때, n = k+1 일 때 성립하는지 확인합니다.

즉 selectionSort(a, k) 가 성공하면 selectionSort(a, k+1) 이 성공하는지 보면 됩니다. 

 

n = k 일 때 위 함수가 성공한 결과가 a[1] < a[2] < ... < a[k] 라고 할때

selectionSort(a, k+1) 의 함수 내에서 동작한 결과는 a[0] < a[i], ∀i > 1, i < k+1 입니다.

따라서 a[0] < a[1] < ... < a[k] 로 배열에 저장된 값은 오름차순으로 정렬 됩니다.

 

 

 

 

 

2.4 Time Complexity

 

시간 복잡도를 계산 해보겠습니다. T(n) 은 selectionSort() 를 돌리는 데 걸리는 시간입니다.

T(n) = n + T(n-1) = n + (n-1) + T(n-2) = ... = n^2 ... = O(n^2)

상당히 오래 걸립니다.

 

 

 

 

 

 

 

3. Merge Algoritm and sort

 

merge 알고리즘은 정렬된 두 배열을 하나의 정렬된 배열로 합치는 알고리즘입니다.

 

void merge(int a[], int b[], int n, int m)
{
	/*
    @param n is length of array a
    @param m is length of array b
    @param result is array we are going to make
    @param i is index of result
    */
    
    int* result = new int[n+m];
    int i = 0;
	
    int l, r;
    l = 0;
    r = 0;
    
    while(l <= n && r <= m)
    {
    	if(a[l] < b[m])
        {
        	result[i] = a[l];
            l++;
            i++;
        }
        else
        {
        	result[i] = b[r];
            r++;
            i++;
        }
    }
    
    while(l <= n)
    {
    	result[i] = a[l];
        l++;
        i++;
    }
    
    while(r <= m)
    {
    	result[i] = b[r];
        r++;
        i++;
    }
}

 

위 함수, merge 알고리즘을 이용하여 배열을 정렬하면 mergeSort 입니다.

 

// mergeSort with Recursive
void mergeSort(int a[], int n)
{
	if(n <= 1) return;
    
    int b[n];
    for(int i=0; i<n; i++)
    	b[i] = a[i]
        
    mergeSort(b, n/2);
    mergeSort(b + n/2, n - n/2);
    
    merge(b, b + n/2, n/2, n - n/2);
    return;
}

void merge(int a[], int b[], int n, int m)
{
	/*
    @param n is length of array a
    @param m is length of array b
    @param result is array we are going to make
    @param i is index of result
    */
    
    int* result = new int[n+m];
    int i = 0;
	
    int l, r;
    l = 0;
    r = 0;
    
    while(l <= n && r <= m)
    {
    	if(a[l] < b[m])
        {
        	result[i] = a[l];
            l++;
            i++;
        }
        else
        {
        	result[i] = b[r];
            r++;
            i++;
        }
    }
    
    while(l <= n)
    {
    	result[i] = a[l];
        l++;
        i++;
    }
    
    while(r <= m)
    {
    	result[i] = b[r];
        r++;
        i++;
    }
}

 

그림으로 나타내면 다음과 같습니다.

 

 

 

 

 

 

 

 

3.1 mergeSort의 완전성을 증명

 

주장 : sorting 이 끝나면 해당 배열은 오름차순으로 정렬되어야 합니다.

Base : n = 1 할 일 이 없어서 return 합니다.

Step : n / 2 일 때 sort 가 성공한다면 a[0] < a[1] < ... < a[n/2 - 1] 이고 a[n/2] < a[n/2+1] < ... < a[n-1] 이다. 이때 merge 가 두 배열에 대해 성공한다면 n 일 때 a[0] < a[1] < ... < a[n/2 - 1] < a[n/2 + 1] < ... < a[n-1] 이 된다.

 

3.1.1 merge 에 대한 완전성을 증명

 

주장 : a[0] < a[1] < ... < a[n] 인 배열과 a[n+1] < b[n+2] < ... < b[2n-1] 인 배열이 있을 때 k 번째 loop 가 끝나면

a[0] < a[1] < ... < a[k-1] 이다. 그리고 k 가 2n 까지 될때까지 해당 주장이 깨지지 않으면 완전성이 입증된다.

Base : n = 0 할 게 없으니 그냥 return 해 준다.

Step : k 번 째 loop를 성공적으로 돌았을 때, a[0] < a[1] < ... < a[k-1] 이다. 여기서 한 번 더 loop를 돌면 남아있는 a배열 요소들 중 가장 작은 값과 b배열 요소들중 가장 작은 값을 비교해서 더 작을 값을 a[k]로 넣는다. 하지만 이때 a[0], a[1] 과 같이 이전에 미리 뽑힌 요소들은 a와 b가 오름차순으로 정렬되어 있었기 때문에 a[k]보다는 작다. 그래서 a[0] < a[1] < ... < a[k-1] < a[k] 가 성립한다.

 

 

 

 

 

 

3.2 Time Complexity

 

시간 복잡도를 계산 해보겠습니다. T(n) 은 mergeSort() 를 돌리는 데 걸리는 시간입니다.

T(n) = T(n/2) + T(n/2) + n = T(n/4) + T(n/4) + n/2 + T(n/4) + T(n/4) + n/2 + n = 4 * T(n/4) + n + n = ... = O(nlogn)

 

아니면 (수행의 깊이) * (한 번 수행에 걸리는 시간) 으로 구할 수도 있습니다.

이는 아래와 같습니다.