Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 82
Текст из файла (страница 82)
Thus, the amortized cost of the operation is= ci + Φi - Φi-1= numi + (2 · numi - sizei) - (2 · numi-1 - sizei-1)= numi +(2 · numi -2 · (numi - 1)) - (2(numi - 1) - (numi - 1))= numi + 2 - (numi - 1)= 3.Figure 17.3 plots the values of numi, sizei, and Φi against i. Notice how the potential builds topay for the expansion of the table.Figure 17.3: The effect of a sequence of n TABLE-INSERT operations on the number numi ofitems in the table, the number sizei of slots in the table, and the potential Φi = 2·numi - sizei,each being measured after the ith operation.
The thin line shows numi, the dashed line showssizei, and the thick line shows Φi. Notice that immediately before an expansion, the potentialhas built up to the number of items in the table, and therefore it can pay for moving all theitems to the new table. Afterwards, the potential drops to 0, but it is immediately increased by2 when the item that caused the expansion is inserted.17.4.2 Table expansion and contractionTo implement a TABLE-DELETE operation, it is simple enough to remove the specified itemfrom the table. It is often desirable, however, to contract the table when the load factor of thetable becomes too small, so that the wasted space is not exorbitant. Table contraction isanalogous to table expansion: when the number of items in the table drops too low, weallocate a new, smaller table and then copy the items from the old table into the new one.
Thestorage for the old table can then be freed by returning it to the memory-management system.Ideally, we would like to preserve two properties:••the load factor of the dynamic table is bounded below by a constant, andthe amortized cost of a table operation is bounded above by a constant.We assume that cost can be measured in terms of elementary insertions and deletions.A natural strategy for expansion and contraction is to double the table size when an item isinserted into a full table and halve the size when a deletion would cause the table to becomeless than half full.
This strategy guarantees that the load factor of the table never drops below1/2, but unfortunately, it can cause the amortized cost of an operation to be quite large.Consider the following scenario. We perform n operations on a table T , where n is an exactpower of 2. The first n/2 operations are insertions, which by our previous analysis cost a totalof Φ(n). At the end of this sequence of insertions, num[T] = size[T] = n/2. For the second n/2operations, we perform the following sequence:I, D, D, I, I, D, D, I, I, ... ,where I stands for an insertion and D stands for a deletion. The first insertion causes anexpansion of the table to size n.
The two following deletions cause a contraction of the tableback to size n/2. Two further insertions cause another expansion, and so forth. The cost ofeach expansion and contraction is Θ(n), and there are Θ(n) of them. Thus, the total cost of then operations is Θ(n2), and the amortized cost of an operation is Θ(n).The difficulty with this strategy is obvious: after an expansion, we do not perform enoughdeletions to pay for a contraction. Likewise, after a contraction, we do not perform enoughinsertions to pay for an expansion.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, butwe halve the table size when a deletion causes the table to become less than 1/4 full, ratherthan 1/2 full as before.
The load factor of the table is therefore bounded below by the constant1/4. The idea is that after an expansion, the load factor of the table is 1/2. Thus, half the itemsin the table must be deleted before a contraction can occur, since contraction does not occurunless the load factor would fall below 1/4. Likewise, after a contraction, the load factor ofthe table is also 1/2. Thus, the number of items in the table must be doubled by insertionsbefore an expansion can occur, since expansion occurs only when the load factor wouldexceed 1.We omit the code for TABLE-DELETE, since it is analogous to TABLE-INSERT.
It isconvenient 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 num[T] = 0, then size[T] = 0.We can now use the potential method to analyze the cost of a sequence of n TABLE-INSERTand TABLE-DELETE operations. We start by defining a potential function Φ that is 0immediately after an expansion or contraction and builds as the load factor increases to 1 ordecreases to 1/4.
Let us denote the load factor of a nonempty table T by α(T) = num[T]/size[T]. Since for an empty table, num[T] = size[T] = 0 and α[T] = 1, we always have num[T]= α(T) · size[T], whether the table is empty or not. We shall use as our potential function(17.6)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 Φ is an upper bound on theactual cost of the sequence.Before proceeding with a precise analysis, we pause to observe some properties of thepotential function.
Notice that when the load factor is 1/2, the potential is 0. When the loadfactor is 1, we have size[T] = num[T], which implies Φ(T) = num[T], and thus the potentialcan pay for an expansion if an item is inserted. When the load factor is 1/4, we have size[T] =4 · num[T], which implies Φ(T) = num[T], and thus the potential can pay for a contraction ifan item is deleted. Figure 17.4 illustrates how the potential behaves for a sequence ofoperations.Figure 17.4: The effect of a sequence of n TABLE-INSERT and TABLE-DELETE operationson the number numi of items in the table, the number sizei of slots in the table, and thepotentialeach being measured after the ith operation.
The thinline shows numi, the dashed line shows sizei, and the thick line shows Φi. Notice thatimmediately before an expansion, the potential has built up to the number of items in thetable, 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 thetable.To analyze a sequence of n TABLE-INSERT and TABLE-DELETE operations, we let cidenote the actual cost of the ith operation, denote its amortized cost with respect to Φ, numidenote the number of items stored in the table after the ith operation, sizei denote the total sizeof the table after the ith operation, αi denote the load factor of the table after the ith operation,and Φi denote the potential after the ith operation.
Initially, num0 = 0, size0 = 0, α0 = 1, and Φ0= 0.We start with the case in which the ith operation is TABLE-INSERT. The analysis is identicalto that for table expansion in Section 17.4.1 if αi-1 ≥ 1/2. Whether the table expands or not, theamortized cost of the operation is at most 3. If αi-1 < 1/2, the table cannot expand as a resultof the operation, since expansion occurs only when αi-1 = 1. If αi < 1/2 as well, then theamortized cost of the ith operation is= ci + Φi - Φi-1= 1 + (sizei/2 - numi) - (sizei-1/2 - numi-1)= 1 + (sizei/2 - numi) - (sizei/2 - (numi - 1))= 0.If αi-1 < 1/2 but αi ≥ 1/2, then= ci+Φi-Φi-1= 1 + (2 · numi - sizei) - (sizei-1 /2 - numi-1)= 1 + (2(numi-1 +1) - sizei-1) - (sizei-1/2 - numi-1)= 3 · numi-1 - 3/2; sizei-1 +3= 3αi-1 sizei-1 - 3/2 sizei-1 +3< 3/2 sizei-1 - 3/2 sizei-1 +3= 3.Thus, the amortized cost of a TABLE-INSERT operation is at most 3.We now turn to the case in which the ith operation is TABLE-DELETE.
In this case, numi =numi-1 -1. If ai-1 < 1/2, then we must consider whether the operation causes a contraction. If itdoes not, then sizei = sizei-1 and the amortized cost of the operation is= ci + Φi - Φi-1= 1 + (sizei /2 - numi) - (sizei-1 /2 - numi-1)= 1 + (sizei /2 - numi) - (sizei /2 - (numi +1))= 2.If αi-1 < 1/2 and the ith operation does trigger a contraction, then the actual cost of theoperation is ci = numi +1, since we delete one item and move numi items. We have sizei/2 =sizei-1/4 = numi-1 = numi +1, and the amortized cost of the operation is= ci + Φi - Φi-1= (numi +1) + (sizei/2 - numi) (sizei-1/2 - numi-1) = (numi +1) + ((numi +1) - numi) - ((2 ·numi +2) - (numi +1))= 1.When the ith operation is a TABLE-DELETE and αi-1 ≥ 1/2, the amortized cost is alsobounded above by a constant.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
