귀납법

[Discrete Mathematics] 점근적 분석법 - 추정 후 증명

Asymptotic Analysis Method (점근적 분석법) - 점화식* 의 점근적 복잡도를 구하는 방법 - 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리) * 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식 ex) 피보나치 수열 : \(F(n) = F(n-1) + F(n-2)\) ex) 팩토리얼의 함수적 표현 : \(f(n) = n * f(n-1)\) 추정 후 증명 Substitution Method - 점화식의 모양을 보고 점근적 복잡도를 추정한 후, 귀납적으로 증명하여 점근적 시간복잡도(Time Complexity)를 구하는 방법 ex) 점화식 \(T(n) ≤ 2T({n \over 2}) + n\) 의 추정 후 증명법을 통한 풀..