DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 832

The new method is implemented in Listing 22.2.

L ISTING 22.2

ImprovedFibonacci.java
1 import java.util.Scanner;
2
3 public class ImprovedFibonacci {
4 /** Main method */
5 public static void main(String args[]) {
6 // Create a Scanner
7 Scanner input = new Scanner(System.in);
8 System.out.print( "Enter an index for the Fibonacci number: " );
9

input

int index = input.nextInt();

10
11 // Find and display the Fibonacci number
12 System.out.println(
13

invoke fib

"Fibonacci number at index " + index + " is " + fib(index));

14 }
15
16 /** The method for finding the Fibonacci number */

17 public static long fib( long n) {

18 long f0 = 0 ; // For fib(0) f0

f1
f2

19 long f1 = 1 ; // For fib(1)

20 long f2 = 1 ; // For fib(2)

21
22 if (n == 0 )

23 return f0;

24 else if (n == 1 )

25 return f1;

26 else if (n == 2 )

27 return f2;

28
29 for ( int i = 3 ; i <= n; i++) {
30 f0 = f1;
31 f1 = f2;
32

update f0, f1, f2

f2 = f0 + f1;

33 }
34
35

return f2;

36 }
37 }

Enter an index for the Fibonacci number: 6
Fibonacci number at index 6 is 8

Enter an index for the Fibonacci number: 7
Fibonacci number at index 7 is 13

Obviously, the complexity of this new algorithm is O ( n ). This is a tremendous improvement
over the recursive O (2 n ) algorithm.
The algorithm for computing Fibonacci numbers presented here uses an approach known
as dynamic programming . Dynamic programming is the process of solving subproblems,
then combining the solutions of the subproblems to obtain an overall solution. This naturally
leads to a recursive solution. However, it would be inefficient to use recursion, because the

O ( n )

dynamic programming