chap04.htm

介绍算法的书籍

<img src="71_a.gif"><P>
In general,<P>
<img src="71_b.gif"><P>
and thus, when <I>i</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>log<I><SUB>b</SUB> n</I><img src="../images/hfbrdr12.gif"><I>, we obtain </I>n<SUB>i<I></SUB> <img src="../images/lteq12.gif"> </I>b<I> + </I>b <I>/ (</I>b<I> - 1) = </I>O<I>(1).</I><P>
We can now iterate recurrence (4.10), obtaining<P>
<img src="71_c.gif"><P>
<h4><a name="0725_0005">(4.13)<a name="0725_0005"></sub></sup></h4><P>
which is much the same as equation (4.6), except that <I>n</I> is an arbitrary integer and not restricted to be an exact power of <I>b</I>.<P>
We can now evaluate the summation<P>
<img src="71_d.gif"><P>
<h4><a name="0725_0006">(4.14)<a name="0725_0006"></sub></sup></h4><P>
from (4.13) in a manner analogous to the proof of Lemma 4.3. Beginning with case 3, if <I>af</I><FONT FACE="Times New Roman" SIZE=3>(<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 FACE="Times New Roman" SIZE=3>) <img src="../images/lteq12.gif"> <I>cf</I>(<I>n</I>) for <I>n</I> &gt; <I>b</I> + <I>b</I>/(<I>b</I> - 1), where <I>c</I> &lt; 1 is a constant, then it follows that <I>a<SUP>j</I> </SUP><I>f</I></FONT>(<I>n<SUB>j</I></FONT></SUB>) <img src="../images/lteq12.gif"> <I>c<SUP>j</SUP>f</I></FONT>(<I>n</I>). Therefore, the sum in equation (4.14) can be evaluated just as in Lemma 4.3. For case 2, we have <I>f</I>(<I>n</I>) = <img src="../images/bound.gif"><FONT FACE="Times New Roman" SIZE=3>(<I>n</I><SUP>log<I>ba</I></SUP><FONT FACE="Times New Roman" SIZE=3>)</FONT>. If we can show that <I>f</I>(<I>n<SUB>j</I></FONT></SUB>) = <I>O</I><FONT FACE="Times New Roman" SIZE=3>(<I>n<SUP>log</SUP><SUB>b</SUB><SUP>a</SUP>/a<SUP>j</I><FONT FACE="Times New Roman" SIZE=3>) </FONT></SUP>= <I>O</I>((<I>n</I>/<I>b<SUP>j</I></FONT></SUP>)<SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP>), then the proof for case 2 of Lemma 4.3 will go through. Observe that <I>j </I><img src="../images/lteq12.gif"> <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>log<I><SUB>b</SUB>n</I><img src="../images/hfbrdr12.gif"> <I>implies </I>b<SUP>j<I></SUP>/</I>n<I> <img src="../images/lteq12.gif"></I> 1. The bound <I>f</I>(<I>n</I>) = <I>O</I><FONT FACE="Times New Roman" SIZE=3>(<I>n</I><SUP>log</SUP><I><SUB>b</SUB><SUP>a</I></SUP><FONT FACE="Times New Roman" SIZE=3>) </FONT>implies that there exists a constant <I>c</I> &gt; 0 such that for sufficiently large <I>n<SUB>j</I></FONT></SUB>,<P>
<img src="71_e.gif"><P>
since <I>c</I>(1 + <I>b</I>/(<I>b</I> - 1))<SUP>log<I>ba </I></SUP>is a constant. Thus, case 2 is proved. The proof of case 1 is almost identical. The key is to prove the bound <I>f</I>(<I>n<SUB>j</I></SUB>) = <I>O</I><FONT FACE="Times New Roman" SIZE=3>(<I>n</I><SUP>log</SUP><I><SUB>b</I></SUB><SUP>a</SUP>-<SUP><img src="../images/memof12.gif"></SUP><FONT FACE="Times New Roman" SIZE=3>)</FONT>, which is similar to the corresponding proof of case 2, though the algebra is more intricate.</FONT><P>
We have now proved the upper bounds in the master theorem for all integers <I>n</I>. The proof of the lower bounds is similar.<P>
<P>







<h2><a name="0726_0001">Exercises<a name="0726_0001"></h2><P>
<a name="0726_0002">4.4-1<a name="0726_0002"><P>
Give a simple and exact expression for <I>n<SUB>i</I></SUB> in equation (4.12) for the case in which <I>b</I> is a positive integer instead of an arbitrary real number.<P>
<a name="0726_0003">4.4-2<a name="0726_0003"><P>
Show that if <I>f</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><I><SUB>b</I></SUB><SUP>a </SUP>1g<I><SUP>k</I></SUP> <I>n</I>), <I>where k</I> <img src="../images/gteq.gif"> 0, then the master recurrence has solution <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n<SUP>log</SUP><SUB>b</SUB><SUP>a </I></SUP>1g<I><SUP>k</I>+1 </SUP><I>n</I>). For simplicity, confine your analysis to exact powers of <I>b</I>.<P>
<a name="0726_0004">4.4-3<a name="0726_0004"><P>
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition <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 implies that there exists a constant <img src="../images/memof12.gif"> &gt; 0 such that <I>f</I>(<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"><SUP>)</sup>.<P>
<P>


<P>







<h1><a name="0727_11e3">Problems<a name="0727_11e3"></h1><P>
<a name="0727_11e4">4-1     Recurrence examples<a name="0727_11e4"><P>
Give asymptotic upper and lower bounds for <I>T</I>(<I>n</I>) in each of the following recurrences. Assume that <I>T</I>(<I>n</I>) is constant for <I>n </I><img src="../images/lteq12.gif"> 2. Make your bounds as tight as possible, and justify your answers.<P>
<I><B>a</I>.</B>     <I>T</I>(<I>n</I>) = 2<I>T </I><img src="../images/lteq12.gif"> (<I>n</I>/2) + <I>n</I><SUP>3</SUP>.<P>
<I><B>b</I>.</B>     <I>T</I>(<I>n</I>) = <I>T</I>(9<I>n</I>/10) + <I>n</I>.<P>
<I><B>c</I>.</B>     <I>T</I>(<I>n</I>) = 16<I>T</I>(<I>n</I>/4) + <I>n</I><SUP>2</SUP>.<P>
<I><B>d</I>.</B>     <I>T</I>(<I>n</I>) = 7<I>T</I>(<I>n</I>/3) + <I>n</I><SUP>2</SUP>.<P>
<I><B>e</I>.</B>     <I>T</I>(<I>n</I>) = 7<I>T</I>(<I>n</I>/2) + <I>n</I><SUP>2</SUP>.<P>
<img src="72_a.gif"><P>
<I><B>g</I>.</B>     <I>T</I>(<I>n</I>) = <I>T</I>(<I>n</I> - 1) + <I>n</I>.<P>
<img src="72_b.gif"><P>
<a name="0727_11e5">4-2     Finding the missing integer<a name="0727_11e5"><P>
An array <I>A</I>[1 . . <I>n</I>] contains all the integers from 0 to <I>n</I> except one. It would be easy to determine the missing integer in <I>O</I>(<I>n</I>) time by using an auxiliary array <I>B</I>[0 . . <I>n</I>] to record which numbers appear in <I>A</I>. In this problem, however, we cannot access an entire integer in <I>A</I> with a single operation. The elements of <I>A</I> are represented in binary, and the only operation we can use to access them is "fetch the <I>j</I>th bit of <I>A</I>[<I>i</I>]," which takes constant time.<P>
Show that if we use only this operation, we can still determine the missing integer in <I>O</I>(<I>n</I>) time.<P>
<a name="0727_11e6">4-3     Parameter-passing costs<a name="0727_11e6"><P>
<a name="0727_11d9">Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an <I>N</I>-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself. This problem examines the implications of three parameter-passing strategies:<P>
1.     An array is passed by pointer. Time = <img src="../images/bound.gif"> (1).<P>
2.     An array is passed by copying. Time = <img src="../images/bound.gif"> (<I>N</I>), where <I>N</I> is the size of the array.<P>
3.     An array is passed by copying only the subrange that might be accessed by the called procedure. Time = <img src="../images/bound.gif"> <B>(<I>p - q</I> + 1 ) </B>if the subarray <I>A</I>[<I>p . . q</I>] is passed.<P>
<I><B>a.</I></B>     Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 1.3-5). Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let <I>N</I> be the size of the original problem and <I>n</I> be the size of a subproblem.<P>
<I><B>b.</I></B>     Redo part (a) for the <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> algorithm from Section 1.3.1.<P>
<a name="0727_11e7">4-4     More recurrence examples<a name="0727_11e7"><P>
Give asymptotic upper and lower bounds for <I>T</I>(<I>n</I>) in each of the following recurrences. Assume that <I>T</I>(<I>n</I>) is constant for <I>n</I> <img src="../images/lteq12.gif"> 2. Make your bounds as tight as possible, and justify your answers.<P>
<I><B>a.</I></B>     <I>T</I>(<I>n</I>) = 3<I>T</I>(<I>n</I>/2) + <I>n </I>1g <I>n</I>.<P>
<I><B>b.</I></B>     <I>T</I>(<I>n</I>) = 3<I>T</I>(<I>n</I>/3 + 5) + <I>n </I>/ 2.<P>
<I><B>c.</I></B>     <I>T</I>(<I>n</I>) = 2<I>T</I>(<I>n</I>/2) + <I>n </I>/ lg <I>n</I>.<P>
<I><B>d</I></B><I>.</I>     <I>T</I>(<I>n</I>) = <I>T</I>(<I>n</I> - 1) + 1 / <I>n</I>.<P>
<I><B>e</I></B><I>.</I>     <I>T</I>(<I>n</I>) = <I>T</I>(<I>n</I> - 1) + 1g <I>n</I>.<P>
<img src="74_a.gif"><P>
<a name="0727_11e8">4-5     Sloppiness conditions<a name="0727_11e8"><P>
<a name="0727_11da"><a name="0727_11db">Often, we are able to bound a recurrence <I>T</I>(<I>n</I>) at exact powers of an integral constant <I>b</I>. This problem gives sufficient conditions for us to extend the bound to all real <I>n</I> &gt; 0.<P>
<I><B>a</I></B><I>.</I>     Let <I>T</I>(<I>n</I>) and <I>h</I>(<I>n</I>) be monotonically increasing functions, and suppose that <I>T</I>(<I>n</I>) &lt; <I>h</I>(<I>n</I>) when <I>n</I> is an exact power of a constant <I>b</I> &gt; 1. Moreover, suppose that <I>h</I>(<I>n</I>) is "slowly growing" in the sense that <I>h</I>(<I>n</I>) = <I>O</I>(<I>h</I>(<I>n</I>/<I>b</I>)). Prove that <I>T</I>(<I>n</I>) = <I>O</I>(<I>h</I>(<I>n</I>)).<P>
<I><B>b.</I></B>     Suppose that we have the recurrence <I>T</I>(<I>n</I>) = <I>aT</I>(<I>n</I>/<I>b</I>) + <I>f</I>(<I>n</I>), where <I>a </I><img src="../images/gteq.gif"> 1, <I>b</I> &gt; 1, and <I>f</I>(<I>n</I>) is monotonically increasing. Suppose further that  the initial conditions for the recurrence are given by <I>T</I>(<I>n</I>) = <I>g</I>(<I>n</I>) for <I>n</I> <img src="../images/lteq12.gif"> <I>n</I><SUB>0</SUB>, where <I>g</I>(<I>n</I>) is monotonically increasing and <I>g</I>(<I>n</I><SUB>0</SUB>) &lt; <I>aT</I>(<I>n</I><SUB>0</SUB>/<I>b</I>)+ <I>f</I>(<I>n</I><SUB>0</SUB>). Prove that <I>T</I>(<I>n</I>) is monotonically increasing.<P>
<I><B>c</I></B><I>.</I>     Simplify the proof of the master theorem for the case in which <I>f</I>(<I>n</I>) is monotonically increasing and slowly growing. Use Lemma 4.4.<P>
<a name="0727_11e9">4-6     Fibonacci numbers<a name="0727_11e9"><P>
<a name="0727_11dc"><a name="0727_11dd"><a name="0727_11de"><a name="0727_11df"><a name="0727_11e0"><a name="0727_11e1">This problem develops properties of the Fibonacci numbers, which are defined by recurrence (2.13). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the <I><B>generating function</I> </B>(or <I><B>formal power series</I></B>) <img src="74_b.gif"> as<P>
<img src="74_c.gif"><P>
<I><B>a.</I></B>     Show that <img src="74_d.gif"><P>
<I><B>b.</I></B>     Show that<P>
<img src="74_e.gif"><P>
where<P>
<img src="74_f.gif"><P>
and<P>
<img src="75_a.gif"><P>
<I><B>c.</I></B>     Show that<P>
<img src="75_b.gif"><P>
<I><B>d.     </I></B>Prove that <img src="75_c.gif">, rounded to the nearest integer. <I>Hint</I>: <img src="75_d.gif">)<P>
<I><B>e.</I></B>     Prove that <I>F<SUB>i</I> + 2</SUB> <img src="../images/gteq.gif"> <img src="../images/phicap12.gif"><SUP>i<I></SUP> for </I>i<I> <img src="../images/gteq.gif"> 0.</I><P>
<a name="0727_11ea">4-7     VLSI chip testing<a name="0727_11ea"><P>
Professor Diogenes has <I>n</I> supposedly identical VLSI<SUP>1 </SUP>chips that in principle are capable of testing each other. The professor's test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. Thus, the four possible outcomes of a test are as follows:<P>
<pre>Chip <B><I>A <