chap03.htm

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

<P>







<h1><a name="070a_11cb">3.2 Bounding summations<a name="070a_11cb"></h1><P>
<a name="070a_11c9"><a name="070a_11ca">There are many techniques available for bounding the summations that describe the running times of algorithms. Here are some of the most frequently used methods.<P>





<h2>Mathematical induction</h2><P>
The most basic way to evaluate a series is to use mathematical induction. As an example, let us prove that the arithmetic series <img src="46_d.gif"> evaluates to 1/2<I>n</I>(<I>n</I> + 1). We can easily verify this for <I>n</I> = 1, so we make the inductive assumption that it holds for <I>n</I> and prove that it holds for <I>n</I> + 1. We have<P>
<img src="46_e.gif"><P>
One need not guess the exact value of a summation in order to use mathematical induction. Induction can be used to show a bound as well. As an example, let us prove that the geometric series <img src="46_f.gif"> is <I>0</I>(3<I><SUP>n</I></SUP>). More specifically, let us prove that <img src="46_g.gif"> for some constant <I>c</I>. For the initial condition <I>n</I> = 0, we have <img src="46_h.gif"> as long as <I>c</I> <img src="../images/gteq.gif"> 1. Assuming that the bound holds for <I>n</I>, let us prove that it holds for <I>n</I> + 1. We have<P>
<img src="46_i.gif"><P>
as long as (1/3 + 1/<I>c</I>) <img src="../images/lteq12.gif"> 1 or, equivalently, <I>c</I> <img src="../images/gteq.gif"> 3/2. Thus, <img src="47_a.gif">, as we wished to show.<P>
We have to be careful when we use asymptotic notation to prove bounds by induction. Consider the following fallacious proof that <img src="47_b.gif">. Certainly, <img src="47_c.gif">. Assuming the bound for <I>n</I>, we now prove it for <I>n</I>+1:<P>
<img src="47_d.gif"><P>
The bug in the argument is that the &quot;constant&quot; hidden by the &quot;big-oh<FONT FACE="CG Times (W1)" SIZE=2>&quot;</FONT> grows with <I>n</I> and thus is not constant. We have not shown that the same constant works for <I>all n.</I><P>
<P>







<h2>Bounding the terms</h2><P>
Sometimes, a good upper bound on a series can be obtained by bounding each term of the series, and it often suffices to use the largest term to bound the others. For example, a quick upper bound on the arithmetic series (3.1) is<P>
<img src="47_e.gif"><P>
In general, for a series <img src="47_f.gif">, then<P>
<img src="47_g.gif"><P>
The technique of bounding each term in a series by the largest term is a weak method when the series can in fact be bounded by a geometric series. Given the series <img src="47_h.gif"> suppose that <I>a<SUB>k</I>+1</SUB>/<I>a<SUB>k</I></SUB> <img src="../images/lteq12.gif"> <I>r</I> for all <I>k</I> <img src="../images/gteq.gif"> 0, where <I>r</I> &lt; 1 is a constant. The sum can be bounded by an infinite decreasing geometric series, since <I>a<SUB>k</I></SUB> <img src="../images/lteq12.gif"> <I>a</I><SUB>0</SUB><I>r<SUP>k</I></SUP>, and thus<P>
<img src="47_i.gif"><P>
We can apply this method to bound the summation <img src="48_a.gif">. The first term is 1/3, and the ratio of consecutive terms is<P>
<img src="48_b.gif"><P>
for all <I>k</I> <img src="../images/gteq.gif">1. Thus, each term is bounded above by (1/3)(2/3)<I><SUP>k</I></SUP>, so that<P>
<img src="48_c.gif"><P>
A common bug in applying this method is to show that the ratio of consecutive terms is less than 1 and then to assume that the summation is bounded by a geometric series. An example is the infinite harmonic series, which diverges since<P>
<img src="48_d.gif"><P>
The ratio of the (<I>k</I> + 1)st and <I>k</I>th terms in this series is <I>k</I>/(<I>k</I> + 1) &lt; 1, but the series is not bounded by a decreasing geometric series. To bound a series by a geometric series, one must show that the ratio is bounded away from 1; that is, there must be an <I>r</I> &lt; 1, which is a <I>constant</I>, such that the ratio of all pairs of consecutive terms never exceeds <I>r</I>. In the harmonic series, no such <I>r</I> exists because the ratio becomes arbitrarily close to 1.<P>
<P>







<h2>Splitting summations</h2><P>
One way to obtain bounds on a difficult summation is to express the series as the sum of two or more series by partitioning the range of the index and then to bound each of the resulting series. For example, suppose we try to find a lower bound on the arithmetic series <img src="48_e.gif">, which has already been shown to have an upper bound of <I>n</I><SUP>2</SUP>. We might attempt to bound each term in the summation by the smallest term, but since that term is 1, we get a lower bound of <I>n</I> for the summation--far off from our upper bound of <I>n</I><SUP>2</SUP>.<P>
We can obtain a better lower bound by first splitting the summation. Assume for convenience that <I>n</I> is even. We have<P>
<img src="48_f.gif"><P>
<img src="49_a.gif"><P>
which is an asymptotically tight bound, since <img src="49_b.gif">.<P>
For a summation arising from the analysis of an algorithm, we can often split the summation and ignore a constant number of the initial terms. Generally, this technique applies when each term <I>a<SUB>k</I></SUB> in a summation <img src="49_c.gif"> is independent of <I>n</I>. Then for any constant <I>k</I><SUB>0</SUB> &gt; 0, we can write<P>
<img src="49_d.gif"><P>
since the initial terms of the summation are all constant and there is a constant number of them. We can then use other methods to bound <img src="49_e.gif">. For example, to find an asymptotic upper bound on<P>
<img src="49_f.gif"><P>
we observe that the ratio of consecutive terms is<P>
<img src="49_g.gif"><P>
if <I>k</I> <img src="../images/gteq.gif"> 3. Thus, the summation can be split into<P>
<img src="49_h.gif"><P>
since the second summation is a decreasing geometric series.<P>
The technique of splitting summations can be used to determine asymptotic bounds in much more difficult situations. For example, we can obtain a bound of <I>0</I>(lg <I>n</I>) on the harmonic series (3.5):<P>
<img src="49_i.gif"><P>
The idea is to split the range 1 to <I>n</I> into <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>1g <I>n<FONT FACE="Courier New" SIZE=2></I><img src="../images/hfbrdr12.gif"><I></I></FONT> pieces and upper bound the contribution of each piece by 1. Thus,<P>
<img src="50_a.gif"><P>
<h4><a name="070d_0001">(3.8)<a name="070d_0001"></sub></sup></h4><P>
<P>







<h2>Approximation by integrals</h2><P>
When a summation can be expressed as <img src="50_b.gif">, where &acirc;(<I>k</I>) is a monotonically increasing function, we can approximate it by integrals:<P>
<img src="50_c.gif"><P>
<h4><a name="070e_0001">(3.9)<a name="070e_0001"></sub></sup></h4><P>
The justification for this approximation is shown in Figure 3.1. The summation is represented as the area of the rectangles in the figure, and the integral is the shaded region under the curve. When &acirc;(<I>k</I>) is a monotonically decreasing function, we can use a similar method to provide the bounds<P>
<img src="50_d.gif"><P>
<h4><a name="070e_0002">(3.10)<a name="070e_0002"></sub></sup></h4><P>
The integral approximation (3.10) gives a tight estimate for the <I>n</I>th harmonic number. For a lower bound, we obtain<P>
<img src="50_e.gif"><P>
<h4><a name="070e_0003">(3.11)<a name="070e_0003"></sub></sup></h4><P>
For the upper bound, we derive the inequality<P>
<img src="50_f.gif"><P>
which yields the bound<P>
<img src="50_g.gif"><P>
<h4><a name="070e_0004">(3.12)<a name="070e_0004"></sub></sup></h4><P>
<img src="51_a.gif"><P>
<h4><a name="070e_0005">Figure 3.1 Approximation of <img src="51_b.gif"> by integrals. The area of each rectangle is shown within the rectangle, and the total rectangle area represents the value of the summation. The integral is represented by the shaded area under the curve. By comparing areas in (a), we get <img src="51_c.gif">, and then by shifting the rectangles one unit to the right, we get <img src="51_d.gif">.in (b).<a name="070e_0005"></sub></sup></h4><P>
<P>







<h2><a name="070f_0001">Exercises<a name="070f_0001"></h2><P>
<a name="070f_0002">3.2-1<a name="070f_0002"><P>
Show that <img src="52_a.gif"> is bounded above by a constant.<P>
<a name="070f_0003">3.2-2<a name="070f_0003"><P>
Find an asymptotic upper bound on the summation<P>
<img src="52_b.gif"><P>
<a name="070f_0004">3.2-3<a name="070f_0004"><P>
Show that the nth harmonic number is <img src="../images/omega12.gif">(1g n) by splitting the summation.<P>
<a name="070f_0005">3.2-4<a name="070f_0005"><P>
Approximate <img src="52_c.gif"> with an integral.<P>
<a name="070f_0006">3.2-5<a name="070f_0006"><P>
Why didn't we use the integral approximation (3.10) directly on <img src="52_d.gif"> to obtain an upper bound on the <I>n</I>th harmonic number?<P>
<P>


<P>







<h1><a name="0710_0001">Problems<a name="0710_0001"></h1><P>
<a name="0710_0002">3-1 Bounding summations<a name="0710_0002"><P>
Give asymptotically tight bounds on the following summations. Assume that <I>r</I> <img src="../images/gteq.gif"> 0 and <I>s</I> <img src="../images/gteq.gif"> 0 are constants.<P>
<img src="52_e.gif"><P>
<P>







<h1>Chapter notes</h1><P>
Knuth [121] is an excellent reference for the material presented in this chapter. Basic properties of series can be found in any good calculus book, such as Apostol [12] or Thomas and Finney [192].<P>
<P>


<P>
<P>
<center>Go to <a href="chap04.htm">Chapter 4</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>