Java Reference
In-Depth Information
Programming
This section analyzes and designs an efficient algorithm for finding Fibonacci
numbers using dynamic programming.
Key
Point
Section 18.3, Case Study: Computing Fibonacci Numbers, gave a recursive method for find-
ing the Fibonacci number, as follows:
/** The method for finding the Fibonacci number */
public static long
fib(
long
index) {
if
(index ==
0
)
// Base case
return
0
;
else if
(index ==
1
)
// Base case
return
1
;
else
// Reduction and recursive calls
return
fib(index -
1
) + fib(index -
2
);
}
We can now prove that the complexity of this algorithm is
O
(2
n
). For convenience, let the
index be
n
. Let
T
(
n
) denote the complexity for the algorithm that finds fib(
n
) and
c
denote the
constant time for comparing the index with
0
and
1
; that is,
T
(1) and
T
(0) are
c
. Thus,
T
(
n
)
=
T
(
n
-
1)
+
T
(
n
-
2)
+
c
…
2
T
(
n
-
1)
+
c
…
2(2
T
(
n
-
2)
+
c
)
+
c
2
2
T
(
n
=
-
2)
+
2
c
+
c
Similar to the analysis of the Tower of Hanoi problem, we can show that
T
(
n
) is
O
(2
n
).
However, this algorithm is not efficient. Is there an efficient algorithm for finding a Fibo-
nacci number? The trouble with the recursive
fib
method is that the method is invoked redun-
dantly with the same arguments. For example, to compute
fib(4)
,
fib(3)
and
fib(2)
are invoked. To compute
fib(3)
,
fib(2)
and
fib(1)
are invoked. Note that
fib(2)
is
redundantly invoked. We can improve it by avoiding repeatedly calling of the
fib
method
with the same argument. Note that a new Fibonacci number is obtained by adding the pre-
ceding two numbers in the sequence. If you use the two variables
f0
and
f1
to store the two
preceding numbers, the new number,
f2
, can be immediately obtained by adding
f0
with
f1
.
Now you should update
f0
and
f1
by assigning
f1
to
f0
and assigning
f2
to
f1
, as shown
in Figure 22.2.
f0 f1 f2
Fibonacci series: 0 1
1
2 3
5
8
13 21
34
55
89 ...
indices: 0 1
2
3 4
5
6
7
8
9
10
11
f0 f1 f2
Fibonacci series: 0 1
1
2 3
5
8
13 21
34
55
89 ...
indices: 0 1
2
3 4
5
6
7
8
9
10
11
f0
f1
f2
Fibonacci series: 0 1
1
2 3
5
8
13 21
34
55
89 ...
indices: 0 1
2
3 4
5
6
7
8
9
10
11
F
IGURE
22.2
Variables
f0
,
f1
, and
f2
store three consecutive Fibonacci numbers in the
series.
Search WWH ::
Custom Search