chap18.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<h2><a name="0841_15cc">Exercises<a name="0841_15cc"></h2><P>
<a name="0841_15cd">18.1-1<a name="0841_15cd"><P>
<a name="0841_15ca">If a <FONT FACE="Courier New" SIZE=2>MULTIPUSH</FONT> operation were included in the set of stack operations, would the <I>O</I>(1) bound on the amortized cost of stack operations continue to hold?<P>
<a name="0841_15ce">18.1-2<a name="0841_15ce"><P>
<a name="0841_15cb">Show that if a <FONT FACE="Courier New" SIZE=2>DECREMENT</FONT> operation were included in the <I>k-</I>bit counter example, <I>n</I> operations could cost as much as <img src="../images/bound.gif">(<I>nk</I>) time.<P>
<a name="0841_15cf">18.1-3<a name="0841_15cf"><P>
A sequence of <I>n</I> operations is performed on a data structure. The <I>i</I>th operation costs <I>i</I> if <I>i</I> is an exact power of 2, and 1 otherwise. Use an aggregate method of analysis to determine the amortized cost per operation.<P>
<P>


<P>







<h1><a name="0842_15d0">18.2 The accounting method<a name="0842_15d0"></h1><P>
<a name="0842_15cc"><a name="0842_15cd"><a name="0842_15ce"><a name="0842_15cf">In the <I><B>accounting method</I></B> of amortized analysis, we assign differing charges to different operations, with some operations charged more or less than they actually cost. The amount we charge an operation is called its <I><B>amortized cost</I></B>. When an operation's amortized cost exceeds its actual cost, the difference is assigned to specific objects in the data structure as <I><B>credit</I></B>. Credit can be used later on to help pay for operations whose amortized cost is less than their actual cost. Thus, one can view the amortized cost of an operation as being split between its actual cost and credit that is either deposited or used up. This is very different from the aggregate method, in which all operations have the same amortized cost.<P>
One must choose the amortized costs of operations carefully. If we want analysis with amortized costs to show that in the worst case the average cost per operation is small, the total amortized cost of a sequence of operations must be an upper bound on the total actual cost of the sequence. Moreover, as in the aggregate method, this relationship must hold for all sequences of operations. Thus, the total credit associated with the data structure must be nonnegative at all times, since it represents the amount by which the total amortized costs incurred exceed the total actual costs incurred. If the total credit were ever allowed to become negative (the result of undercharging early operations with the promise of repaying the account later on), then the total amortized costs incurred at that time would be below the total actual costs incurred; for the sequence of operations up to that time, the total amortized cost would not be an upper bound on the total actual cost. Thus, we must take care that the total credit in the data structure never becomes negative.<P>





<h2>Stack operations</h2><P>
<a name="0843_15d0"><a name="0843_15d1">To illustrate the accounting method of amortized analysis, let us return to the stack example. Recall that the actual costs of the operations were<P>
<pre>PUSH     1 ,</sub></sup></pre><P>
<pre>POP      1 ,</sub></sup></pre><P>
<pre>MULTIPOP  min(<I>k</I>,<I>s</I>) ,</sub></sup></pre><P>
where <I>k</I> is the argument supplied to <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> and <I>s</I> is the stack size when it is called. Let us assign the following amortized costs:<P>
<pre>PUSH     2 ,</sub></sup></pre><P>
<pre>POP      0 ,</sub></sup></pre><P>
<pre>MULTIPOP  0 .</sub></sup></pre><P>
Note that the amortized cost of <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> is a constant (0), whereas the actual cost is variable. Here, all three amortized costs are <I>O</I>(l), although in general the amortized costs of the operations under consideration may differ asymptotically.<P>
We shall now show that we can pay for any sequence of stack operations by charging the amortized costs. Suppose we use a dollar bill to represent each unit of cost. We start with an empty stack. Recall the analogy of Section 11.1 between the stack data structure and a stack of plates in a cafeteria. When we push a plate on the stack, we use 1 dollar to pay the actual cost of the push and are left with a credit of 1 dollar (out of the 2 dollars charged), which we put on top of the plate. At any point in time, every plate on the stack has a dollar of credit on it.<P>
The dollar stored on the plate is prepayment for the cost of popping it from the stack. When we execute a <FONT FACE="Courier New" SIZE=2>POP</FONT> operation, we charge the operation nothing and pay its actual cost using the credit stored in the stack. To pop a plate, we take the dollar of credit off the plate and use it to pay the actual cost of the operation. Thus, by charging the <FONT FACE="Courier New" SIZE=2>PUSH</FONT> operation a little bit more, we needn't charge the <FONT FACE="Courier New" SIZE=2>POP</FONT> operation anything.<P>
Moreover, we needn't charge <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operations anything either. To pop the first plate, we take the dollar of credit off the plate and use it to pay the actual cost of a <FONT FACE="Courier New" SIZE=2>POP</FONT> operation. To pop a second plate, we again have a dollar of credit on the plate to pay for the <FONT FACE="Courier New" SIZE=2>POP</FONT> operation, and so on. Thus, we have always charged at least enough up front to pay for <FONT FACE="Courier New" SIZE=2>MULTIPOP</FONT> operations. In other words, since each plate on the stack has 1 dollar of credit on it, and the stack always has a nonnegative number of plates, we have ensured that the amount of credit is always nonnegative. Thus, for <I>any</I> 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, the total amortized cost is an upper bound on the total actual cost. Since the total amortized cost is <I>O</I>(<I>n</I>), so is the total actual cost.<P>
<P>







<h2>Incrementing a binary counter</h2><P>
<a name="0844_15d2"><a name="0844_15d3">As another illustration of the accounting method, we analyze the <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operation on a binary counter that starts at zero. As we observed earlier, the running time of this operation is proportional to the number of bits flipped, which we shall use as our cost for this example. Let us once again use a dollar bill to represent each unit of cost (the flipping of a bit in this example).<P>
For the amortized analysis, let us charge an amortized cost of 2 dollars to set a bit to 1. When a bit is set, we use 1 dollar (out of the 2 dollars charged) to pay for the actual setting of the bit, and we place the other dollar on the bit as credit. At any point in time, every 1 in the counter has a dollar of credit on it, and thus we needn't charge anything to reset a bit to 0; we just pay for the reset with the dollar bill on the bit.<P>
The amortized cost of <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> can now be determined. The cost of resetting the bits within the <B>while</B> loop is paid for by the dollars on the bits that are reset. At most one bit is set, in line 6 of <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT>, and therefore the amortized cost of an <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operation is at most 2 dollars. The number of l's in the counter is never negative, and thus the amount of credit is always nonnegative. Thus, for <I>n</I> <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> operations, the total amortized cost is <I>O</I>(<I>n</I>), which bounds the total actual cost.<P>
<P>







<h2><a name="0845_15d6">Exercises<a name="0845_15d6"></h2><P>
<a name="0845_15d7">18.2-1<a name="0845_15d7"><P>
A sequence of stack operations is performed on a stack whose size never exceeds <I>k</I>. After every <I>k</I> operations, a copy of the entire stack is made for backup purposes. Show that the cost of <I>n</I> stack operations, including copying the stack, is <I>O</I>(<I>n</I>) by assigning suitable amortized costs to the various stack operations.<P>
<a name="0845_15d8">18.2-2<a name="0845_15d8"><P>
<a name="0845_15d4">Redo Exercise 18.1-3 using an accounting method of analysis.<P>
<a name="0845_15d9">18.2-3<a name="0845_15d9"><P>
<a name="0845_15d5">Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Show how to implement a counter as a bit vector so that any sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>INCREMENT</FONT> and <FONT FACE="Courier New" SIZE=2>RESET</FONT> operations takes time <I>O</I>(<I>n</I>) on an initially zero counter. (<I>Hint</I>: Keep a pointer to the high-order 1.)<P>
<P>


<P>