📄 chap04.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 4: RECURRENCES</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap05.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap03.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0712_11cc">CHAPTER 4: RECURRENCES<a name="0712_11cc"></h1><P>
<a name="0712_11cb">As noted in Chapter 1, when an algorithm contains a recursive call to itself, its running time can often be described by a recurrence. A <I><B>recurrence</I> </B>is an equation or inequality that describes a function in terms of its value on smaller inputs. For example, we saw in Chapter 1 that the worst-case running time <I>T</I>(<I>n</I>) of the <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> procedure could be described by the recurrence<P>
<img src="53_a.gif"><P>
<h4><a name="0712_11cd">(4.1)<a name="0712_11cd"></sub></sup></h4><P>
whose solution was claimed to be <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>).<P>
This chapter offers three methods for solving recurrences--that is, for obtaining asymptotic "<img src="../images/bound.gif">" or "<I>O</I>" bounds on the solution. In the <I><B>substitution method</I></B>, we guess a bound and then use mathematical induction to prove our guess correct. The <I><B>iteration method</I></B> converts the recurrence into a summation and then relies on techniques for bounding summations to solve the recurrence. The <I><B>master method</I></B> provides bounds for recurrences of the form<P>
<pre><I>T</I>(<I>n</I>) = <I>aT</I>(<I>n</I>/<I>b</I>) + <img src="../images/scrptf12.gif">(<I>n</I>),</sub></sup></pre><P>
where <I>a</I> <img src="../images/gteq.gif"> 1, <I>b</I> > 1, and <img src="../images/scrptf12.gif">(<I>n</I>) is a given function; it requires memorization of three cases, but once you do that, determining asymptotic bounds for many simple recurrences is easy.<P>
<h2>Technicalities</h2><P>
In practice, we neglect certain technical details when we state and solve recurrences. A good example of a detail that is often glossed over is the assumption of integer arguments to functions. Normally, the running time <I>T</I>(<I>n</I>) of an algorithm is only defined when <I>n</I> is an integer, since for most algorithms, the size of the input is always an integer. For example, the recurrence describing the worst-case running time of <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> is really<P>
<img src="53_b.gif"><P>
<h4><a name="0714_0001">(4.2)<a name="0714_0001"></sub></sup></h4><P>
Boundary conditions represent another class of details that we typically ignore. Since the running time of an algorithm on a constant-sized input is a constant, the recurrences that arise from the running times of algorithms generally have <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(1) for sufficiently small <I>n</I>. Consequently, for convenience, we shall generally omit statements of the boundary conditions of recurrences and assume that <I>T</I>(<I>n</I>) is constant for small <I>n</I>. For example, we normally state recurrence (4.1) as<P>
<pre><I>T</I>(<I>n</I>) = 2<I>T</I>(<I>n</I>/2) + <img src="../images/bound.gif">(<I>n</I>),</sub></sup></pre><P>
<h4><a name="0714_0002">(4.3)<a name="0714_0002"></sub></sup></h4><P>
without explicitly giving values for small <I>n</I>. The reason is that although changing the value of <I>T</I>(1) changes the solution to the recurrence, the solution typically doesn't change by more than a constant factor, so the order of growth is unchanged.<P>
When we state and solve recurrences, we often omit floors, ceilings, and boundary conditions. We forge ahead without these details and later determine whether or not they matter. They usually don't, but it is important to know when they do. Experience helps, and so do some theorems stating that these details don't affect the asymptotic bounds of many recurrences encountered in the analysis of algorithms (see Theorem 4.1 and Problem 4-5). In this chapter, however, we shall address some of these details to show the fine points of recurrence solution methods.<P>
<P>
<h1><a name="0715_11ce">4.1 The substitution method<a name="0715_11ce"></h1><P>
<a name="0715_11cc"><a name="0715_11cd">The substitution method for solving recurrences involves guessing the form of the solution and then using mathematical induction to find the constants and show that the solution works. The name comes from the substitution of the guessed answer for the function when the inductive hypothesis is applied to smaller values. This method is powerful, but it obviously can be applied only in cases when it is easy to guess the form of the answer.<P>
The substitution method can be used to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence<P>
<pre><I>T</I>(<I>n</I>) = 2<I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif">) + <I>n</I>,</sub></sup></pre><P>
<h4><a name="0715_11cf">(4.4)<a name="0715_11cf"></sub></sup></h4><P>
which is similar to recurrences (4.2) and (4.3). We guess that the solution is <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I> lg <I>n</I>). Our method is to prove that <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I> lg <I>n</I> for an appropriate choice of the constant <I>c</I> > 0. We start by assuming that this bound holds for <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>, that is, that <I>T</I>(<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>) <img src="../images/lteq12.gif"> <I>c</I> <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> 1g (<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>). Substituting into the recurrence yields<P>
<pre><I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> 2(<I>c </I><img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif"> 1g (<img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif">)) + <I>n</I></sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> <I>cn </I>lg(<I>n</I>/2) + <I>n</I></sub></sup></pre><P>
<pre>= <I>cn </I>lg <I>n - cn</I> lg 2 +<I> n</I></sub></sup></pre><P>
<pre>= <I>cn</I> lg <I>n - cn </I>+ <I>n</I></sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> <I>cn</I> lg <I>n,</I></sub></sup></pre><P>
where the last step holds as long as <I>c</I> <img src="../images/gteq.gif"> 1.<P>
Mathematical induction now requires us to show that our solution holds for the boundary conditions. That is, we must show that we can choose the constant <I>c</I> large enough so that the bound <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I> lg <I>n</I> works for the boundary conditions as well. This requirement can sometimes lead to problems. Let us assume, for the sake of argument, that <I>T</I>(1) = 1 is the sole boundary condition of the recurrence. Then, unfortunately, we can't choose <I>c</I> large enough, since <I>T</I>(1) <img src="../images/lteq12.gif"> <I>c</I>1 lg 1 = 0.<P>
This difficulty in proving an inductive hypothesis for a specific boundary condition can be easily overcome. We take advantage of the fact that asymptotic notation only requires us to prove <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I> lg <I>n</I> for <I>n</I> <img src="../images/gteq.gif"> <I>n</I><SUB>0</SUB>, where <I>n</I><SUB>0</SUB> is a constant. The idea is to remove the difficult boundary condition <I>T</I>(1) = 1 from consideration in the inductive proof and to include <I>n</I> = 2 and <I>n</I> = 3 as part of the boundary conditions for the proof. We can impose <I>T</I>(2) and <I>T</I>(3) as boundary conditions for the inductive proof because for <I>n</I> > 3, the recurrence does not depend directly on <I>T</I>(1). From the recurrence, we derive <I>T</I>(2) = 4 and <I>T</I>(3) = 5. The inductive proof that <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I> lg <I>n</I> for some constant <I>c</I> <img src="../images/gteq.gif"> 2 can now be completed by choosing <I>c</I> large enough so that <I>T</I>(2) <img src="../images/lteq12.gif"> <I>c</I>2 lg 2 and <I>T</I>(3) <img src="../images/lteq12.gif"> <I>c</I>3 lg 3. As it turns out, any choice of <I>c</I> <img src="../images/gteq.gif"> 2 suffices. For most of the recurrences we shall examine, it is straightforward to extend boundary conditions to make the inductive assumption work for small <I>n</I>.<P>
<h2>Making a good guess</h2><P>
Unfortunately, there is no general way to guess the correct solutions to recurrences. Guessing a solution takes experience and, occasionally, creativity. Fortunately, though, there are some heuristics that can help you become a good guesser.<P>
If a recurrence is similar to one you have seen before, then guessing a similar solution is reasonable. As an example, consider the recurrence<P>
<pre><I>T</I>(<I>n</I>) = 2<I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif"> + 17) + <I>n</I>,</sub></sup></pre><P>
which looks difficult because of the added "17" in the argument to <I>T</I> on the right-hand side. Intuitively, however, this additional term cannot substantially affect the solution to the recurrence. When <I>n</I> is large, the difference between <I>T</I>(<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>) and <I>T</I>(<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 17) is not that large: both cut <I>n</I> nearly evenly in half. Consequently, we make the guess that <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I> lg <I>n</I>), which you can verify as correct by using the substitution method (see Exercise 4.1-5).<P>
Another way to make a good guess is to prove loose upper and lower bounds on the recurrence and then reduce the range of uncertainty. For example, we might start with a lower bound of <I>T</I>(<I>n</I>) = <img src="../images/omega12.gif">(<I>n</I>) for the recurrence (4.4), since we have the term <I>n </I>in the recurrence, and we can prove an initial upper bound of <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I><SUP>2</SUP>). Then, we can gradually lower the upper bound and raise the lower bound until we converge on the correct, asymptotically tight solution of <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>).<P>
<P>
<h2>Subtleties</h2><P>
There are times when you can correctly guess at an asymptotic bound on the solution of a recurrence, but somehow the math doesn't seem to work out in the induction. Usually, the problem is that the inductive assumption isn't strong enough to prove the detailed bound. When you hit such a snag, revising the guess by subtracting a lower-order term often permits the math to go through.<P>
Consider the recurrence<P>
<pre><I>T</I>(<I>n</I>) = <I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif">) + <I>T</I> (<img src="../images/hfbrul14.gif"><I>n</I>/2<img src="../images/hfbrur14.gif">) + 1.</sub></sup></pre><P>
We guess that the solution is <I>O</I>(<I>n</I>), and we try to show that <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn </I>for an appropriate choice of the constant <I>c</I>. Substituting our guess in the recurrence, we obtain<P>
<pre><I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>c </I><img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif"> + <I>c </I><img src="../images/hfbrul14.gif"><I>n</I>/2<img src="../images/hfbrur14.gif"> + 1</sub></sup></pre><P>
<pre>= <I>cn</I> + 1,</sub></sup></pre><P>
which does not imply <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I> for any choice of <I>c</I>. It's tempting to try a larger guess, say <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I><SUP>2</SUP>), which can be made to work, but in fact, our guess that the solution is <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I>) is correct. In order to show this, however, we must make a stronger inductive hypothesis.<P>
Intuitively, our guess is nearly right: we're only off by the constant 1, a lower-order term. Nevertheless, mathematical induction doesn't work unless we prove the exact form of the inductive hypothesis. We overcome our difficulty by <I>subtracting</I> a lower-order term from our previous guess. Our new guess is <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I> - <I>b</I>, where <I>b</I> <img src="../images/gteq.gif"> 0 is constant. We now have<P>
<pre><I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> (<I>c</I><img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif"> - <I>b</I>) + (<I>c</I><img src="../images/hfbrul14.gif"><I>n</I>/2<img src="../images/hfbrur14.gif"> - <I>b</I>) + 1</sub></sup></pre><P>
<pre>= <I>cn</I> - 2<I>b</I> + 1</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> <I>cn</I> - <I>b </I>,</sub></sup></pre><P>
as long as <I>b</I> <img src="../images/gteq.gif"> 1. As before, the constant <I>c</I> must be chosen large enough to handle the boundary conditions.<P>
Most people find the idea of subtracting a lower-order term counterintuitive. After all, if the math doesn't work out, shouldn't we be increasing our guess? The key to understanding this step is to remember that we are using mathematical induction: we can prove something stronger for a given value by assuming something stronger for smaller values.<P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -