chap18.htm

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

<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif">     </FONT>the amortized cost of a table operation is bounded above by a constant.<P>
<img src="371_a.gif"><P>
<h4><a name="084c_15f1">Figure 18.3 The effect of a sequence of n <FONT FACE="Courier New" SIZE=2>TABLE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT></FONT></FONT> operations on the number num<SUB>i</SUB> of items in the table, the number size<SUB>i</SUB> of slots in the table, and the potential <img src="../images/phicap12.gif"><SUB>i </SUB> = 2 <img src="../images/dot10.gif"> num<SUB>i</SUB> - size<SUB>i</SUB>, each being measured after the ith operation. The thin line shows num<SUB>i</SUB>, the thick line shows size<SUB>i</SUB>, and the dashed line shows <img src="../images/phicap12.gif"><SUB>i</SUB>. Notice that immediately before an expansion, the potential has built up to the number of items in the table, and therefore it can pay for moving all the items to the new table. Afterwards, the potential drops to 0, but it is immediately increased by 2 when the item that caused the expansion is inserted.<a name="084c_15f1"></sub></sup></h4><P>
We assume that cost can be measured in terms of elementary insertions and deletions.<P>
A natural strategy for expansion and contraction is to double the table size when an item is inserted into a full table and halve the size when a deletion would cause the table to become less than half full. This strategy guarantees that the load factor of the table never drops below 1/2, but unfortunately, it can cause the amortized cost of an operation to be quite large. Consider the following scenario. We perform <I>n</I> operations on a table <I>T</I>, where <I>n</I> is an exact power of 2. The first <I>n/2</I> operations are insertions, which by our previous analysis cost a total of <img src="../images/phicap12.gif"> (<I>n</I>). At the end of this sequence of insertions, <I>num</I>[<I>T</I>]<I> = size</I>[<I>T</I>]<I> = n/2.</I> For the second <I>n/2</I> operations, we perform the following sequence:<P>
<pre>I, D, D, I, I, D, D, I, I,... ,</sub></sup></pre><P>
where I stands for an insertion and D stands for a deletion. The first insertion causes an expansion of the table to size <I>n</I>. The two following deletions cause a contraction of the table back to size <I>n/2</I>. Two further insertions cause another expansion, and so forth. The cost of each expansion and contraction is <img src="../images/bound.gif">(<I>n</I>), and there are <img src="../images/bound.gif">(<I>n</I>) of them. Thus, the total cost of the <I>n</I> operations is <img src="../images/bound.gif">(<I>n<SUP>2</I></SUP>), and the amortized cost of an operation is <img src="../images/bound.gif">(<I>n</I>).<P>
<a name="084c_15ec">The difficulty with this strategy is obvious: after an expansion, we do not perform enough deletions to pay for a contraction. Likewise, after a contraction, we do not perform enough insertions to pay for an expansion.<P>
We can improve upon this strategy by allowing the load factor of the table to drop below 1/2. Specifically, we continue to double the table size when an item is inserted into a full table, but we halve the table size when a deletion causes the table to become less than 1/4 full, rather than 1/2 full as before. The load factor of the table is therefore bounded below by the constant 1/4. The idea is that after an expansion, the load factor of the table is 1/2. Thus, half the items in the table must be deleted before a contraction can occur, since contraction does not occur unless the load factor would fall below 1/4. Likewise, after a contraction, the load factor of the table is also 1/2. Thus, the number of items in the table must be doubled by insertions before an expansion can occur, since expansion occurs only when the load factor would exceed 1.<P>
<a name="084c_15ed">We omit the code for <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>, since it is analogous to T<FONT FACE="Courier New" SIZE=2>ABLE-</FONT><FONT FACE="Courier New" SIZE=2>INSERT</FONT>. It is convenient to assume for analysis, however, that if the number of items in the table drops to 0, the storage for the table is freed. That is, if <I>num</I>[<I>T</I>] = 0, then <I>size</I>[<I>T</I>] = 0.<P>
<a name="084c_15ee"><a name="084c_15ef">We can now use the potential method to analyze the cost of a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> operations. We start by defining a potential function <img src="../images/phicap12.gif"> that is 0 immediately after an expansion or contraction and builds as the load factor increases to 1 or decreases to 1/4. Let us denote the load factor of a nonempty table <I>T</I> by <img src="../images/alpha12.gif">(<I>T</I>) = <I>num</I>[<I>T</I>]<I>/size</I>[<I>T</I>]<I>.</I> Since for an empty table, <I>num</I>[<I>T</I>] = <I>size</I>[<I>T</I>] = 0 and <img src="../images/alpha12.gif">[<I>T</I>] = 1, we always have <I>num</I>[<I>T</I>] = <img src="../images/alpha12.gif">(<I>T</I>) <img src="../images/dot10.gif"><I> size</I>[<I>T</I>], whether the table is empty or not. We shall use as our potential function<P>
<img src="372_a.gif"><P>
<h4><a name="084c_15f2">(18.5)<a name="084c_15f2"></sub></sup></h4><P>
Observe that the potential of an empty table is 0 and that the potential is never negative. Thus, the total amortized cost of a sequence of operations with respect to <img src="../images/phicap12.gif"> is an upper bound on their actual cost.<P>
Before proceeding with a precise analysis, we pause to observe some properties of the potential function. Notice that when the load factor is 1/2, the potential is 0. When it is 1, we have <I>size</I>[<I>T</I>]<I> = num</I>[<I>T</I>]<I>, </I> which implies <img src="../images/phicap12.gif"><I>(T) = num</I>[<I>T</I>]<I>,</I> and thus the potential can pay for an expansion if an item is inserted. When the load factor is 1/4, we have <I>size</I>[<I>T</I>]<I> = 4 </I><img src="../images/dot10.gif"><I> num</I>[<I>T</I>]<I> ,</I> which implies <img src="../images/phicap12.gif">(<I>T</I>)<I> = num</I>[<I>T</I>]<I>,</I> and thus the potential can pay for a contraction if an item is deleted. Figure 18.4 illustrates how the potential behaves for a sequence of operations.<P>
To analyze a sequence of <I>n</I> <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> operations, we let <I>c<SUB>i</I></SUB> denote the actual cost of the <I>i</I>th operation, <img src="372_b.gif"> denote its amortized cost with respect to <img src="../images/phicap12.gif">, <I>num<SUB>i</I></SUB> denote the number of items stored in the table after the <I>i</I>th operation, <I>size<SUB>i</I></SUB> denote the total size of the table after the <I>i</I>th operation, <img src="../images/alpha12.gif"> <I><SUB>i</I></SUB> denote the load factor of the table after the <I>i</I>th operation, and <img src="../images/phicap12.gif"><I><SUB>i</I></SUB> denote the potential after the <I>i</I>th operation. Initially, <I>num</I><SUB>0</SUB><I> = </I>0<I>, size</I><SUB>0</SUB> = 0, <img src="../images/alpha12.gif"><SUB>0</SUB> = 1, and <img src="../images/phicap12.gif"><SUB>0</SUB> = 0.<P>
<img src="373_a.gif"><P>
<h4><a name="084c_15f3">Figure 18.4 The effect of a sequence of n <FONT FACE="Courier New" SIZE=2>TABLE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT></FONT></FONT> and <FONT FACE="Courier New" SIZE=2>TABLE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT></FONT></FONT> operations on the number num<SUB>i</SUB> of items in the  table, the number size<SUB>i</SUB> of slots in the table, and the potential<a name="084c_15f3"></sub></sup></h4><P>
<img src="373_b.gif"><P>
<h4>each being measured after the ith operation. The thin line shows num<SUB>i</SUB>, the thick line shows size<SUB>i</SUB>, and the dashed line shows <img src="../images/phicap12.gif"><SUB>i</SUB>. Notice that immediately before an expansion, the potential has built up to the number of items in the table, and therefore it can pay for moving all the items to the new table. Likewise, immediately before a contraction, the potential has built up to the number of items in the table.</sub></sup></h4><P>
We start with the case in which the <I>i</I>th operation is <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>. If <img src="../images/alpha12.gif"><I><SUB>i-</I>1</SUB><img src="../images/gteq.gif"><I> </I>1/2<I>,</I> the analysis is identical to that for table expansion in Section 18.4.1. Whether the table expands or not, the amortized cost <img src="373_c.gif"> of the operation is at most 3. If <img src="../images/alpha12.gif"><I><SUB>i-</I>1</SUB> &lt; 1/2, the table cannot expand as a result of the operation, since expansion occurs only when <img src="../images/alpha12.gif"><I><SUB>i-</I>1 </SUB>= 1. If <img src="../images/alpha12.gif"><I><SUB>i</I></SUB> &lt; 1/2 as well, then the amortized cost of the <I>i</I>th operation is<P>
<img src="373_d.gif"><P>
<pre>If <img src="../images/alpha12.gif"><I><SUB>i-</I>1</SUB> &lt; 1/2 but <img src="../images/alpha12.gif"><I><SUB>i</I></SUB> <img src="../images/gteq.gif"> 1/2, then</sub></sup></pre><P>
<img src="373_e.gif"><P>
<img src="374_a.gif"><P>
Thus, the amortized cost of a <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation is at most 3.<P>
We now turn to the case in which the <I>i</I>th operation is <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. In this case, <I>num<SUB>i</I></SUB> = <I>num<SUB>i-</I>1</SUB> - 1. If <img src="../images/alpha12.gif"><I><SUB>i-</I>1</SUB><I> </I>&lt;<I> </I>1/2, then we must consider whether the operation causes a contraction. If it does not, the<I>n size<SUB>i = </SUB>size<SUB>i-</I>1</SUB> and the amortized cost of the operation is<P>
<img src="374_b.gif"><P>
If <img src="../images/alpha12.gif"><I><SUB>i-</I>1</SUB> &lt; 1/2 and the <I>i</I>th operation does trigger a contraction, then the actual cost of the operation is <I>c<SUB>i</I></SUB> = <I>num<SUB>i</I></SUB> + 1, since we delete one item and move <I>num<SUB>i</I></SUB> items. We have <I>size<SUB>i</I></SUB>/2 = <I>size<SUB>i</I>-1</SUB>/4 = <I>num<SUB>i</I></SUB> + 1, and the amortized cost of the operation is<P>
<img src="374_c.gif"><P>
When the <I>i</I>th operation is a <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> and <img src="../images/alpha12.gif"><I><SUB>i</I>-1 </SUB><img src="../images/gteq.gif"> 1/2, the amortized cost is also bounded above by a constant. The analysis is left as Exercise 18.4-3.<P>
In summary, since the amortized cost of each operation is bounded above by a constant, the actual time for any sequence of <I>n</I> operations on a dynamic table is <I>O(n)</I>.<P>
<P>







<h2><a name="084d_15f1">Exercises<a name="084d_15f1"></h2><P>
<a name="084d_15f2">18.4-1<a name="084d_15f2"><P>
Argue intuitively that if <img src="../images/alpha12.gif"><I><SUB>i-</I>1</SUB> <img src="../images/lteq12.gif"> 1/2 and <img src="../images/alpha12.gif"><I><SUB>i</I></SUB> <img src="../images/lteq12.gif"> 1/2, then the amortized cost of a <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation is 0.<P>
<a name="084d_15f3">18.4-2<a name="084d_15f3"><P>
<a name="084d_15f0">Suppose that we wish to implement a dynamic, open-address hash table. Why might we consider the table to be full when its load factor reaches some value <img src="../images/alpha12.gif"> that is strictly less than 1? Describe briefly how to make insertion into a dynamic, open-address hash table run in such a way that the expected value of the amortized cost per insertion is <I>O</I>(1). Why is the expected value of the actual cost per insertion not necessarily <I>O</I>(1) for all insertions?<P>
<a name="084d_15f4">18.4-3<a name="084d_15f4"><P>
Show that if the <I>i</I>th operation on a dynamic table is <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> and <img src="../images/alpha12.gif"><I><SUB>i-</I>1</SUB> <img src="../images/gteq.gif"> 1/2, then the amortized cost of the operation with respect to the potential function (18.5) is bounded above by a constant.<P>
<a name="084d_15f5">18.4-4<a name="084d_15f5"><P>
Suppose that instead of contracting a table by halving its size when its load factor drops below 1/4, we contract it by multiplying its size by 2/3 when its load factor drops below 1/3. Using the potential function<P>
<pre><img src="../images/phicap12.gif">(<I>T</I>) = |2 <img src="../images/dot10.gif"> <I>num</I>[<I>T</I>] - <I>size</I>[<I>T</I>]| <B>,</B></sub></sup></pre><P>
show that the amortized cost of a <FONT FACE="Courier New" SIZE=2>TABLE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> that uses this strategy is bounded above by a constant.<P>
<P>


<P>







<h1><a name="084e_15fc">Problems<a name="084e_15fc"></h1><P>
<a name="084e_15fd">18-1     Bit-reversed binary counter<a name="084e_15fd"><P>
<a name="084e_15f1"><a name="084e_15f2"><a name="084e_15f3"><a name="084e_15f4"><a name="084e_15f5">Chapter 32 examines an important algorithm called the Fast Fourier Transform, or FFT. The first step of the FFT algorithm performs a <I><B>bit-reversal permutation </I></B>on an input array <I>A</I>[0 . . n - 1] whose length is <I>n</I> = 2<I><SUP>k</I></SUP> for some nonnegative integer <I>k</I>. This permutation swaps elements whose indices have binary representations that are the reverse of each other.<P>
We can express each index <I>a</I> as a <I>k</I>-bit sequence <img src="../images/lftwdchv.gif"><I>a<SUB>k-</I>1</SUB>, <I>a<SUB>k-2</I></SUB>, . . . , <I>a</I><SUB>0</SUB><img src="../images/wdrtchv.gif">, where <img src="375_a.gif">. We define<P>
<pre>rev<I><SUB>k</I></SUB>(<img src="../images/lftwdchv.gif"><I>a<SUB>k-</I>1</SUB>, <I>a<SUB>k-2</I></SUB>,..., <I>a</I><SUB>0</SUB><img src="../images/wdrtchv.gif">) = (<img src="../images/lftwdchv.gif"><I>a</I><SUB>0, </SUB><I>a</I><SUB>1</SUB>,..., <I>a<SUB>k-</I>1</SUB><img src="../images/wdrtchv.gif"> ;</sub></sup></pre><P>
thus,<P>
<img src="375_b.gif"><P>
For example, if <I>n</I> = 16 (or, equivalently, <I>k</I> = 4), then rev<I><SUB>k</I></SUB>(3) = 12, since the 4-bit representation of 3 is 0011, which when reversed gives 1100, the 4-bit representation of 12.<P>
<I><B>a.     </I></B>Given a function rev<I><SUB>k</I><