수학적 귀납법

  • 수학적 귀납법의 기본형: P(1)이 참이고, P(n-1)->P(n)이 참이면 P(n)은 모든 자연수 n에 대하여 참이다.
  • 수학적 귀납법의 강한 형태: P(1)이 참이고, P(1)^P(2)^… ^P(n-1)->P(n)이 참이면 P(n)은 모든 자연수 n에 대하여 참이다.

명제 P->Q의 의미

P Q T/F
T T T
T F F
F T T
F F T

100 점을 받으면 치킨을 쏜다고 하자. 여기서 P는 “100점을 받는다”, Q는 “치킨을 쏜다”에 해당한다.

  • P가 참이고 Q가 참인 경우: 100점을 받았고, 치킨을 쐈으니까 참이다.
  • P가 참이고 Q가 거짓인 경우: 100점을 맞았음에도 치킨을 쏘지 않았으므로 것이다.
  • P가 거짓인 경우: 치킨을 쐈든 안 쐈든 간에 틀린 말은 안 했으므로.. 참이다.

왜 이걸 설명하느냐 하면, “P(n-1)->P(n)”이 참이라면 P(n-1)이 거짓인 경우와, P(n-1)과 P(n)이 모두 참인 두 가지 경우가 존재하기 때문이다.
근데 P(n-1)이 거짓인 경우에는 어차피 참이 되어버리기 때문에 우리는 P(n-1)과 P(n)이 모두 참인 경우에 대해서만 증명을 할 것이다.

재귀

1부터 n까지의 합을 return하는 함수에 대해 생각해보자.

간단한 함수로 나타낼 수 있다.

int sum(int x)
{
    int i, S;
    S = 0;
    for (int i; i <= x; i++) S += i;
    return S;
}

심지어 더 간단한 함수로 나타낼 수 있다!

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

코드를 읽는 방법

코드를 읽는 방법에는 두 가지가 있다:

원래 읽던 방법

sum(4) = 4 + sum(3) = 4 + 3 + sum(2) = … = 4 + 3 + 2 + 1 + sum(0)

수학적 귀납법으로 읽기

P(x): sum(x)는 1 + 2 + … + x를 리턴한다.

Proof
  • base case: P(1)이 참이다: sum(1)이 리턴하는 값이 1이다. (성립)
  • step: P(x-1)->P(x)이 참이다:
    • “sum(x-1)이 1+2+..+x-1을 리턴하면 sum(x)는 1+2+…+x-1+x를 리턴한다”를 증명하면 된다.
    • 코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴하고 있다.
    • sum(x-1)의 리턴값은 1+2+…+x-1과 같다고 가정했으므로 sum(x)는 1+2+…+x를 리턴함을 알 수 있다.
The Complexity
T(n) = 1 + T(n-1)
     = 1 + 1 + T(n-2) 
     ... = n
     
--> 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;
}

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

  • Invariant: 만약 어떤 i에 대해 a[i]=x라면 I <= 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)가 정확하다고 가정하면, 즉, 제일 위 주장이 search(a, m-1, x)에서 성립한다고 가정하면 제일 위 주장이 성립함.
    • case 3: case 2와 유사함