chap18.htm

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

<h1><a name="0846_15dc">18.3 The potential method<a name="0846_15dc"></h1><P>
<a name="0846_15d6"><a name="0846_15d7"><a name="0846_15d8">Instead of representing prepaid work as credit stored with specific objects in the data structure, the <I><B>potential method</I></B> of amortized analysis represents the prepaid work as "potential energy,"or just "potential," that can be released to pay for future operations. The potential is associated with the data structure as a whole rather than with specific objects within the data structure.<P>
<a name="0846_15d9"><a name="0846_15da"><a name="0846_15db">The potential method works as follows. We start with an initial data structure <I>D</I><SUB>0 </SUB>on which <I>n </I>operations are performed. For each <I>i</I> = 1, 2, . . . , <I>n</I>, we let <I>c<SUB>i</I></SUB> be the actual cost of the <I>i</I>th operation and <I>D<SUB>i</I></SUB> be the data structure that results after applying the <I>i</I>th operation to data structure <I>D<SUB>i - </I>l.</SUB> A <I><B>potential function</I></B> <img src="../images/phicap12.gif"> maps each data structure <I>D<SUB>i</I></SUB> to a real number <img src="../images/phicap12.gif"> (<I>D<SUB>i</I></SUB>), which is the <I><B>potential</I></B> associated with data structure <I>D<SUB>i</I></SUB>. The <I><B>amortized cost</I></B> <img src="363_a.gif"> of the <I>i</I>th operation with respect to potential function <img src="../images/phicap12.gif"> is defined by<P>
<img src="363_b.gif"><P>
<h4><a name="0846_15dd">(18.1)<a name="0846_15dd"></sub></sup></h4><P>
The amortized cost of each operation is therefore its actual cost plus the increase in potential due to the operation. By equation (18.1), the total amortized cost of the <I>n</I> operations is<P>
<img src="363_c.gif"><P>
<img src="364_a.gif"><P>
<h4><a name="0846_15de">(18.2)<a name="0846_15de"></sub></sup></h4><P>
The second equality follows from equation (3.7), since the <img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) telescope.<P>
If we can define a potential function <img src="../images/phicap12.gif"> so that <img src="../images/phicap12.gif">(<I>D<SUB>n</SUB>) </I><img src="../images/gteq.gif"><I></I> <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>), then the total amortized cost <img src="364_b.gif"> is an upper bound on the total actual cost. In practice, we do not always know how many operations might be performed. Therefore, if we require that <img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>)<I> </I><img src="../images/gteq.gif"> <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>) for all <I>i</I>, then we guarantee, as in the accounting method, that we pay in advance. It is often convenient to define <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>) to be 0 and then to show that <img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) <img src="../images/gteq.gif"> 0 for all <I>i</I>. (See Exercise 18.3-1 for an easy way to handle cases in which <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>) <img src="../images/noteq.gif"> 0.)<P>
Intuitively, if the potential difference <img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) - <img src="../images/phicap12.gif">(<I>D<SUB>i - </I>1</SUB>) of the <I>i</I>th operation is positive, then the amortized cost <img src="364_c.gif"> represents an overcharge to the <I>i</I>th operation, and the potential of the data structure increases. If the potential difference is negative, then the amortized cost represents an undercharge to the <I>i</I>th operation, and the actual cost of the operation is paid by the decrease in the potential.<P>
The amortized costs defined by equations (18.1) and (18.2) depend on the choice of the potential function <img src="../images/phicap12.gif">. Different potential functions may yield different amortized costs yet still be upper bounds on the actual costs. There are often trade-offs that can be made in choosing a potential function; the best potential function to use depends on the desired time bounds.<P>





<h2>Stack operations</h2><P>
<a name="0847_15dc"><a name="0847_15dd">To illustrate the potential method, we return once again to the example of the stack operations <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>. We define the potential function <img src="../images/phicap12.gif"> on a stack to be the number of objects in the stack. For the empty stack <I>D</I><SUB>0</SUB> with which we start, we have <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>) = 0. Since the number of objects in the stack is never negative, the stack <I>D<SUB>i </I></SUB>that results after the <I>i</I>th operation has nonnegative potential, and thus<P>
<pre><img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>)  <img src="../images/gteq.gif">  0</sub></sup></pre><P>
<pre>=  <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>).</sub></sup></pre><P>
The total amortized cost of <I>n</I> operations with respect to <img src="../images/phicap12.gif"> therefore represents an upper bound on the actual cost.<P>
Let us now compute the amortized costs of the various stack operations. If the <I>i</I>th operation on a stack containing <I>s</I> objects is a <FONT FACE="Courier New" SIZE=2>PUSH</FONT> operation, then the potential difference is<P>
<pre><img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) - <img src="../images/phicap12.gif">(<I>D<SUB>i - </I>1</SUB>)  =  (<I>s</I> + 1 ) - <I>s</I></sub></sup></pre><P>
<pre>=  1 .</sub></sup></pre><P>
By equation (18.1), the amortized cost of this <FONT FACE="Courier New" SIZE=2>PUSH</FONT> operation is<P>
<img src="364_d.gif"><P>
Suppose that the <I>i</I>th operation on the stack is <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT>(<I>S,k</I>) and that <I>k</I>' <I>= min(</I>k,s<I>) objects are popped off the stack. The actual cost of the operation is </I>k<I>'</I>, and the potential difference is<P>
<pre><img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) - <img src="../images/phicap12.gif">(<I>D<SUB>i-</I>1</SUB>) = -<I>k</I>'<I>.</I></sub></sup></pre><P>
Thus, the amortized cost of the <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operation is<P>
<img src="365_a.gif"><P>
Similarly, the amortized cost of an ordinary <FONT FACE="Courier New" SIZE=2>POP</FONT> operation is 0.<P>
The amortized cost of each of the three operations is <I>O</I>(1), and thus the total amortized cost of a sequence of <I>n</I> operations is <I>O</I>(<I>n</I>). Since we have already argued that <img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) <img src="../images/gteq.gif"> <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>), the total amortized cost of <I>n</I> operations is an upper bound on the total actual cost. The worst-case cost of <I>n</I> operations is therefore <I>O</I>(<I>n</I>).<P>
<P>







<h2>Incrementing a binary counter</h2><P>
<a name="0848_15de"><a name="0848_15df">As another example of the otential method, we again look at incrementing a binary counter. This time, we define the potential of the counter after the <I>i</I>th <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operation to be <I>b<SUB>i</I></SUB>, the number of 1's in the counter after the <I>i</I>th operation.<P>
Let us compute the amortized cost of an <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operation. Suppose that the <I>i</I>th <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operation resets <I>t<SUB>i</SUB> </I>bits. The actual cost of the operation is therefore at most <I>t<SUB>i</SUB> </I>+1, since in addition to resetting <I>t<SUB>i</SUB> </I>bits, it sets at most one bit to a 1. The number of 1's in the counter after the <I>i</I>th operation is therefore <I>b<SUB>i</SUB> </I><img src="../images/lteq12.gif"><I> b<SUB>i-1</SUB> </I>- <I>t<SUB>i</SUB> +</I>1,<I> </I>and the potential difference is<P>
<pre><img src="../images/phicap12.gif"> (<I>D<SUB>i</I></SUB>) - <img src="../images/phicap12.gif">(<I>D<SUB>i</I>-1</SUB>)  <img src="../images/lteq12.gif"><I>  </I>(<I>b<SUB>i</I>-1</SUB> - <I>t<SUB>i</SUB> </I>+ 1) - <I>b<SUB>i</I>-1</sub></sup></pre><P>
<pre>=  1 - <I>t<SUB>i</SUB>.</I></sub></sup></pre><P>
The amortized cost is therefore<P>
<img src="365_b.gif"><P>
If the counter starts at zero, then <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>) = 0. Since <img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) <img src="../images/gteq.gif"> 0 for all <I>i</I>, the total amortized cost of a sequence of <I>n</I> INCREMENT operations is an upper bound on the total actual cost, and so the worst-case cost of <I>n </I>INCREMENT operations is <I>O</I>(<I>n</I>).<P>
The potential method gives us an easy way to analyze the counter even when it does not start at zero. There are initially <I>b</I><SUB>0</SUB> 1's, and after <I>n </I><FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations there are <I>b<SUB>n</I></SUB> 1's, where 0 <img src="../images/lteq12.gif"> <I>b</I><SUB>0</SUB><I>, b<SUB>n</SUB> </I><img src="../images/lteq12.gif"><I> k</I>. We can rewrite equation (18.2) as<P>
<img src="366_a.gif"><P>
<h4><a name="0848_15e0">(18.3)<a name="0848_15e0"></sub></sup></h4><P>
We have <img src="366_b.gif"> for all 1 <img src="../images/lteq12.gif"> <I>i </I><img src="../images/lteq12.gif"><I> n</I>. Since <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>) = <I>b</I><SUB>0</SUB> and <img src="../images/phicap12.gif">(<I>D<SUB>n</I></SUB>) = <I>b<SUB>n</I></SUB>,<SUB> </SUB>the total actual cost of <I>n</I> <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations is<P>
<img src="366_c.gif"><P>
Note in particular that since <I>b</I><SUB>0</SUB><I> </I><img src="../images/lteq12.gif"><I> k</I>, if we execute at least <I>n </I>= <img src="../images/omega12.gif">(<I>k</I>) <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations, the total actual cost is <I>O</I>(<I>n</I>), no matter what initial value the counter contains.<P>
<P>







<h2><a name="0849_15e2">Exercises<a name="0849_15e2"></h2><P>
<a name="0849_15e3">18.3-1<a name="0849_15e3"><P>
Suppose we have a potential function <img src="../images/phicap12.gif"> such that <img src="../images/phicap12.gif">(<I>D<SUB>i</I></SUB>) <img src="../images/gteq.gif"> <img src="../images/phicap12.gif">(<I>D</I><SUB>0</SUB>) for all <I>i</I>, but <img src="../images/phicap12.gif">(D<SUB>0</SUB>) <img src="../images/noteq.gif"> 0. Show that there exists a potential function <img src="../images/phicap12.gif">'<I> such that <img src="../images/phicap12.gif">'</I>(<I>D</I><SUB>0</SUB>) = 0, <img src="../images/phicap12.gif">'<I>(</I>D<SUB>i<I></SUB>) <img src="../images/gteq.gif"> 0 for all </I>i<I> <img src="../images/gteq.gif"> 1, and the amortized costs using <img src="../images/phicap12.gif">'</I> are the same as the amortized costs using <img src="../images/phicap12.gif">.<P>
<a name="0849_15e4">18.3-2<a name="0849_15e4"><P>
Redo Exercise 18.1-3 using a potential method of analysis.<P>