📄 chap03.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 3: SUMMATIONS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap04.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap02.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="06ff_11b2">CHAPTER 3: SUMMATIONS<a name="06ff_11b2"></h1><P>
<a name="06ff_11b0"><a name="06ff_11b1">When an algorithm contains an iterative control construct such as a <B>while</B> or <B>for</B> loop, its running time can be expressed as the sum of the times spent on each execution of the body of the loop. For example, we found in Section 1.2 that the <I>j</I>th iteration of insertion sort took time proportional to <I>j</I> in the worst case. By adding up the time spent on each iteration, we obtained the summation (or series)<P>
<img src="42_a.gif"><P>
Evaluating this summation yielded a bound of <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) on the worst-case running time of the algorithm. This example indicates the general importance of understanding how to manipulate and bound summations. (As we shall see in Chapter 4, summations also arise when we use certain methods to solve recurrences.)<P>
Section 3.1 lists several basic formulas involving summations. Section 3.2 offers useful techniques for bounding summations. The formulas in Section 3.1 are given without proof, though proofs for some of them are presented in Section 3.2 to illustrate the methods of that section. Most of the other proofs can be found in any calculus text.<P>
<h1><a name="0701_11b9">3.1 Summation formulas and properties<a name="0701_11b9"></h1><P>
<a name="0701_11b2"><a name="0701_11b3"><a name="0701_11b4">Given a sequence <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . of numbers, the finite sum <I>a</I><SUB>1</SUB> + <I>a</I><SUB>2</SUB> + . . . +<I>a<SUB>n</I></SUB> can be written<P>
<img src="42_b.gif"><P>
If <I>n</I> = 0, the value of the summation is defined to be 0. If <I>n</I> is not an integer, we assume that the upper limit is <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I><img src="../images/hfbrdr12.gif"></FONT>. Similarly, if the sum begins with <I>k</I> = <I>x</I>, where <I>x</I> is not an integer, we assume that the initial value for the summation is <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"><I>x</I><img src="../images/hfbrdr12.gif"></FONT>. (Generally, we shall put in floors and ceilings explicitly.) The value of a finite series is always well defined, and its terms can be added in any order.<P>
Given a sequence <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . of numbers, the infinite sum <I>a</I><SUB>1</SUB> + <I>a</I><SUB>2</SUB> + <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> can be written<P>
<img src="43_a.gif"><P>
which is interpreted to mean<P>
<img src="43_b.gif"><P>
<a name="0701_11b5"><a name="0701_11b6"><a name="0701_11b7"><a name="0701_11b8">If the limit does not exist, the series <I><B>diverges</I></B>; otherwise, it <I><B>converges</I></B>. The terms of a convergent series cannot always be added in any order. We can, however, rearrange the terms of an <I><B>absolutely convergent series</I></B>, that is, a series <img src="43_c.gif"> for which the series <img src="43_d.gif"> also converges.<P>
<h2>Linearity</h2><P>
<a name="0702_11b9"><a name="0702_11ba">For any real number <I>c</I> and any finite sequences <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB> and <I>b</I><SUB>1</SUB>, <I>b</I><SUB>2</SUB>, . . . , <I>b<SUB>n</I></SUB>,<P>
<img src="43_e.gif"><P>
The linearity property is also obeyed by infinite convergent series.<P>
<a name="0702_11bb"><a name="0702_11bc">The linearity property can be exploited to manipulate summations incorporating asymptotic notation. For example,<P>
<img src="43_f.gif"><P>
In this equation, the <img src="../images/bound.gif">-notation on the left-hand side applies to the variable <I>k</I>, but on the right-hand side, it applies to <I>n</I>. Such manipulations can also be applied to infinite convergent series.<P>
<P>
<h2>Arithmetic series</h2><P>
<a name="0703_11bd">The summation<P>
<img src="43_g.gif"><P>
which came up when we analyzed insertion sort, is an <I><B>arithmetic series</I></B> and has the value<P>
<img src="43_h.gif"><P>
<h4><a name="0703_11be">(3.1)<a name="0703_11be"></sub></sup></h4><P>
<h4><a name="0703_11bf">(3.2)<a name="0703_11bf"></sub></sup></h4><P>
<P>
<h2>Geometric series</h2><P>
<a name="0704_11be"><a name="0704_11bf"><a name="0704_11c0">For real <I>x</I> <img src="../images/noteq.gif"> 1, the summation<P>
<img src="44_a.gif"><P>
is a <I><B>geometric </I></B>or e<I><B>xponential series</I></B> and has the value<P>
<img src="44_b.gif"><P>
<h4><a name="0704_11c1">(3.3)<a name="0704_11c1"></sub></sup></h4><P>
When the summation is infinite and |<I>x</I>| < 1, we have the infinite decreasing geometric series<P>
<img src="44_c.gif"><P>
<h4><a name="0704_11c2">(3.4)<a name="0704_11c2"></sub></sup></h4><P>
<P>
<h2>Harmonic series</h2><P>
<a name="0705_11c1"><a name="0705_11c2">For positive integers <I>n</I>, the <I>n</I>th <B>harmonic number</B> is<P>
<img src="44_d.gif"><P>
<h4><a name="0705_11c3">(3.5)<a name="0705_11c3"></sub></sup></h4><P>
<P>
<h2>Integrating and differentiating series</h2><P>
<a name="0706_11c3"><a name="0706_11c4">Additional formulas can be obtained by integrating or differentiating the formulas above. For example, by differentiating both sides of the infinite geometric series (3.4) and multiplying by <I>x</I>, we get<P>
<img src="44_e.gif"><P>
<h4><a name="0706_11c5">(3.6)<a name="0706_11c5"></sub></sup></h4><P>
<P>
<h2>Telescoping series</h2><P>
<a name="0707_11c5"><a name="0707_11c6"><a name="0707_11c7">For any sequence <I>a</I><SUB>0</SUB>, <I>a</I><SUB>1</SUB>, . . . , <I>a<SUB>n</I></SUB>,<P>
<img src="44_f.gif"><P>
<h4><a name="0707_11c8">(3.7)<a name="0707_11c8"></sub></sup></h4><P>
since each of the terms <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n-</I>1</SUB> is added in exactly once and subtracted out exactly once. We say that the sum<I><B> telescopes.</I></B> Similarly,<P>
<img src="44_g.gif"><P>
As an example of a telescoping sum, consider the series<P>
<img src="45_a.gif"><P>
Since we can rewrite each term as<P>
<img src="45_b.gif"><P>
we get<P>
<img src="45_c.gif"><P>
<P>
<h2>Products</h2><P>
<a name="0708_11c8">The finite product <I>a</I><SUB>1</SUB> <I>a</I><SUB>2</SUB> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <I>a<SUB>n</I></SUB> can be written<P>
<img src="45_d.gif"><P>
If <I>n</I> = 0, the value of the product is defined to be 1. We can convert a formula with a product to a formula with a summation by using the identity<P>
<img src="45_e.gif"><P>
<P>
<h2><a name="0709_0001">Exercises<a name="0709_0001"></h2><P>
<a name="0709_0002">3.1-1<a name="0709_0002"><P>
Find a simple formula for <img src="45_f.gif"><P>
<a name="0709_0003">3.1-2<a name="0709_0003"><P>
Show that <img src="45_g.gif"> by manipulating the harmonic series.<P>
<a name="0709_0004">3.1-3<a name="0709_0004"><P>
Show that <img src="45_h.gif"><P>
<a name="0709_0005">3.1-4<a name="0709_0005"><P>
Evaluate the sum <img src="45_i.gif"><P>
<a name="0709_0006">3.1-5<a name="0709_0006"><P>
Use the linearity property of summations to prove that <img src="45_j.gif"><P>
<a name="0709_0007">3.1-6<a name="0709_0007"><P>
Prove that <img src="46_a.gif"><P>
<a name="0709_0008">3.1-7<a name="0709_0008"><P>
Evaluate the product <img src="46_b.gif"><P>
<a name="0709_0009">3.1-8<a name="0709_0009"><P>
Evaluate the product <img src="46_c.gif"><P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -