Java Reference
In-Depth Information
Proof of
Theorem 7.5
(continued from previous page)
T
()
OA
M
ON
B
A
log
(7.11)
=
(
)
=
(
).
If
A
=
B
k
, then each term in the sum in Equation 7.10 is
1
. As the sum contains
1 +
log
B
N
terms and
A
=
B
k
implies
A
M
=
N
k
,
T
(
N
) =
O
(
A
M
log
B
N
) =
O
(
N
k
log
B
N
) =
O
(
N
k
log
N
).
Finally, if
A < B
k
, then the terms in the geometric series are larger than 1. We can com-
pute the sum using a standard formula, thereby obtaining
+
B
k
-----
M
1
⎝
⎛⎞
-
1
------------------------------
OA
M
B
k
M
⎛
⎝
⎛⎞
⎞
M
A
M
OB
k
ON
k
TN
()
=
=
=
(
()
)
=
()
-----
⎝
⎠
B
k
-----
-
1
proving the last case of Theorem 7.5.
dynamic programming
7.6
A problem that can be mathematically expressed recursively can also be
expressed as a recursive algorithm. In many cases, doing so yields a signifi-
cant performance improvement over a more naive exhaustive search. Any
recursive mathematical formula could be directly translated to a recursive
algorithm, but often the compiler may not do justice to the recursive algorithm
and an inefficient program results. That is the case for the recursive computa-
tion of the Fibonacci numbers described in Section 7.3.4. To avoid this recur-
sive explosion, we can use
dynamic programming
to rewrite the recursive
algorithm as a nonrecursive algorithm that systematically records the answers
to the subproblems in a table. We illustrate this technique with the following
problem.
Dynamic program-
ming
solves sub-
problems nonrecur-
sively by recording
answers in a table.
change-making problem
For a currency with coins (cents) what is the minimum number of
coins needed to make
K
cents of change?
C
1
C
2
,
,
…
C
N
,
U.S. currency has coins in 1-, 5-, 10-, and 25-cent denominations (ignore
the less frequently occurring 50-cent piece). We can make 63 cents by using
two 25-cent pieces, one 10-cent piece, and three 1-cent pieces, for a total of
six coins. Change-making in this currency is relatively simple: We repeatedly
use the largest coin available to us. We can show that for U.S. currency this
approach always minimizes the total number of coins used, which is an
Greedy algorithms
make locally opti-
mal decisions at
each step. This is
the simple, but not
always the correct,
thing to do.
Search WWH ::
Custom Search