Data Structures and Algorithms |
9 Dynamic Algorithms |
Sometimes, the divide and conquer approach seems appropriate but fails to produce an efficient algorithm.
We all know the algorithm for calculating Fibonacci numbers:
int fib( int n ) { if ( n < 2 ) return n; else return fib(n-1) + fib(n-2); }This algorithm is commonly used as an example of the elegance of recursion as a programming technique. However, when we examine its time complexity, we find it's far from elegant!
int fib( int n ) { int k, f1, f2; if ( n < 2 ) return n; else { f1 = f2 = 1; for(k=2;k<n;k++) { f = f1 + f2; f2 = f1; f1 = f; } return f; }runs in O(n) time.
This algorithm solves the problem of calculating f_{0} and f_{1} first, calculates f_{2} from these, then f_{3} from f_{2} and f_{1}, and so on. Thus, instead of dividing the large problem into two (or more) smaller problems and solving those problems (as we did in the divide and conquer approach), we start with the simplest possible problems. We solve them (usually trivially) and save these results. These results are then used to solve slightly larger problems which are, in turn, saved and used to solve larger problems again.
Key terms |
Continue on to Binomial Coefficients | Back to the Table of Contents |