간단한 재귀 algrithom의 실행 시간

Question

나는 이것을 풀 수있는 방법을 알고 있었지만 몇 년 후에 잊는다. 여기에 문제가 있습니다 :

T(n)은 알고리즘 실행 시간이고, T(n)=T(n-1)+T(n-2)입니다.
T (1) 및 T (2)는 실행 시간이 일정합니다.

실행 시간은 T(n)입니다.

Answer 1

구현 방법에 따라 다릅니다. 테이블에 T(n)의 결과를 저장하면 선형 시간으로 실행할 수 있습니다. 그렇지 않은 경우 기하 급수적으로 소요됩니다. (지수는 n입니다.) (위키 피 디아 항목 memoization 참조)