chap04.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h2>Avoiding pitfalls</h2><P>
It is easy to err in the use of asymptotic notation. For example, in the recurrence (4.4) we can falsely prove <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I>) by guessing <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn </I>and then arguing<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">) + <I>n</I></sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> <I>cn</I> + <I>n</I></sub></sup></pre><P>
<pre>= <I>O</I>(<I>n</I>),      <img src="../images/lftbigar.gif"> <I>wrong!!</I></sub></sup></pre><P>
since <I>c</I> is a constant. The error is that we haven't proved the exact form of the inductive hypothesis, that is, that <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I>.<P>
<P>







<h2>Changing variables</h2><P>
Sometimes, a little algebraic manipulation can make an unknown recurrence similar to one you have seen before. As an example, consider the recurrence<P>
<img src="57_a.gif"><P>
which looks difficult. We can simplify this recurrence, though, with a change of variables. For convenience, we shall not worry about rounding off values, such as <img src="57_b.gif">, to be integers. Renaming <I>m</I> = 1g <I>n </I>yields<P>
<pre><I>T</I>(2<I><SUP>m</I></SUP>) = 2<I>T</I>(2<I><SUP>m</I>/2</SUP>) + <I>m.</I></sub></sup></pre><P>
We can now rename <I>S</I>(<I>m</I>) = <I>T</I>(2<I><SUP>m</I></SUP>) to produce the new recurrence<P>
<pre><I>S</I>(<I><SUP>m</I></SUP>) = 2<I>S</I>(<I><SUP>m</I>/2</SUP>) + <I>m,</I></sub></sup></pre><P>
which is very much like recurrence (4.4) and has the same solution: <I>S</I>(<I>m</I>) = <I>O</I>(<I>m</I> lg <I>m</I>). Changing back from <I>S</I>(<I>m</I>) to <I>T</I>(<I>n</I>), we obtain <I>T</I>(<I>n</I>) = <I>T</I>(2<I><SUP>m</I></SUP>) = <I>S</I>(<I>m</I>) = <I>O</I>(<I>m</I> lg <I>m</I>) = <I>O</I>(lg <I>n</I> lg lg <I>n</I>).<P>
<P>







<h2><a name="071a_0001">Exercises<a name="071a_0001"></h2><P>
<a name="071a_0002">4.1-1<a name="071a_0002"><P>
Show that the solution of <I>T</I>(<I>n</I>) = <I>T</I>(<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"></FONT>) + 1 is <I>O</I>(lg <I>n</I>).<P>
<a name="071a_0003">4.1-2<a name="071a_0003"><P>
Show that the solution of<I> T</I>(<I>n</I>) = 2<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>) + <I>n</I> is <img src="../images/omega12.gif"><FONT FACE="Times New Roman" SIZE=4>(<I>n</I></FONT> lg <I>n</I>). Conclude that the solution is <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>).<P>
<a name="071a_0004">4.1-3<a name="071a_0004"><P>
Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition <I>T</I>(1) = 1 for the recurrence (4.4) without adjusting the boundary conditions for the inductive proof.<P>
<a name="071a_0005">4.1-4<a name="071a_0005"><P>
Show that <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>) is the solution to the &quot;exact&quot; recurrence (4.2) for merge sort.<P>
<a name="071a_0006">4.1-5<a name="071a_0006"><P>
Show that the solution to <I>T</I>(<I>n</I>) = 2<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) + <I>n</I> is <I>O</I>(<I>n</I> lg <I>n</I>).<P>
<a name="071a_0007">4.1-6<a name="071a_0007"><P>
Solve the recurrence <img src="58_a.gif"> by making a change of variables. Do not worry about whether values are integral.<P>
<P>


<P>







<h1><a name="071b_11d0">4.2 The iteration method<a name="071b_11d0"></h1><P>
<a name="071b_11ce"><a name="071b_11cf">The method of iterating a recurrence doesn't require us to guess the answer, but it may require more algebra than the substitution method. The idea is to expand (iterate) the recurrence and express it as a summation of terms dependent only on <I>n</I> and the initial conditions. Techniques for evaluating summations can then be used to provide bounds on the solution.<P>
As an example, consider the recurrence<P>
<pre><I>T</I>(<I>n</I>) = 3<I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/4<img src="../images/hfbrdr12.gif">) + <I>n</I>.</sub></sup></pre><P>
We iterate it as follows:<P>
<pre><I>T</I>(<I>n</I>) = <I>n</I> + 3<I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/4<img src="../images/hfbrdr12.gif">)</sub></sup></pre><P>
<pre>= <I>n</I> + 3 (<img src="../images/hfbrdl12.gif"><I>n</I>/4<img src="../images/hfbrdr12.gif"> + 3<I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/16<img src="../images/hfbrdr12.gif">))</sub></sup></pre><P>
<pre>= <I>n</I> + 3(<img src="../images/hfbrdl12.gif"><I>n</I>/4<img src="../images/hfbrdr12.gif"> + 3(<img src="../images/hfbrdl12.gif"><I>n</I>/16<img src="../images/hfbrdr12.gif"> + 3<I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/64<img src="../images/hfbrdr12.gif">)))</sub></sup></pre><P>
<pre>= <I>n</I> + 3 <img src="../images/hfbrdl12.gif"><I>n</I>/4<img src="../images/hfbrdr12.gif"> + 9 <img src="../images/hfbrdl12.gif"><I>n</I>/16<img src="../images/hfbrdr12.gif"> + 27<I>T</I>(<img src="../images/hfbrdl12.gif"><I>n</I>/64<img src="../images/hfbrdr12.gif">),</sub></sup></pre><P>
where <img src="../images/hfbrdl12.gif"><img src="../images/hfbrdl12.gif"><I>n</I>/4<img src="../images/hfbrdr12.gif">/4<img src="../images/hfbrdr12.gif"> = <img src="../images/hfbrdl12.gif"><I>n</I>/16<img src="../images/hfbrdr12.gif"> and <img src="../images/hfbrdl12.gif"><img src="../images/hfbrdl12.gif"><I>n</I>/16<img src="../images/hfbrdr12.gif">/4<img src="../images/hfbrdr12.gif"> = <img src="../images/hfbrdl12.gif"><I>n</I>/64<img src="../images/hfbrdr12.gif"> follow from the identity (2.4).<P>
How far must we iterate the recurrence before we reach a boundary condition? The <I>i</I>th term in the series is 3<I><SUP>i</I> </SUP><img src="../images/hfbrdl12.gif"><I>n</I>/4<I><SUP>i</I></SUP><img src="../images/hfbrdr12.gif">. The iteration hits <I>n</I> = 1 when <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/4<I><SUP>i</I></SUP><img src="../images/hfbrdr12.gif"> = 1 or, equivalently, when <I>i</I> exceeds log<SUB>4</SUB> <I>n</I>. By continuing the iteration until this point and using the bound <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/4<I><SUP>i</I></SUP><img src="../images/hfbrdr12.gif"> <img src="../images/lteq12.gif"> <I>n</I>/4<I><SUP>i</I></SUP>, we discover that the summation contains a decreasing geometric series:<P>
<img src="58_b.gif"><P>
Here, we have used the identity (2.9) to conclude that 3<SUP>log</SUP><SUB>4</SUB> <I><SUP>n</I></SUP> = <I>n</I><SUP>log</SUP><SUB>4</SUB><SUP>3</SUP>, and we have used the fact that log<SUB>4</SUB> 3 &lt; 1 to conclude that <img src="../images/bound.gif">(<I>n</I><SUP>log</SUP><SUB>4</SUB><SUP>3</SUP>) = <I>o</I>(<I>n</I>)<I>.</I><P>
The iteration method usually leads to lots of algebra, and keeping everything straight can be a challenge. The key is to focus on two parameters: the number of times the recurrence needs to be iterated to reach the boundary condition, and the sum of the terms arising from each level of the iteration process. Sometimes, in the process of iterating a recurrence, you can guess the solution without working out all the math. Then, the iteration can be abandoned in favor of the substitution method, which usually requires less algebra.<P>
When a recurrence contains floor and ceiling functions, the math can become especially complicated. Often, it helps to assume that the recurrence is defined only on exact powers of a number. In our example, if we had assumed that <I>n</I> = 4<I><SUP>k</I></SUP> for some integer <I>k</I>, the floor functions could have been conveniently omitted. Unfortunately, proving the bound <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I>) solely for exact powers of 4 is technically an abuse of the <I>O</I>-notation. The definitions of asymptotic notation require that bounds be proved for <I>all</I> sufficiently large integers, not just those that are powers of 4. We shall see in Section 4.3 that for a large class of recurrences, this technicality can be overcome. Problem 4-5 also gives conditions under which an analysis for exact powers of an integer can be extended to all integers.<P>
Recursion trees<P>
Exercises<P>
<P>







<h1><a name="071e_11d6">4.3 The master method<a name="071e_11d6"></h1><P>
<a name="071e_11d4"><a name="071e_11d5">The master method provides a &quot;cookbook&quot; method for solving recurrences of the form<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>
<h4><a name="071e_11d7">(4.5)<a name="071e_11d7"></sub></sup></h4><P>
where <I>a</I> <img src="../images/gteq.gif"> 1 and <I>b</I> &gt; 1 are constants and &acirc;(<I>n</I>) is an asymptotically positive function. The master method requires memorization of three cases, but then the solution of many recurrences can be determined quite easily, often without pencil and paper.<P>
The recurrence (4.5) describes the running time of an algorithm that divides a problem of size <I>n</I> into <I>a</I> subproblems, each of size <I>n</I>/<I>b</I>, where <I>a</I> and <I>b</I> are positive constants. The <I>a</I> subproblems are solved recursively, each in time <I>T</I>(<I>n</I>/<I>b</I>). The cost of dividing the problem and combining the results of the subproblems is described by the function &acirc;(<I>n</I>). (That is, using the notation from Section 1.3.2, &acirc;(<I>n</I>) = <I>D</I>(<I>n</I>) + <I>C</I>(<I>n</I>).) For example, the recurrence arising from the <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> procedure has <I>a</I> = 2, <I>b</I> = 2, and &acirc;(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I>).<P>
As a matter of technical correctness, the recurrence isn't actually well defined because <I>n</I>/<I>b</I> might not be an integer. Replacing each of the <I>a</I> terms <I>T</I>(<I>n</I>/<I>b</I>) with either <I>T</I>(<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"></FONT><I>) or </I>T<I>(<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"></I>n</FONT><I>/</I>b<FONT FACE="Courier New" SIZE=2><I><img src="../images/hfbrur14.gif"></I></FONT>) doesn't affect the asymptotic behavior of the recurrence, however. (We'll prove this in the next section.) We normally find it convenient, therefore, to omit the floor and ceiling functions when writing divide-and-conquer recurrences of this form.<P>





<h2>The master theorem</h2><P>
<a name="071f_11d6">The master method depends on the following theorem.<P>