[ 자료구조 ] 기본사항: 수학적 귀납법, 시간복잡도

 

수학적 귀납법 ( 명제 :  P(n)이 있을때 )

•  기본형 : p(1)이 참이고, p(n-1) ->  p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다.
•  강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) ->  p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다.

수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다.

 

base: p(1) 이 참이다.

step : p(n-1) ->  p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다.

 

base 와 step은 서로 독립적이고, 보통 base는 참인것을 금방 알수 있으며, 포인트가 되는 것은 step 부분이 참인 것을

알아내는 것이다.

그런데 step 에서 p(n-1) ->  p(n) 을 잘보면 둘다 참일 필요가 없다. 

 

명제 P -> Q 의 의미

• P -> Q
  • P 가 참 , Q가 참 ->  참
  • P가 참, Q가 거짓 -> 거짓
  • P가 거짓, Q가 참 ->  참
  • P가 거짓, Q가 거짓 -> 참 

예시로 알고리즘을 보고 정확하고 빠른지 한번 알아보자

 

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

위 코드는 1부터 x 까지 모두 더해주는 함수이다. 

가장 평범한 코드이고 시간은 x만큼 반복하므로 x만큼 시간을 쓸 것이다.

 

이는 재귀를 이용하여 작성할 수 있다.

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

이 함수는 x 에 sum(x-1)을 더하는 재귀적인 함수이다.  이 함수가 정확하게 실행 될 지 수학적 귀납법으로 증명해보자.

 

p(x)  :  sum(x)는 1+2+3+...+x를 항상 리턴한다.

 

Base : P(1)이 참이다.

"sum(1)이 리턴하는 값은 1이다."를 증명하면 된다. 실제 코드에 1을 대입해보자. 

처음에는 return 1 + sum(0) 이 리턴 된 것이고 sum(0)은  if문에 걸려 0을 반환하며 종료하게 된다.

결론적으로는 1를 리턴한다.

 

Step : P(x-1) -> P(x) 이 참이다.

sum(x-1)이 1+2+3+4+...+x-1 를 리턴하면, sum(x)는 1+2+3+4+...+x 를 리턴한다를 보여주면 된다.

코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴함. sum(x-1)의 리턴값은 1+2+3+..+(x-1) 과 같다고 가정했으므로 sum(x)는 1+2+...+(x-1)+x = 1+2+...+x를 리턴한다. 

 

이제 Complexity 를 생각해보자.

 

Complexity( 시간 복잡도 )

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

따라서 T(n) = O(n)