[알고리즘] 1. 수학적 귀납법과 재귀

1. 수학적 귀납법

$P(1)$ 이 참이고, $P(n-1) \xrightarrow{} P(n)$ 이 참이면 $P(n)$ 은 모든 자연수 $n$ 에 대해서 참이다.

$P(n-1)$ 이 참이라고 가정하는 이유: $P(n-1)$ 이 거짓이면 $P(n-1) \xrightarrow{} P(n)$ 전체가 Vacuously True 이므로 할 말이 없다.

 

2. Recursive Sum Function

int sum(int x) {
    if (x <= 0) return 0;
    return x + sum(x-1); // Recursion
}

재귀로 직접 들어가지 않고, 수학적 귀납법을 이용하여 위 코드의 정확성을 증명할 수 있다. 여기서 중요한 것은, 재귀 함수가 정답을 리턴한다고 믿는 것이다: $sum(x)$ returns $1+2+...+x$ 

• $x$가 1일 때: 1을 리턴하므로 $P(1)$이 참이다.
• $x-1$ 일 때: $P(x-1)$ 이 참이라고 가정하자. 즉, $sum(x-1)$ 은 $1+2+...+(x-1)$ 을 리턴한다. (by 재귀 성공)
• $x$ 일 때: $sum(x)$는 $x + sum(x-1)$의 값을 리턴한다. 이 때 $sum(x-1) = 1+2+...+(x-1)$ 이라고 가정했으므로 $sum(x)$는 $sum(x) = 1+2+...+x$ 를 리턴한다.
• 따라서, $sum(x)$는 $1+2+...+x$를 리턴함을 증명했다.

시간 복잡도: $T(n) = 1 + T(n-1) = ... = n = O(n)$

 

3. Recursive Binary Search

int search(int a[], int n, int x) {
    int m;
    if (n == 0) return -1;
    m = n / 2;
    if (a[m] == x) return m;
    else if (a[m] > x) return search(a, m-1, x);
    else {
        int r = search(a+m+1, n-m-1, x);
        if (r == -1) return -1;
        else return r + m + 1;
    }
}

For some i, if $a[i] = x$, search() returns i.

• $n = 0$ 인 경우: 어떤 $i$에 대하여 $a[i] = x$가 성립할 방법이 없으므로, 함수는 항상 -1을 리턴한다.
• $a[m] = x$ 인 경우: m을 리턴하므로 주장이 성립한다.
• $a[m] > x$ 인 경우: $a[m], a[m+1], ..., a[n]$ 은 모두 $a[m]$ 보다 크거나 같으므로 이들 중에서는 $x$와 같은 값이 없다. 따라서 $a[i] = x$인 경우가 있다면 $i$는 $0, 1, ..., m-1$ 중 하나이다. 귀납적으로 $search(a, m-1, x)$ 가 정확하다고 가정하면 주장이 성립한다.
• $a[m] < x$ 인 경우: 위의 Case와 비슷함. 

시간 복잡도: $T(n) = 1 + T(n/2) = 1 + (1 + T(n/4)) = ... = log n = O(log n)$

 

4. Recursive Selection Sort

int sort(int a[], int n)
{
    if (n <= 1) return;
    int j, m, t;
    m = 0;
    for (j = 0; j < n; j++) {
        if (a[m] > a[j]) m = j;
    }
    t = a[0]; a[0] = a[m]; a[m] = t;  // swap
    sort(a+1, n-1);
    return;
}

Set of elements preserves / results: $a[0] < a[1] < ... < a[n-1]$

• 집합 조건을 깰 수 있는 코드는 없다.
• $n = 1$인 경우: 할 일이 없다.
• $n-1$ 일 때 sort 함수가 성공한다고 가정하자. (sort() 함수가 실패할 경우는 할 말이 없다.) 즉, 재귀 호출이 끝난 후 $a[1] < a[2] < ... < a[n-1]$ 이다. 
• 코드의 9번째 줄을 보면 a[0]에는 항상 배열 전체에서 가장 작은 값이 들어가있다. 따라서 재귀로 들어가기 전부터 $\forall x ((x>0) \rightarrow (a[0] < a[x]))$ 가 성립했다. 그러므로 n일 때 $a[0] < a[1] < a[2] < ... < a[n-1]$ 이므로 sort 함수가 성공한다.

시간 복잡도: $T(n) = n + T(n-1) = n + (n-1) + T(n-2) = ... = O(n^2)$