chap04.htm

介绍算法的书籍

<a name="071f_11d7">Theorem 4.1<a name="071f_11d7"><P>
Let <I>a</I> <img src="../images/gteq.gif"> 1 and <I>b</I> &gt; 1 be constants, let &acirc;(<I>n</I>) be a function, and let <I>T</I>(<I>n</I>) be defined on the nonnegative integers by the recurrence<P>
<pre><I>T</I>(<I>n</I>) = <I>aT</I>(<I>n</I>/<I>b</I>) + &acirc;(<I>n</I>),</sub></sup></pre><P>
where we interpret <I>n</I>/<I>b</I> to mean either <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/<I>b<FONT FACE="Courier New" SIZE=2></I><img src="../images/hfbrdr12.gif"><I></I></FONT> or <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/<I>b</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"></FONT>. Then <I>T</I>(<I>n</I>) can be bounded asymptotically as follows.<P>
1.     If &acirc;(<I>n</I>) = <I>O</I>(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I>-</SUP><img src="../images/memof12.gif"><SUP>) for some constant <img src="../images/memof12.gif"> &gt; 0, then <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I></SUP><FONT FACE="Courier New" SIZE=2>log<SUP><I><SUB>b</SUB></SUP>a</I></FONT><SUP>).</sup><P>
2.     If &acirc;(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>), then <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>lg <I>n</I>).<P>
3.     If &acirc;(<I>n</I>) = <img src="../images/omega12.gif">(<I>n</I>log<SUP><I><SUB>b</SUB></SUP>a</I>+<SUP><img src="../images/memof12.gif"></SUP>) for some constant <img src="../images/memof12.gif"> &gt; 0, and if <I>a</I>&acirc;(<I>n</I>/<I>b</I>) <img src="../images/lteq12.gif"> <I>c</I>&acirc;(<I>n</I>) for some constant <I>c</I> &lt; 1 and all sufficiently large <I>n</I>, then <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(&acirc;(<I>n</I>)).      <P>
Before applying the master theorem to some examples, let's spend a moment trying to understand what it says. In each of the three cases, we are comparing the function &acirc;(<I>n</I>) with the function <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a.</I></SUP> Intuitively, the solution to the recurrence is determined by the larger of the two functions. If, as in case 1, the function <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> is the<I> </I>larger, then the solution is <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(&acirc;(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>). If, as in case 3, the function &acirc;(<I>n</I>) is the larger, then the solution is <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(&acirc;(<I>n</I>)). If, as in case 2, the two functions are the same size, we multiply by a logarithmic factor, and the solution is <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a </I></SUP>lg <I>n</I>) = <img src="../images/bound.gif">(&acirc;(<I>n</I>)lg <I>n</I>).<P>
Beyond this intuition, there are some technicalities that must be understood. In the first case, not only must &acirc;(<I>n</I>) be smaller than <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</SUP><FONT FACE="Times New Roman" SIZE=2>,</I> </FONT>it must be <I>polynomially</I> smaller. That is, &acirc;(<I>n</I>) must be asymptotically smaller than <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> by a factor of <I>n</I><img src="../images/memof12.gif"> for some constant <img src="../images/memof12.gif"> &gt; 0. In the third case, not only must &acirc;(<I>n</I>) be larger than <I>n</I><SUP><FONT FACE="Courier New" SIZE=2>log</SUP><I><SUB>b</SUB><SUP>a</I></FONT></SUP>, it must be polynomially larger and in addition satisfy the "regularity" condition that <I>a</I>&acirc;(<I>n</I>/<I>b</I>) <img src="../images/lteq12.gif"> <I>c</I>&acirc;(<I>n</I>). This condition is satisfied by most of the polynomially bounded functions that we shall encounter.<P>
It is important to realize that the three cases do not cover all the possibilities for &acirc;(<I>n</I>). There is a gap between cases 1 and 2 when &acirc;(<I>n</I>) is smaller than <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> but not polynomially smaller. Similarly, there is a gap between cases 2 and 3 when &acirc;(<I>n</I>) is larger than <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a </I></SUP>but not polynomially larger. If the function &acirc;(<I>n</I>) falls into one of these gaps, or if the regularity condition in case 3 fails to hold, the master method cannot be used to solve the recurrence.<P>
<P>







<h2>Using the master method</h2><P>
To use the master method, we simply determine which case (if any) of the master theorem applies and write down the answer.<P>
As a first example, consider<P>
<pre><I>T</I>(<I>n</I>) = 9<I>T</I>(<I>n</I>/3) + <I>n</I>.</sub></sup></pre><P>
For this recurrence, we have <I>a</I> = 9, <I>b</I> = 3, &acirc;(<I>n</I>) = <I>n</I>, and thus <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> = <I>n</I><SUP>log</SUP><SUB><FONT FACE="Times New Roman" SIZE=1>3</SUB><SUP>9</FONT></SUP> = <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>). Since &acirc;(<I>n</I>) = <I>0</I>(<I>n</I><SUP>log</SUP><SUB><FONT FACE="Times New Roman" SIZE=1>3</SUB><SUP>9-</SUP><img src="../images/memof12.gif"></FONT><SUP>), </SUP>where <img src="../images/memof12.gif"> = 1, we can apply case 1 of the master theorem and conclude that the solution is <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP><FONT FACE="Courier New" SIZE=2>2</FONT></SUP>).<P>
Now consider<P>
<pre><I>T</I>(<I>n</I>) = <I>T</I>(2<I>n</I>/3) + 1,</sub></sup></pre><P>
in which <I>a</I> = 1, <I>b</I> = 3/2, &acirc;(<I>n</I>) = 1, and <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> = <I>n</I><SUP>log</SUP><SUB><FONT FACE="Times New Roman" SIZE=1>3/2</SUB><SUP>1</FONT></SUP> = n<SUP>0</SUP> = 1. Case 2 applies, since &acirc;(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>) = <img src="../images/bound.gif">(1), and thus the solution to the recurrence is <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(lg <I>n</I>).<P>
For the recurrence<P>
<pre><I>T</I>(<I>n</I>) = 3<I>T</I>(<I>n</I>/4) + <I>n </I>lg <I>n</I>,</sub></sup></pre><P>
we have <I>a</I> = 3, <I>b</I> = 4, &acirc;(<I>n</I>) = <I>n </I>lg <I>n</I>, and <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> = <I>n</I><SUP>log</SUP><SUB><FONT FACE="Times New Roman" SIZE=1>4</SUB><SUP>3</FONT></SUP> = <I>0</I>(<I>n</I><SUP>0.793</SUP>). Since &acirc;(<I>n</I>) = <img src="../images/omega12.gif">(<I>n</I><SUP>log<FONT FACE="Times New Roman" SIZE=1></SUP><SUB>4</SUB><SUP>3+</SUP><img src="../images/memof12.gif"><SUP><FONT FACE="Times New Roman" SIZE=2></SUP>), </FONT></FONT>where <img src="../images/memof12.gif"> <img src="../images/approx18.gif"> 0.2, case 3 applies if we show that the regularity condition holds for &acirc;(<I>n</I>). For sufficiently large <I>n</I>, <I>a&acirc;</I>(<I>n</I>/<I>b</I>) = 3(<I>n</I>/4) lg(<I>n</I>/4) <img src="../images/lteq12.gif"> (3/4)<I>n</I> lg <I>n</I> = <I>c</I>&acirc;(<I>n</I>) for <I>c</I> = 3/4. Consequently, by case 3, the solution to the recurrence is <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n </I>lg <I>n</I>).<P>
The master method does not apply to the recurrence<P>
<pre><I>T</I>(<I>n</I>) = 2<I>T</I>(<I>n</I>/2) = + <I>n </I>1g <I>n</I>,</sub></sup></pre><P>
even though it has the proper form: <I>a</I> = 2, <I>b</I> = 2, &acirc;(<I>n</I>) = <I>n</I>1g <I>n</I>, and <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> = <I>n</I>. It seems that case 3 should apply, since &acirc;(<I>n</I>) = <I>n</I>1g <I>n</I> is asymptotically larger than <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> = <I>n</I> but not polynomially larger. The ratio &acirc;(<I>n</I>)/<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> = (<I>n </I>1g <I>n</I>)/<I>n</I> = 1g <I>n</I> is asymptotically less than <I>n</I><img src="../images/memof12.gif"><I></I> for any positive constant <img src="../images/memof12.gif">. Consequently, the recurrence falls into the gap between case 2 and case 3. (See Exercise 4.4-2 for a solution.)<P>
<P>







<h2><a name="0721_0001">Exercises<a name="0721_0001"></h2><P>
<a name="0721_0002">4.3-1<a name="0721_0002"><P>
Use the master method to give tight asymptotic bounds for the following recurrences.<P>
<I><B>a.</I>     </B><I>T</I>(<I>n</I>) = 4<I>T</I>(<I>n</I>/2) + <I>n</I>.<P>
<I><B>b.</I>     </B><I>T</I>(<I>n</I>) = 4<I>T</I>(<I>n</I>/2) + <I>n</I><SUP>2</SUP>.<P>
<I><B>c.</I>     </B><I>T</I>(<I>n</I>) = 4<I>T</I>(<I>n</I>/2) + <I>n</I><SUP>3</SUP>.<P>
<a name="0721_0003">4.3-2<a name="0721_0003"><P>
The running time of an algorithm <I>A</I> is described by the recurrence <I>T</I>(<I>n</I>) = 7<I>T</I>(<I>n</I>/2) + <I>n</I><SUP>2</SUP>. A competing algorithm <I>A</I>' has a running time of <I>T</I>'(<I>n</I>) = <I>aT</I>'<I>(</I>n<I>/4) + </I>n<I><SUP>2</SUP>. What is the largest integer value for </I>a<I> such that </I>A<I>' is asymptotically faster than </I>A<I>?</I><P>
<a name="0721_0004">4.3-3<a name="0721_0004"><P>
Use the master method to show that the solution to the recurrence <I>T</I>(<I>n</I>) = <I>T</I>(<I>n</I>/2) + <img src="../images/bound.gif">(1) of binary search (see Exercise 1.3-5) is <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(1g <I>n</I>).<P>
<a name="0721_0005">4.3-4<a name="0721_0005"><P>
Consider the regularity condition <I>a&acirc;</I>(<I>n</I>/<I>b</I>) <img src="../images/lteq12.gif"> <I>c</I>&acirc;(<I>n</I>) for some constant <I>c</I> &lt; 1, which is part of case 3 of the master theorem. Give an example of a simple function &acirc;(<I>n</I>) that satisfies all the conditions in case 3 of the master theorem except the regularity condition.<P>
<P>


<P>







<h1><a name="0722_11d8">* 4.4 Proof of the master theorem<a name="0722_11d8"></h1><P>
<a name="0722_11d7">This section contains a proof of the master theorem (Theorem 4.1) for more advanced readers. The proof need not be understood in order to apply the theorem.<P>
The proof is in two parts. The first part analyzes the &quot;master&quot; recurrence (4.5), under the simplifying assumption that <I>T</I>(<I>n</I>) is defined only on exact powers of <I>b</I> &gt; 1, that is, for <I>n</I> = 1, <I>b</I>, <I>b</I><SUP>2</SUP>, . . .. This part gives all the intuition needed to understand why the master theorem is true. The second part shows how the analysis can be extended to all positive integers <I>n </I>and is merely mathematical technique applied to the problem of handling floors and ceilings.<P>
In this section, we shall sometimes abuse our asymptotic notation slightly by using it to describe the behavior of functions that are only defined over exact powers of <I>b</I>. Recall that the definitions of asymptotic notations require that bounds be proved for all sufficiently large numbers, not just those that are powers of <I>b</I>. Since we could make new asymptotic notations that apply to the set {<I>b<SUP>i</SUP> : i </I>= 0,1, . . .}, instead of the nonnegative integers, this abuse is minor.<P>
Nevertheless, we must always be on guard when we are using asymptotic notation over a limited domain so that we do not draw improper conclusions. For example, proving that <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I>) when <I>n</I> is an exact power of 2 does not guarantee that <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I>). The function <I>T</I>(<I>n</I>) could be defined as<P>
<img src="65_a.gif"><P>
in which case the best upper bound that can be proved is <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I><SUP>2</SUP>). Because of this sort of drastic consequence, we shall never use asymptotic notation over a limited domain without making it absolutely clear from the context that we are doing so.<P>





<h2><a name="0723_0001">4.4.1 The proof for exact powers<a name="0723_0001"></h2><P>
The first part of the proof of the master theorem analyzes the master recurrence (4.5),<P>
<pre><I>T</I>(<I>n</I>) = <I>aT</I>(<I>n/b</I>) + <I>&acirc;</I>(<I>n</I>),</sub></sup></pre><P>
under the assumption that <I>n</I> is an exact power of <I>b</I> &gt; 1, where <I>b</I> need not be an integer. The analysis is broken into three lemmas. The first reduces the problem of solving the master recurrence to the problem of evaluating an expression that contains a summation. The second determines bounds on this summation. The third lemma puts the first two together to prove a version of the master theorem for the case in which <I>n</I> is an exact power of <I>b</I>.<P>
<a name="0723_0002">Lemma 4.2<a name="0723_0002"><P>
Let <I>a</I> <img src="../images/gteq.gif"> 1 and <I>b</I> &gt; 1 be constants, and let &acirc;(<I>n</I>) be a nonnegative function defined on exact powers of <I>b</I>. Define <I>T(n)</I> on exact powers of <I>b</I> by the recurrence<P>
<img src="65_b.gif"><P>
where <I>i</I> is a positive integer. Then<P>
<img src="65_c.gif"><P>
<h4><a name="0723_0003">(4.6)<a name="0723_0003"></sub></sup></h4><P>
<I><B>Proof     </I></B>Iterating the recurrence yields<P>
<pre><I>T</I>(<I>n</I>) = &acirc;(<I>n</I>) + <I>aT</I>(<I>n/b</I>)</sub></sup></pre><P>
<pre>= &acirc;(<I>n</I>) + <I>a</I>&acirc;(<I>n/b</I>) + <I>a</I><SUP>2</SUP><I>T</I>(<I>n/b</I><SUP>2</SUP>)</sub></sup></pre><P>
<pre>= &acirc;(<I>n</I>) + <I>a</I>&acirc;(<I>n/b</I>) + <I>a</I><SUP>2</SUP>&acirc;(<I>n/b</I><SUP>2</SUP>) + . . .</sub></sup></pre><P>
<pre>+ <I>a</I><SUP>log</SUP><I><SUB>b</SUB><SUP>n</I>-1 </SUP><I>f</I>(<I>n</I>/<I>b</I><SUP>log</SUP><I><SUB>b</SUB><SUP>n</I>-1</SUP>) + <I>a</I><SUP>log</SUP><I><SUB>b</SUB><SUP>n</SUP>T</I>(1) .</sub></sup></pre><P>
Since <I>a</I><SUP>log</SUP><I><SUB>b<FONT FACE="Times New Roman" SIZE=1> </SUB><SUP>n</SUP> </I></FONT>= <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>, the last term of this expression becomes<P>
<pre><I>a</I><SUP>log</SUP><I><SUB>b</SUB><SUP>n</I></SUP> <I>T</I>(1) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>);</sub></sup></pre><P>
using the boundary condition <I>T</I>(1) = <img src="../images/bound.gif">(1). The remaining terms can be expressed as the sum<P>