Solving Recurrences-알고리즘02

재귀함수의 식을 예로 다음을 볼 수 있다. 이러한 재귀식은 알고리즘을 분석할 때, 특히 recursive algorithm을 분석 할때 많이 쓰인다 예를 들면 n!을 구하는 알고리즘의 T(n)은 어떻게 구할까? f(n)=n! 이라고 할때 f(n)=f(n-1)*n=f(n-2)*(n-1)*(n) .... 이다. f(n)의 연산횟수를 T(n)이라고 한다면 T(n) = T(n-1) + 1 (f(n-1)과 n의 곱셈) = T(n-2) + 1 (f(n-2)와f(n-1)의 곱셈) + 1 이므로 따라서 f(n) = O(n) 이다. 그렇다면 이런식은 어떻게 풀까? 이런 복잡한 식들을 푸는 방법 3가지를 오늘 알아보자. 1. Substitution Method 귀납적 풀이랑 비슷하다.(이산수학에서나오는 것과 똑같은 거 같..

2023.06.12