2024-04-03-03. 수학적 귀납법
수학적 귀납법
- 수학적 귀납법의 기본형 : P(1)이 참이고, P(n-1)->P(n)이 참이면, P(n)은 모든 자연수 n에 대해서 참이다.
- 위에서 P(1)을 base라 하고, P(n-1)->P(n)를 step이라 한다.
P(n-1)->P(n)을 증명할 때 P(n-1)이 참이라고 ‘가정’하고 P(n)임을 증명한다.
- 수학적 귀납법의 강한 형태 : P(1)이 참이고, P(1)∧P(2)∧…∧P(n-1)->P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
수학적 귀납법 예제
1+2+...+n = n(n+1)/2 가 모든 자연수 n에 대해 성립함을 증명하여라.
- step : 1+2+...+(n-1) = (n-1)n/2 가 성립한다고 가정하면
1+2+...+(n-1)+n = (n-1)n/2 + n
(n-1)n/2 + n = (n2-n+2n)/2 = n(n+1)/2
1+2+...+(n-1)+n = n(n+1)/2
명제 P->Q의 의미
P(n) : n이 등장하는 문장
명제 : 객관적으로 참, 거짓을 판단할 수 있는 문장. 아래의 4개 문장은 명제이다.
조건 : 그 자체로는 명제가 아니지만, 변수값에 따라 참, 거짓을 판단할 수 있는 문장. 아래에서 P와 Q는 조건이다.
- P가 참, Q가 참 -> 전체는 참
- P가 참, Q가 거짓 -> 전체는 거짓
- P가 거짓, Q가 참 -> 전체는 참
- P가 거짓, Q가 거짓 -> 전체는 참
예전에는 3, 4번째 경우를 vacuous(공허한)이라고 했다.
그러나 이 경우를 true라고 하는 것이 더 편리하기에 지금은 참이라고 한다.
ex1) 자연수 n에 대해 3<n -> 10<n2
- 위 명제는 참인가?
- n = 1일 때, 위 명제는 참. (거짓->거짓)
ex2) 자연수 n에 대해 1<n -> 10<n2
n=1, n=4일 때는 참이 되지만, n=2일 때는 거짓이 된다.
수학적 귀납법을 통한 재귀함수 증명
unsigned int sum(unsigned int x)
{
if(x <= 0) return 0;
return x + sum(x – 1);
}
위 함수가 항상 0+1+2+…+x 를 리턴한다는 것을 증명해 보자.
S(3)->S(2)->S(1)->S(0)->0->1->3->6 처럼 따라 들어가는 식으로 생각하면 복잡한 함수에서 증명하기 어렵다. 수학적 귀납법을 이용해 증명하자.
- P(1)이 참이다 : “sum(1)이 리턴하는 값은 1이다”를 증명하면 됨. 실제 코드에 1을 대입하면 1을 리턴함을 알 수 있음.
- P(x-1) -> P(x) 가 참이다 : “sum(x-1)이 1+2+…+(x-1)을 리턴하면 sum(x)는 1+2+…+x를 리턴한다”를 증명하면 됨.
- 코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴함. sum(x-1)의 리턴 값은 1+2+…+(x-1)과 같다고 가정했으므로 sum(x)는 1+2+…+(x-1)+x를 리턴함을 확인할 수 있음
재귀함수의 시간복잡도 계산
위 함수에서 sum(n)을 실행하는 데 걸리는 시간이 T(n)이라고 하자.
점근 표기법을 이용할 것이므로, if문의 비교 연산과 return문의 더하기 연산에 걸리는 시간이 총 1이라고 해도 문제가 없다. 따라서 다음 식이 성립한다.
T(n) = (n<=0 계산 시간) + (n + sum(n-1) 덧셈 계산 시간) + (sum(n-1) 실행 시간)
= 1 + T(n-1)
T(n-1) = 1 + T(n-2)
T(n-2) = 1 + T(n-3)
...
T(1) = 1+T(0)
T(0) = 1
T(n) = 1+1+1+...+1 = n
따라서 T(n) = O(n)이 성립한다.