피보나치 수를 이렇게 계산하면 시간이 상당히 오래 걸린다.Exs 2 참고로 이 함수의 실행 시간을 구하는 식도 함수처럼 재귀식으로 표현된다.
Tfib(1) = C0
(7.9)
Tfib(2) = C0
(7.10)
모든 i > 3에 대해 Tfib(i) = Tfib(i–1) + Tfib(i–2) + C1
(7.11)
여기서 C0과 C1는 상수로서 구체적인 값은 플랫폼마다 다르다.
기발한 구현 방식 덕분에 플랫폼에 상관없이 이 함수의 실행 시간은 항상 다음과 같다.
(7.12)
여기 나온 C2도 플랫폼 종속적인 상수다. 따라서 fib(n)의 실행 시간은 n에 대한 지수함수다. 그래서 실전에서 쓰기에는 안 좋은 성능이다.
Exs 2 n을 다양한 수로 지정해서 fib(n)을 호출하고 각각 시간을 측정해 보자. POSIX 시스템이라면 /bin/time으로 프로그램의 실행 시간을 측정할 수 있다.