Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 80
Текст из файла (страница 80)
Suppose we use a dollar bill to represent each unit of cost. We start with anempty stack. Recall the analogy of Section 10.1 between the stack data structure and a stackof plates in a cafeteria. When we push a plate on the stack, we use 1 dollar to pay the actualcost of the push and are left with a credit of 1 dollar (out of the 2 dollars charged), which weput on top of the plate. At any point in time, every plate on the stack has a dollar of credit onit.The dollar stored on the plate is prepayment for the cost of popping it from the stack. Whenwe execute a POP operation, we charge the operation nothing and pay its actual cost using thecredit stored in the stack.
To pop a plate, we take the dollar of credit off the plate and use it topay the actual cost of the operation. Thus, by charging the PUSH operation a little bit more,we needn't charge the POP operation anything.Moreover, we needn't charge MULTIPOP 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 POP operation.To pop a second plate, we again have a dollar of credit on the plate to pay for the POPoperation, and so on. Thus, we have always charged enough up front to pay for MULTIPOPoperations.
In other words, since each plate on the stack has 1 dollar of credit on it, and thestack always has a nonnegative number of plates, we have ensured that the amount of credit isalways nonnegative. Thus, for any sequence of n PUSH, POP, and MULTIPOP operations,the total amortized cost is an upper bound on the total actual cost.
Since the total amortizedcost is O(n), so is the total actual cost.Incrementing a binary counterAs another illustration of the accounting method, we analyze the INCREMENT operation ona binary counter that starts at zero. As we observed earlier, the running time of this operationis 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 thisexample).For the amortized analysis, let us charge an amortized cost of 2 dollars to set a bit to 1.
Whena 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 to be used later when we flip the bit back to0. At any point in time, every 1 in the counter has a dollar of credit on it, and thus we needn'tcharge anything to reset a bit to 0; we just pay for the reset with the dollar bill on the bit.The amortized cost of INCREMENT can now be determined.
The cost of resetting the bitswithin the while loop is paid for by the dollars on the bits that are reset. At most one bit is set,in line 6 of INCREMENT, and therefore the amortized cost of an INCREMENT operation isat most 2 dollars. The number of 1's in the counter is never negative, and thus the amount ofcredit is always nonnegative. Thus, for n INCREMENT operations, the total amortized cost isO(n), which bounds the total actual cost.Exercises 17.2-1A sequence of stack operations is performed on a stack whose size never exceeds k.
Afterevery k operations, a copy of the entire stack is made for backup purposes. Show that the costof n stack operations, including copying the stack, is O(n) by assigning suitable amortizedcosts to the various stack operations.Exercises 17.2-2Redo Exercise 17.1-3 using an accounting method of analysis.Exercises 17.2-3Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bitsin it 0). Show how to implement a counter as an array of bits so that any sequence of nINCREMENT and RESET operations takes time O(n) on an initially zero counter. (Hint:Keep a pointer to the high-order 1.)17.3 The potential methodInstead of representing prepaid work as credit stored with specific objects in the datastructure, the potential method of amortized analysis represents the prepaid work as "potentialenergy," or just "potential," that can be released to pay for future operations.
The potential isassociated with the data structure as a whole rather than with specific objects within the datastructure.The potential method works as follows. We start with an initial data structure D0 on which noperations are performed. For each i = 1, 2, ..., n, we let ci be the actual cost of the ithoperation and Di be the data structure that results after applying the ith operation to datastructure Di-1. A potential function Φ maps each data structure Di to a real number Φ(Di),which is the potential associated with data structure Di. The amortized cost of the ithoperation with respect to potential function Φ is defined by(17.2)The amortized cost of each operation is therefore its actual cost plus the increase in potentialdue to the operation. By equation (17.2), the total amortized cost of the n operations is(17.3)The second equality follows from equation (A.9), since the Φ(Di) terms telescope.If we can define a potential function Φ so that Φ(Dn) ≥ Φ(D0), then the total amortized costis an upper bound on the total actual cost.
In practice, we do not always know howmany operations might be performed. Therefore, if we require that Φ (Di) ≥ Φ (D0) for all i,then we guarantee, as in the accounting method, that we pay in advance. It is often convenientto define Φ (D0) to be 0 and then to show that Φ (Di) ≥ 0 for all i. (See Exercise 17.3-1 for aneasy way to handle cases in which Φ(D0) ≠ 0.)Intuitively, if the potential difference Φ(Di) - Φ(Di-1) of the ith operation is positive, then theamortized cost represents an overcharge to the ith operation, and the potential of the datastructure increases.
If the potential difference is negative, then the amortized cost representsan undercharge to the ith operation, and the actual cost of the operation is paid by the decreasein the potential.The amortized costs defined by equations (17.2) and (17.3) depend on the choice of thepotential function Φ.
Different potential functions may yield different amortized costs yet stillbe upper bounds on the actual costs. There are often trade-offs that can be made in choosing apotential function; the best potential function to use depends on the desired time bounds.Stack operationsTo illustrate the potential method, we return once again to the example of the stack operationsPUSH, POP, and MULTIPOP. We define the potential function Φ on a stack to be the numberof objects in the stack. For the empty stack D0 with which we start, we have Φ(D0) = 0. Sincethe number of objects in the stack is never negative, the stack Di that results after the ithoperation has nonnegative potential, and thusΦ(Di) ≥ 0= Φ(D0).The total amortized cost of n operations with respect to Φ therefore represents an upper boundon the actual cost.Let us now compute the amortized costs of the various stack operations.
If the ith operation ona stack containing s objects is a PUSH operation, then the potential difference isΦ(Di) - Φ(Di-1) = (s + 1) -s=1By equation (17.2), the amortized cost of this PUSH operation is= ci + Φ(Di) - Φ (Di-1)=1+1=2Suppose that the ith operation on the stack is MULTIPOP(S, k) and that ′ = min(k, s) objectsare popped off the stack. The actual cost of the operation is ′, and the potential difference isΦ(Di) - Φ(Di-1) - -′.Thus, the amortized cost of the MULTIPOP operation is= ci + Φ(Di) - Φ(Di-1)=′-′= 0.Similarly, the amortized cost of an ordinary POP operation is 0.The amortized cost of each of the three operations is O(1), and thus the total amortized cost ofa sequence of n operations is O(n). Since we have already argued that Φ(Di) ≥ Φ(D0), the totalamortized cost of n operations is an upper bound on the total actual cost.
The worst-case costof n operations is therefore O(n).Incrementing a binary counterAs another example of the potential method, we again look at incrementing a binary counter.This time, we define the potential of the counter after the ith INCREMENT operation to be bi, the number of ′s in the counter after the ith operation.Let us compute the amortized cost of an INCREMENT operation. Suppose that the ithINCREMENT operation resets ti bits. The actual cost of the operation is therefore at most ti +1, since in addition to resetting ti bits, it sets at most one bit to 1. If bi = 0, then the ithoperation resets all k bits, and so bi-1 = ti = k.
If bi > 0, then bi = bi-1 - ti + 1. In either case, bi ≤bi-1 - ti + 1, and the potential difference isΦ(Di) - Φ(Di-1) ≤ (bi-1 - ti + 1) - bi-1= 1 - t i.The amortized cost is therefore= ci + Φ(Di) - Φ(Di-1)≤ (ti + 1) + (1 - ti)= 2.If the counter starts at zero, then Φ(D0) = 0. Since Φ(Di) ≥ 0 for all i, the total amortized costof a sequence of n INCREMENT operations is an upper bound on the total actual cost, and sothe worst-case cost of n INCREMENT operations is O(n).The potential method gives us an easy way to analyze the counter even when it does not startat zero. There are initially b0 ′s, and after n INCREMENT operations there are bn 1's, where 0≤ b0, bn ≤ k. (Recall that k is the number of bits in the counter.) We can rewrite equation(17.3) as(17.4)We have ≤ 2 for all 1 ≤ i ≤ n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
