Asymptotic Analysis Method (점근적 분석법) - 점화식* 의 점근적 복잡도를 구하는 방법 - 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리) * 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식 ex) 피보나치 수열 : F(n)=F(n−1)+F(n−2) ex) 팩토리얼의 함수적 표현 : f(n)=n∗f(n−1) 마스터 정리 Master Theorem - 특정 형태의 재귀식에서 바로 결과를 도출하는 방법 - 입력의 크기가 n인 문제를 풀기 위해 입력의 크기가 bn 인 문제를 풀고, 나머지 f(n) 의 오버헤드가 필요한 알고리즘의 점화식을 풀 수 있음 \(T..
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(n2)+n 의 추정 후 증명법을 통한 풀..
Asymptotic Analysis Method (점근적 분석법) - 점화식* 의 점근적 복잡도를 구하는 방법 - 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리) * 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식 ex) 피보나치 수열 : F(n)=F(n−1)+F(n−2) ex) 팩토리얼의 함수적 표현 : F(n)=n∗F(n−1) 반복 대치 - 점화식을 반복하여 대치해가면서 점화식을 전체적으로 나열시킨 후에 점근적 시간복잡도(Time Complexity)를 구하는 방법 ex) 팩토리얼값(n!)을 구하는 알고리즘의 시간복잡도 분석과정 Factorial(n){ if (n = 1) return 1; // 1 else..
