28-09-2012, 12:56 PM
Fibonacci numbers
Fibonacci.ppt (Size: 532 KB / Downloads: 243)
Redundant Calculations I
To compute fib(n), we recursively compute fib(n-1). When the recursive call return, we compute fib(n-2) using another recursive call
We have already computed fib(n-2) in the process of computing fib(n-1)
We make two calls to fib(n-2)
Redundant Calculations II
Making two method calls would double the running time
Compounding effect: each recursive call does more and more redundant work
Each call to fib(n-1) and each call to fib(n-2) makes a call to fib(n-3); there are 3 calls to fib(n-3)
Each call to fib(n-2) or fib(n-3) results in a call to fib(n-4), so 5 calls to fib(n-4)
Redundant Calculations III
C(n): number of calls to fib method
C(0)=C(1)=1;
For n>=2, we call fib(n) and plus all the calls needed to evaluate fib(n-1) and fib(n-2) recursively and independently; so C(n)=c(n-1)+c(n-2)+1
The recursive routine fib is exponential
Dynamic Programming – Example
Dynamic programming version of fibonacci(n)
If n is 0 or 1, return 1
Else solve fibonacci(n-1) and fibonacci(n-2)
Look up value if previously computed
Else recursively compute
Find their sum and store
Return result
Dynamic programming algorithm O(n) time
Since solving fibonacci(n-2) is just looking up value