알고리즘 Search & Sort

대부분의 알고리즘은 수학적 귀납법을 이용해서 증명이 가능함 (재귀적인 구조이기 때문)

수학적 귀납법

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

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

int sum(int x) {
        if (x == 1) return 1;
        return x + sum(x - 1);
}

base) sum(1) returns 1 → True

step) “sum(x - 1)이 $1 + 2 + … + (n-1)$을 반환하면, sum(x)이 $1 + 2 + … + (n-1) + n$를 반환한다”를 증명한다.

→ 코드는 x + sum(x-1) 를 반환하므로, sum(x - 1)은 1 + 2 + … + (x - 1)이라고 가정했다. 그러므로 sum(x)의 반환값은 1 + 2 + … + (x - 1) + x와 같음을 증명할 수 있음.

 

Complexity

$T(n)=1+T(n-1) \ = 1 + 1 + T(n - 2) = ... = n \ \therefore T(n) = O(n)$

 

Binary Search

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

 

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 {
                r = search(a + m + 1, n - m - 1, x);
                if (r == -1) return -1;
                else return r + m + 1;
        }
}

 

Proof by Invariant

만약 어떤 i에 대해서 a[i] == x라면 l <= i <= r이 항상 성립한다.

→ Invariant는 최초에 성립, 이후 코드 내에서 invariant를 깨는 코드가 없음

a[i] == x인 i가 없다면 루프는 반드시 끝나고, -1을 반환

a[i] == x인 i가 없다면 루프 안에서 반드시 반환

 

Proof by Induction

가정 : 만약 어떤 i에 대해 a[i] == x라면 함수는 i를 반환한다.

base) n == 0인 경우 어떤 i에 대해서 a[i] == x가 성립할 방법이 없고, 함수는 항상 -1을 반환

step)

case 1. a[m] == x인 경우, m을 반환

case 2. a[m] > x인 경우, a[m], a[m + 1], …, a[n] 중에서는 x와 같은 값이 존재할 수 없음. 따라서 a[i] == x인 경우가 있다면 i는 0, 1, …, (m-1) 중 하나이다. 귀납적으로 search(a, m-1, x)가 정확하다고 가정하면, 재귀적으로 최상위 함수에서 위 가정이 참이다.

case 3. a[m] < x인 경우, a[0], a[1], …, a[m] 중에서는 x와 같은 값이 존재할 수 없음. 따라서 a[i] == x인 경우가 있다면 i는 (m+1), (m+2), …, n중에 하나이다. 귀납적으로 search(a + m + 1, n - m - 1, x)가 정확하다고 가정하면, 재귀적으로 최상위 함수에서 위 가정이 참이다.

 

Complexity

$T(n) = 1 + T(n/2) \ = 1 + 1 + T(n / 4) = ... = \log n \ \therefore T(n)=O(\log n)$

 

Selection Sort

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

 

Proof of Correctness of Sorting

sorting이 끝난 후 배열의 값들을 b[0], b[1], …, b[n-1]

condition 1. {a[0], a[1], …, a[n-1]} = {b[0], b[1], …, b[n-1]}

condition 2. b[0] < b[1] < … < b[n-1]

 

Proof by Invariant

코드 내 집합 조건을 깨는 코드는 없음 (값 변경은 swap)

Invariant : k번째 루프가 끝난 후

1) a[0] < a[1] < … < a[k-1] → a[0] < a[1] < … < a[n-1]

2) a[k-1] < a[x] if x > k - 1

Proof Invariant by Induction

base) k = 0, 1) Null Condition → True, 2) Null Condition → True

step)

k번째 루프가 끝났을 때 invariant가 성립한다면, k+1번째 루프가 끝났을 때도 invariant가 성립

k번째 루프 끝난 후 Invariant

1) a[0] < a[1] < … < a[k - 1]

2) a[k - 1] < a[x] if x > k - 1

a[k], …, a[n - 1] 중 최솟값을 a[k]로 이동했다

k+1번째 루프가 끝난 후 Invariant

1) a[0] < a[1] < … < a[k-1] < a[k]

→ k번째 invariant 2)에 의해 a[k - 1] < a[k] (k > k - 1)

2) a[k] < a[x] if x > k

 

Recursive Selection Sort

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

 

Proof by Induction

집합 조건을 깨는 코드는 없음

base) n == 1, Null Condition → True

step)

n - 1일 때 sort()가 성공한다면, 재귀 호출이 끝난 후 a[1] < a[2] < … < a[n-1] 가정

n일 때 sort()가 성공한다면, 함수가 끝날 때 a[0] < a[1] < a[2] < … < a[n-1] 성립

→ a[0] < a[x]를 재귀 전 for문에서 보장

→ a[0] < a[x], (x > 0)은 재귀적으로 참

 

The Complexity

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