NLP Learner in Switzerland

[C] Recurrence Mathematical Induction ::: 점화식 귀납법으로 풀기 본문

Algorithm in C/Exercise

[C] Recurrence Mathematical Induction ::: 점화식 귀납법으로 풀기

초코빵 2021. 4. 6. 10:00
728x90
반응형

 

까다로운 부분 알아가기

Mathematical induction 수학적 귀납법 방식으로 푸는데는 정해진 단계가 있다.

 

1. Base case를 찾는다. 보통은 n=0 또는 1이고 대부분 문제에 주어지거나 추측할 수 있다. 이를 통해서 T(0) 혹은 T(1)을 구하고 구한 값이 가설과 일치하는지 확인한다.

2. Inductive Hypothesis를 세운다. n일 때 가설이 참이라고 가정한다. Assume T(n) True.

3. Inductive Step을 따라간다. n+1인 경우의 점화식을 도출하고, 2단계에서 가정한 참T(n)값을 반영하여 n+1일 때도 가설이 참임을 증명할 수 있는지 확인하는 단계이다.

 

정답

'Algorithm in C > Exercise' 카테고리의 다른 글

[C] Asymptotic tight bound ::: 점근적 하한 계산하기  (0) 2021.04.05
[C] Running time and Asymptotic complexity ::: 시간복잡도(정확한 수행시간 및 점근적 표기)  (0) 2021.04.04
[C] Pascal Triangle ::: 파스칼 삼각형 출력하기  (0) 2021.04.03
[C] Iteration and Recursion ::: 문자열에서 첫번째 대문자 찾아 인덱스를 반환하기  (0) 2021.04.02
[C] Multiple Recursion ::: 재귀호출이 2번 이상 일어나는 경우  (0) 2021.04.01
'Algorithm in C/Exercise' Related Articles more
Comments