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

subproblems overlap. The key idea behind dynamic programming is to solve each subproblem
only once and store the results for subproblems for later use to avoid redundant computing of
the subproblems.

22.14

✓ ✓

What is dynamic programming? Give an example of dynamic programming.

Check

22.15

Why is the recursive Fibonacci algorithm inefficient, but the nonrecursive Fibonacci
algorithm efficient?

Point

22.6 Finding Greatest Common Divisors Using
Euclid's Algorithm
This section presents several algorithms in the search for an efficient algorithm for
finding the greatest common divisor of two integers.

Key
Point
GCD

The greatest common divisor (GCD) of two integers is the largest number that can evenly
divide both integers. Listing 5.9, GreatestCommonDivisor.java, presented a brute-force algo-
rithm for finding the greatest common divisor of two integers m and n . Brute force refers to an
algorithmic approach that solves a problem in the simplest or most direct or obvious way. As
a result, such an algorithm can end up doing far more work to solve a given problem than a
cleverer or more sophisticated algorithm might do. On the other hand, a brute-force algorithm
is often easier to implement than a more sophisticated one and, because of this simplicity,
sometimes it can be more efficient.
The brute-force algorithm checks whether k (for k = 2 , 3 , 4 , and so on) is a common
divisor for n1 and n2 , until k is greater than n1 or n2 . The algorithm can be described as
follows:

brute force

public static int gcd( int m, int n) {
int gcd = 1 ;

for ( int k = 2 ; k <= m && k <= n; k++) {
if (m % k == 0 && n % k == 0 )
gcd = k;
}

return gcd;

}

Assuming m n , the complexity of this algorithm is obviously O ( n ).

Is there a better algorithm for finding the GCD? Rather than searching a possible divisor
from 1 up, it is more efficient to search from n down. Once a divisor is found, the divisor is
the GCD. Therefore, you can improve the algorithm using the following loop:

Ú

assume m Ú n

O ( n )

improved solutions

for ( int k = n; k >= 1 ; k--) {
if (m % k == 0 && n % k == 0 ) {
gcd = k;
break ;

}
}

This algorithm is better than the preceding one, but its worst-case time complexity is still O ( n ).
A divisor for a number n cannot be greater than n / 2 , so you can further improve the
algorithm using the following loop:

for ( int k = m / 2 ; k >= 1 ; k--) {
if (m % k == 0 && n % k == 0 ) {
gcd = k;