with with

재귀함수를 이용하여 구현된 알고리즘의 경우 시간 복잡도 함수를 구하다 보면 재귀식으로 이루어진 시간 복잡도 함수를 마주하게 된다. 이런 경우 재귀식을 일반식으로 수정해야 하는데, 그 방법을 알아보자. * 선형인 재귀식의 경우만을 다룹니다. - Homogeneous case f(n) = 0 인 형태의 식을 homogeneous라고 하는데, 이런 경우의 재귀식을 계산하는 법을 알아보자. 위 식을 생각해보자. tk 항으로 이루어진 재귀식이다. 이 경우 아래와 같은 특성 방정식(characteristic equation)으로 변환 가능하다. 여기서 두 가지 경우로 나뉘는데, (r-1)(r-2)(r-3) 처럼 중근을 갖지 않는 경우와 (r-1)(r-2)^2 처럼 중근을 갖는 경우로 나뉘게 된다. * 중근을 갖지 ..