[Algorithm] 재귀식(Recurrence)

재귀식(Recurrence)란? 재귀식은 작은 입력에 대한 값으로 함수를 설명하는 방정식 또는 부등식입니다.

조금 다른 관점에서 접근하면 수열의 점화식과 동일한 내용입니다. 형태로는 기저 사례와 재귀 사례로 구분해서 표현합니다.

재귀식과 실행 시간 재귀 알고리즘을 분석할 때 재귀식은 자연스럽게 나타납니다. 하단 Merge Sort는 분석할 때 자연스럽게 재귀식 형태로 호출하는 것을 볼 수 있습니다.

하지만 알고리즘을 분석할 때 이러한 재귀식은 어떻게 해야할지 난감하다는 문제가 있습니다. 재귀식과 점근 성능 분석 결과 예시 몇몇 대표적인 재귀식과 해당 재귀식의 점근 성능 분석 결과가 있습니다.

재귀식의 점근 성능 분석 위와 같은 재귀식의 점근 성능 분석은 다음과 같은 방법으로 할 수 있습니다. 치환법(Substitution Method) 재귀 트리법(Recursion Tree Method) 마스터 정리(Master Method) 마무리 재귀식은 컴퓨터공학에서 사용자가 무슨 의미인지 해...