📄 chap18.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 18: AMORTIZED ANALYSIS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="partv.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="chap17.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="083c_15c1">CHAPTER 18: AMORTIZED ANALYSIS<a name="083c_15c1"></h1><P>
<a name="083c_15c0">In an <I><B>amortized analysis</I></B>, the time required to perform a sequence of data-structure operations is averaged over all the operations performed. Amortized analysis can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a single operation might be expensive. Amortized analysis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the <I>average performance of each operation in the worst case.</I><P>
The first three sections of this chapter cover the three most common techniques used in amortized analysis. Section 18.1 starts with the aggregate method, in which we determine an upper bound <I>T</I>(<I>n</I>) on the total cost of a sequence of <I>n</I> operations. The amortized cost per operation is then <I>T</I>(<I>n</I>)<I>/n</I>.<P>
Section 18.2 covers the accounting method, in which we determine an amortized cost of each operation. When there is more than one type of operation, each type of operation may have a different amortized cost. The accounting method overcharges some operations early in the sequence, storing the overcharge as "prepaid credit" on specific objects in the data structure. The credit is used later in the sequence to pay for operations that are charged less than they actually cost.<P>
Section 18.3 discusses the potential method, which is like the accounting method in that we determine the amortized cost of each operation and may overcharge operations early on to compensate for undercharges later. The potential method maintains the credit as the "potential energy" of the data structure instead of associating the credit with individual objects within the data structure.<P>
We shall use two examples to examine these three models. One is a stack with the additional operation <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT>, which pops several objects at once. The other is a binary counter that counts up from 0 by means of the single operation <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT>.<P>
While reading this chapter, bear in mind that the charges assigned during an amortized analysis are for analysis purposes only. They should not appear in the code. If, for example, a credit is assigned to an object <I>x</I> when using the accounting method, there is no need to assign an appropriate amount to some attribute <I>credit</I>[<I>x</I>] in the code.<P>
The insight into a particular data structure gained by performing an amortized analysis can help in optimizing the design. In Section 18.4, for example, we shall use the potential method to analyze a dynamically expanding and contracting table.<P>
<h1><a name="083e_15c4">18.1 The aggregate method<a name="083e_15c4"></h1><P>
<a name="083e_15c1"><a name="083e_15c2"><a name="083e_15c3">In the <I><B>aggregate method</I></B> of amortized analysis, we show that for all <I>n</I>, a sequence of <I>n</I> operations takes <I>worst-case</I> time <I>T</I>(<I>n</I>) in total. In the worst case, the average cost, or <I><B>amortized cost</I></B>, per operation is therefore <I>T</I>(<I>n</I>) / <I>n</I>. Note that this amortized cost applies to each operation, even when there are several types of operations in the sequence. The other two methods we shall study in this chapter, the accounting method and the potential method, may assign different amortized costs to different types of operations.<P>
<h2>Stack operations</h2><P>
<a name="083f_15c4"><a name="083f_15c5">In our first example of the aggregate method, we analyze stacks that have been augmented with a new operation. Section 11.1 presented the two fundamental stack operations, each of which takes <I>O</I>(1) time:<P>
<FONT FACE="Courier New" SIZE=2>PUSH</FONT>(<I>S</I>, <I>x</I>) pushes object <I>x</I> onto stack <I>S</I>.<P>
<FONT FACE="Courier New" SIZE=2>POP</FONT>(<I>S</I>) pops the top of stack <I>S</I> and returns the popped object.<P>
Since each of these operations runs in <I>O</I>(1) time, let us consider the cost of each to be 1. The total cost of a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>PUSH</FONT> and <FONT FACE="Courier New" SIZE=2>POP</FONT> operations is therefore <I>n</I>, and the actual running time for <I>n</I> operations is therefore <img src="../images/bound.gif">(<I>n</I>).<P>
<a name="083f_15c6">The situation becomes more interesting if we add the stack operation <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT>(<I>S, k</I>), which removes the <I>k</I> top objects of stack <I>S</I>, or pops the entire stack if it contains less than <I>k</I> objects. In the following pseudocode, the operation S<FONT FACE="Courier New" SIZE=2>TACK-</FONT><FONT FACE="Courier New" SIZE=2>EMPTY</FONT> returns <FONT FACE="Courier New" SIZE=2>TRUE</FONT> if there are no objects currently on the stack, and <FONT FACE="Courier New" SIZE=2>FALSE</FONT> otherwise.<P>
<pre>MULTIPOP(<I>S,k</I>)</sub></sup></pre><P>
<pre>1 <B>while</B> not STACK-EMPTY(<I>S</I>) and <I>k </I><img src="../images/noteq.gif"> 0</sub></sup></pre><P>
<pre>2 <B>do</B> POP(<I>S</I>)</sub></sup></pre><P>
<pre>3<I> k </I><img src="../images/arrlt12.gif"> <I>k</I> - 1</sub></sup></pre><P>
Figure 18.1 shows an example of <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT>.<P>
What is the running time of <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT>(<I>S, k</I>) on a stack of <I>s</I> objects? The actual running time is linear in the number of <FONT FACE="Courier New" SIZE=2>POP</FONT> operations actually executed, and thus it suffices to analyze <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> in terms of the abstract costs of 1 each for <FONT FACE="Courier New" SIZE=2>PUSH</FONT> and <FONT FACE="Courier New" SIZE=2>POP</FONT>. The number of iterations of the <B>while</B> loop is the number min(<I>s, k</I>) of objects popped off the stack. For each iteration of the loop, one call is made to P<FONT FACE="Courier New" SIZE=2>OP </FONT>in line 2. Thus, the total cost of <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> is min(<I>s, k</I>), and the actual running time is a linear function of this cost.<P>
<img src="358_a.gif"><P>
<h4><a name="083f_15c7">Figure 18.1 The action of <FONT FACE="Courier New" SIZE=2>MULTIPOP<FONT FACE="Times New Roman" SIZE=2> on a stack S, shown initially in (a). The top 4 objects are popped by <FONT FACE="Courier New" SIZE=2>MULTIPOP<FONT FACE="Times New Roman" SIZE=2>(S, 4), whose result is shown in (b). The next operation is <FONT FACE="Courier New" SIZE=2>MULTIPOP<FONT FACE="Times New Roman" SIZE=2>(S, 7), which empties the stack<img src="../images/arrlt12.gif">shown in (c)<img src="../images/arrlt12.gif">since there were fewer than 7 objects remaining.<a name="083f_15c7"></FONT></FONT></FONT></FONT></FONT></FONT></sub></sup></h4><P>
Let us analyze a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=1>PUSH</FONT>, <FONT FACE="Courier New" SIZE=2>POP</FONT>, and <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operations on an initially empty stack. The worst-case cost of a <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operation in the sequence is <I>O</I>(<I>n</I>), since the stack size is at most <I>n</I>. The worst-case time of any stack operation is therefore <I>O</I>(<I>n</I>), and hence a sequence of <I>n</I> operations costs <I>O</I>(<I>n</I><SUP><FONT FACE="Times New Roman" SIZE=1>2</FONT></SUP>), since we may have <I>O</I>(<I>n</I>) <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operations costing <I>O</I>(<I>n</I>) each. Although this analysis is correct, the <I>O</I>(<I>n</I><SUP><FONT FACE="Times New Roman" SIZE=1>2</FONT></SUP>) result, obtained by considering the worst-case cost of each operation individually, is not tight.<P>
Using the aggregate method of amortized analysis, we can obtain a better upper bound that considers the entire sequence of <I>n</I> operations. In fact, although a single <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operation can be expensive, any sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>PUSH</FONT>, <FONT FACE="Courier New" SIZE=2>POP</FONT>, and <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operations on an initially empty stack can cost at most <I>O</I>(<I>n</I>). Why? Each object can be popped at most once for each time it is pushed. Therefore, the number of times that <FONT FACE="Courier New" SIZE=2>POP</FONT> can be called on a nonempty stack, including calls within <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT>, is at most the number of <FONT FACE="Courier New" SIZE=2>PUSH</FONT> operations, which is at most <I>n</I>. For any value of <I>n</I>, any sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>PUSH</FONT>, <FONT FACE="Courier New" SIZE=2>POP</FONT>, and <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operations takes a total of <I>O</I>(<I>n</I>) time. The amortized cost of an operation is the average: <I>O</I>(<I>n</I>)/<I>n</I> = <I>O</I>(1).<P>
We emphasize again that although we have just shown that the average cost, and hence running time, of a stack operation is <I>O</I>(1), no probabilistic reasoning was involved. We actually showed a <I>worst-case</I> bound of <I>O</I>(<I>n</I>) on a sequence of <I>n</I> operations. Dividing this total cost by <I>n</I> yielded the average cost per operation, or the amortized cost.<P>
<P>
<h2>Incrementing a binary counter</h2><P>
<a name="0840_15c7"><a name="0840_15c8">As another example of the aggregate method, consider the problem of implementing a <I>k-</I>bit binary counter that counts upward from 0. We use an array <I>A</I>[0 . . <I>k</I> - 1] of bits, where <I>length</I>[<I>A</I>] = <I>k</I>, as the counter. A binary number <I>x</I> that is stored in the counter has its lowest-order bit in <I>A</I>[0] and its highest-order bit in <I>A</I>[<I>k</I> - 1], so that <img src="358_b.gif">. Initially, <I>x</I> = 0, and thus <I>A</I>[<I>i</I>] = 0 for <I>i</I> = 0, 1, . . . , <I>k</I> - 1. To add 1 (modulo 2<I><SUP>k</I></SUP>) to the value in the counter, we use the following procedure.<P>
<img src="359_a.gif"><P>
<h4><a name="0840_15ca">Figure 18.2 An 8-bit binary counter as its value goes from 0 to 16 by a sequence of 16 <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations. Bits that flip to achieve the next value are shaded. The running cost for flipping bits is shown at the right. Notice that the total cost is never more than twice the total number of <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations.<a name="0840_15ca"></sub></sup></h4><P>
<pre><a name="0840_15c9">INCREMENT(<I>A</I>)</sub></sup></pre><P>
<pre>1 <I>i</I> <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>2 <B>while</B> <I>i<</I> <I>length</I>[<I>A</I>] and <I>A</I>[<I>i</I>] = 1</sub></sup></pre><P>
<pre>3 <B>do</B> <I>A</I>[<I>i</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>4 <I>i</I> <img src="../images/arrlt12.gif"> <I>i</I> + 1</sub></sup></pre><P>
<pre>5 <B>if</B> <I>i</I> < <I>length</I>[<I>A</I>]</sub></sup></pre><P>
<pre>6 <B>then</B> <I>A</I>[<I>i</I>] <img src="../images/arrlt12.gif"> 1</sub></sup></pre><P>
This algorithm is essentially the same one implemented in hardware by a ripple-carry counter (see Section 29.2.1). Figure 18.2 shows what happens to a binary counter as it is incremented 16 times, starting with the initial value 0 and ending with the value 16. At the start of each iteration of the <B>while</B> loop in lines 2-4, we wish to add a 1 into position <I>i</I>. If <I>A</I>[<I>i</I>] = 1, then adding 1 flips the bit to 0 in position <I>i</I> and yields a carry of 1, to be added into position <I>i</I> + 1 on the next iteration of the loop. Otherwise, the loop ends, and then, if <I>i <</I> <I>k</I>, we know that <I>A</I>[<I>i</I>] = 0, so that adding a 1 into position <I>i</I>, flipping the 0 to a 1, is taken care of in line 6. The cost of each <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operation is linear in the number of bits flipped.<P>
As with the stack example, a cursory analysis yields a bound that is correct but not tight. A single execution of <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> takes time <img src="../images/bound.gif">(<I>k</I>) in the worst case, in which array <I>A</I> contains all 1's. Thus, a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations on an initially zero counter takes time <I>O</I>(<I>nk</I>) in the worst case.<P>
We can tighten our analysis to yield a worst-case cost of <I>O</I>(<I>n</I>) for a sequence of <I>n</I> I<FONT FACE="Courier New" SIZE=2>NCREMENT'S</FONT> by observing that not all bits flip each time <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> is called. As Figure 18.2 shows, <I>A</I>[0] does flip each time <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> is called. The next-highest-order bit, <I>A</I>[1], flips only every other time: a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations on an initially zero counter causes <I>A</I>[1] to flip <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> times. Similarly, bit <I>A</I>[2] flips only every fourth time, or <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>n/4<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> times in a sequence of <I>n</I> I<FONT FACE="Courier New" SIZE=2>NCREMENT'S</FONT>. In general, for <I>i</I> = 0, 1, . . . , <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg <I>n</I><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>, bit <I>A</I>[<I>i</I>] flips <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"><I>n</I></FONT>/2<I><SUP>i</I></SUP><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> times in a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations on an initially zero counter. For <I>i</I> > <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg <I>n</I><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>, bit <I>A</I>[<I>i</I>] never flips at all. The total number of flips in the sequence is thus<P>
<img src="360_a.gif"><P>
by equation (3.4). The worst-case time for a sequence of <I>n</I> I<FONT FACE="Courier New" SIZE=2>NCREMENT </FONT>operations on an initially zero counter is therefore <I>O</I>(<I>n</I>), so the amortized cost of each operation is <I>O</I>(<I>n</I>)/<I>n</I> = <I>O</I>(1).<P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -