chap04.htm

介绍算法的书籍

<img src="66_a.gif"><P>
thus,<P>
<img src="66_b.gif"><P>
which completes the proof.      <P>





<h3>The recursion tree</h3><P>
Before proceeding, let's try to develop some intuition by using a recursion tree. Figure 4.3 shows the tree corresponding to the iteration of the recurrence in Lemma 4.2. The root of the tree has cost &acirc;(<I>n</I>), and it has <I>a</I> children, each with cost &acirc;(<I>n/b</I>). (It is convenient to think of <I>a </I>as being an integer, especially when visualizing the recursion tree, but the mathematics does not require it.) Each of these children has <I>a</I> children with cost &acirc;(<I>n/b</I><SUP>2</SUP>), and thus there are <I>a</I><SUP>2</SUP> nodes that are distance 2 from the root. In general, there are <I>a</I><SUP>2</SUP> nodes that are distance <I>j</I> from the root, and each has cost &acirc;(<I>n/b<SUP>j</I></SUP>). The cost of each leaf is <I>T</I>(1) = <img src="../images/bound.gif">(1), and each leaf is distance <I>log<SUB>b</SUB>n</I> from the root, since <I>n/b</I><SUP>log</SUP><I><SUB>b</SUB><SUP>n</I></SUP> = 1. There are <I>a</I><SUP>log</SUP><I><SUB>b</SUB><SUP>n</SUP> </I>= <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</SUP> </I>leaves in the tree. <P>
We can obtain equation (4.6) by summing the costs of each level of the tree, as shown in the figure. The cost for a level <I>j</I> of internal nodes is <I>a<SUP>j</I></SUP>&acirc;(<I>n/b<SUP>j</I></SUP>), and so the total of all internal node levels is<P>
<img src="66_c.gif"><P>
In the underlying divide-and-conquer algorithm, this sum represents the costs of dividing problems into subproblems and then recombining the subproblems. The cost of all the leaves, which is the cost of doing all <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> subproblems of size 1, is <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>).<P>
<a name="0724_11d8">In terms of the recursion tree, the three cases of the master theorem correspond to cases in which the total cost of the tree is (1) dominated by the costs in the leaves, (2) evenly distributed across the levels of the tree, or (3) dominated by the cost of the root.<P>
The summation in equation (4.6) describes the cost of the dividing and combining steps in the underlying divide-and-conquer algorithm. The next lemma provides asymptotic bounds on the summation's growth.<P>
<img src="67_a.gif"><P>
<h4><a name="0724_11d9">Figure 4.3 The recursion tree generated by T(n) = aT(n/b)+ f(n). The tree is a complete a-ary tree with n<SUP>log</SUP><SUB><FONT FACE="Times New Roman" SIZE=1>b</SUB><SUP>a</SUP><FONT FACE="Times New Roman" SIZE=2> leaves and height log<SUB>b</SUB><FONT FACE="Times New Roman" SIZE=2> a. The cost of each level is shown at the right, and their sum is given in equation (4.6).<a name="0724_11d9"></FONT></FONT></FONT></sub></sup></h4><P>
<a name="0724_11da">Lemma 4.3<a name="0724_11da"><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>. A function <I>g(n)</I> defined over exact powers of <I>b</I> by<P>
<img src="67_b.gif"><P>
<h4><a name="0724_11db">(4.7)<a name="0724_11db"></sub></sup></h4><P>
can then be bounded asymptotically for exact powers of <I>b</I> 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"><I></I>) for some constant <img src="../images/memof12.gif"> &gt; 0, then <I>g(n)</I> = <I>O</I>(<I>n</I><SUP><FONT FACE="Courier New" SIZE=2>log</SUP><I><SUB>b</SUB><SUP>a</I></FONT></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><SUB>), </SUB>then <I>g</I>(<I>n</I>)<I> </I>= <img src="../images/bound.gif"><SUB>(</SUB><I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP><SUB> </SUB>1g <I>n</I><SUB>).<P>
3.     If <I>a</I>&acirc;(<I>n/b</I>) <img src="../images/lteq12.gif"> c&acirc;(<I>n</I>) for some constant <I>c</I> &lt; 1 and all <I>n</I> <img src="../images/gteq.gif"> <I>b</I>, then <I>g</I>(<I>n</I>) = <img src="../images/bound.gif">(&acirc;(<I>n</I>)).<P>
<I><B>Proof     </I></B>For case 1, we have &acirc;(<I>n</I>) = <I>O</I>(<I>n</I><SUP>log</SUP><I>b<SUP>a</I>-</SUP><img src="../images/memof12.gif">), implying that &acirc;(<I>n/b<SUP><FONT FACE="Courier New" SIZE=2>j</I></FONT></SUP>) = <I>O</I>((<I>n/b<SUP><FONT FACE="Courier New" SIZE=2>j</I></FONT></SUP>)<SUP><FONT FACE="Courier New" SIZE=2>log</SUP><I><SUB>b</SUB><SUP>a</I>-</SUP><img src="../images/memof12.gif"></FONT>). Substituting into equation (4.7) yields<P>
<img src="67_c.gif"><P>
<h4><a name="0724_11dc">(4.8)<a name="0724_11dc"></sub></sup></h4><P>
We bound the summation within the <I>O</I>-notation by factoring out terms and simplifying, which leaves an increasing geometric series:<P>
<img src="68_a.gif"><P>
Since <I>b</I> and <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"> </FONT>are constants, the last expression reduces to <I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I><FONT FACE="Times New Roman" SIZE=1>-</SUP><img src="../images/memof12.gif"><SUP><I>O</I></FONT>(<I>n</I></SUP><FONT FACE="Courier New" SIZE=2><SUP><img src="../images/memof12.gif"></FONT></SUP>) = <I>O</I>(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>). Substituting this expression for the summation in equation (4.8) yields<P>
<pre><I>g</I>(<I>n</I>) = <I>O</I>(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>),</sub></sup></pre><P>
and case 1 is proved.<P>
Under the assumption that &acirc;(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I>)<I> </I></SUP>for case 2, we have that &acirc;(<I>n/b<SUP>j</I></SUP>) = <img src="../images/bound.gif">((<I>n/b<SUP>j</I></SUP>)<SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>). Substituting into equation (4.7) yields<P>
<img src="68_b.gif"><P>
<h4><a name="0724_11dd">(4.9)<a name="0724_11dd"></sub></sup></h4><P>
We bound the summation within the <img src="../images/bound.gif"><B> </B>as in case 1, but this time we do not obtain a geometric series. Instead, we discover that every term of the summation is the same:<P>
<img src="68_c.gif"><P>
Substituting this expression for the summation in equation (4.9) yields<P>
<pre><I>g</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>log<I><SUB>b</SUB>n</I>)</sub></sup></pre><P>
<pre>= <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> 1g <I>n</I>),</sub></sup></pre><P>
and case 2 is proved.<P>
Case 3 is proved similarly. Since <img src="../images/scrptf12.gif">(<I>n</I>) appears in the definition (4.7) of <I>g(n)</I> and all terms of <I>g(n)</I> are nonnegative, we can conclude that <I>g(n) </I>= <img src="../images/omega12.gif">(<img src="../images/scrptf12.gif">(<I>n</I>)) for exact powers of <I>b</I>. Under the assumption that <I>af </I>(<I>n/b</I>) <img src="../images/lteq12.gif"> <I>cf</I>(<I>n</I>) for some constant <I>c</I> &lt; 1 and all <I>n</I> <img src="../images/gteq.gif"> <I>b</I>, we have <I>a<SUP>j</I></SUP><img src="../images/scrptf12.gif">(<I>n/b<SUP>j</I></SUP>)<SUP> </SUP><img src="../images/lteq12.gif"> <I>c<SUP>j</I></SUP> <img src="../images/scrptf12.gif">(<I>n</I>). Substituting into equation (4.7) and simplifying yields a geometric series, but unlike the series in case 1, this one has decreasing terms:<P>
<img src="69_a.gif"><P>
since <I>c</I> is constant. Thus, we can conclude that <I>g</I>(<I>n)</I> = <img src="../images/bound.gif">(<img src="../images/scrptf12.gif">(<I>n</I>)) for exact powers of <I>b.</I> Case 3 is proved, which completes the proof of the lemma.      <P>
We can now 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="0724_11de">Lemma 4.4<a name="0724_11de"><P>
Let <I>a</I> <img src="../images/gteq.gif"> 1 and <I>b</I> &gt; 1 be constants, and let <img src="../images/scrptf12.gif">(<I>n</I>) be a nonnegative function defined on exact powers of <I>b</I>. Define <I>T</I>(<I>n</I>) on exact powers of <I>b</I> by the recurrence<P>
<img src="69_b.gif"><P>
where <I>i</I> is a positive integer. Then <I>T</I>(<I>n</I>) can be bounded asymptotically for exact powers of <I>b</I> as follows.<P>
1.     If<I> </I><img src="../images/scrptf12.gif">(<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">) 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>).<P>
2.     If <img src="../images/scrptf12.gif">(<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 <img src="../images/scrptf12.gif">(<I>n</I>) = <img src="../images/omega12.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a+</I></SUP><img src="../images/memof12.gif">) for some constant <img src="../images/memof12.gif"> &gt; 0, and if <I>a</I><img src="../images/scrptf12.gif">(<I>n/b</I>) <img src="../images/lteq12.gif"> <I>c</I><img src="../images/scrptf12.gif">(<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">(<img src="../images/scrptf12.gif">(<I>n</I>)).<P>
<I><B>Proof     </I></B>We use the bounds in Lemma 4.3 to evaluate the summation (4.6) from Lemma 4.2. For case 1, we have<P>
<pre><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>) + <I>O</I>(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>)</sub></sup></pre><P>
<pre>= <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>),</sub></sup></pre><P>
and for case 2,<P>
<pre><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>) + <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP> 1g <I>n</I>)</sub></sup></pre><P>
<pre>= <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a </I>lg<I> n</I></SUP>).</sub></sup></pre><P>
For case 3, the condition <I>a</I><img src="../images/scrptf12.gif">(<I>n/b</I>) <img src="../images/lteq12.gif"> <I>c</I><img src="../images/scrptf12.gif">(<I>n</I>) implies <img src="../images/scrptf12.gif">(<I>n</I>) = <img src="../images/omega12.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a+</I></SUP><img src="../images/memof12.gif">) (see Exercise 4.4-3). Consequently,<P>
<pre><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>) + <img src="../images/bound.gif">(<img src="../images/scrptf12.gif">(<I>n</I>))</sub></sup></pre><P>
<pre>= <img src="../images/bound.gif">(<img src="../images/scrptf12.gif">(<I>n</I>)).      </sub></sup></pre><P>
<P>


<P>







<h2><a name="0725_0001">4.4.2 Floors and ceilings<a name="0725_0001"></h2><P>
To complete the proof of the master theorem, we must now extend our analysis to the situation in which floors and ceilings are used in the master recurrence, so that the recurrence is defined for all integers, not just exact powers of <I>b.</I> Obtaining a lower bound on<P>
<pre><I>T</I>(<I>n</I>) = <I>aT</I>(<img src="../images/hfbrul14.gif"><I>n/b</I><img src="../images/hfbrur14.gif">) + <img src="../images/scrptf12.gif">(<I>n</I>)</sub></sup></pre><P>
<h4><a name="0725_0002">(4.10)<a name="0725_0002"></sub></sup></h4><P>
and an upper bound on<P>
<pre>T(n) = aT(<img src="../images/hfbrdl12.gif">n/b<img src="../images/hfbrdr12.gif">) + <img src="../images/scrptf12.gif">(n)</sub></sup></pre><P>
<h4><a name="0725_0003">(4.11)<a name="0725_0003"></sub></sup></h4><P>
is routine, since the bound <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"><I>n/b</I><img src="../images/hfbrur14.gif"></FONT> <img src="../images/gteq.gif"> <I>n/b</I> can be pushed through in the first case to yield the desired result, and the bound<FONT FACE="Courier New" SIZE=2> <img src="../images/hfbrdl12.gif"><I>n/b</I><img src="../images/hfbrdr12.gif"></FONT> <img src="../images/lteq12.gif"> <I>n/b </I>can be pushed through in the second case. Lower bounding the recurrence (4.11) requires much the same technique as upper bounding the recurrence (4.10), so we shall only present this latter bound. <P>
We wish to iterate the recurrence (4.10), as was done in Lemma 4.2. As we iterate the recurrence, we obtain a sequence of recursive invocations on the arguments<P>
<pre><I>n</I>,</sub></sup></pre><P>
<pre><img src="../images/hfbrul14.gif"><I>n</I>/<I>b</I><img src="../images/hfbrur14.gif"> ,</sub></sup></pre><P>
<pre><img src="../images/hfbrul14.gif"><img src="../images/hfbrul14.gif"><I>n</I>/<I>b</I><img src="../images/hfbrur14.gif">/<I>b</I><img src="../images/hfbrur14.gif"> ,</sub></sup></pre><P>
<pre><img src="../images/hfbrul14.gif"><img src="../images/hfbrul14.gif"><img src="../images/hfbrul14.gif"><I>n</I>/<I>b</I><img src="../images/hfbrur14.gif">/<I>b</I><img src="../images/hfbrur14.gif">/<I>b</I><img src="../images/hfbrur14.gif"> ,</sub></sup></pre><P>
<img src="70_a.gif"><P>
Let us denote the <I>i</I>th element in the sequence by <I>n<SUB>i</I></SUB>, where<P>
<img src="70_b.gif"><P>
<h4><a name="0725_0004">(4.12)<a name="0725_0004"></sub></sup></h4><P>
Our first goal is to determine the number of iterations <I>k</I> such that <I>n<SUB>k</I></SUB> is a constant. Using the inequality<FONT FACE="Courier New" SIZE=2> <img src="../images/hfbrul14.gif"><I>x</I><img src="../images/hfbrur14.gif"></FONT> <img src="../images/lteq12.gif"> <I>x</I> + 1, we obtain<P>
<img src="70_c.gif"><P>