Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 79
Текст из файла (страница 79)
One is a stack with the additionaloperation MULTIPOP, which pops several objects at once. The other is a binary counter thatcounts up from 0 by means of the single operation INCREMENT.While reading this chapter, bear in mind that the charges assigned during an amortizedanalysis are for analysis purposes only. They need not and should not appear in the code. If,for example, a credit is assigned to an object x when using the accounting method, there is noneed to assign an appropriate amount to some attribute credit[x] in the code.The insight into a particular data structure gained by performing an amortized analysis canhelp in optimizing the design.
In Section 17.4, for example, we shall use the potential methodto analyze a dynamically expanding and contracting table.17.1 Aggregate analysisIn aggregate analysis, we show that for all n, a sequence of n operations takes worst-casetime T (n) in total. In the worst case, the average cost, or amortized cost, per operation istherefore T (n)/n. Note that this amortized cost applies to each operation, even when there areseveral types of operations in the sequence. The other two methods we shall study in thischapter, the accounting method and the potential method, may assign different amortizedcosts to different types of operations.Stack operationsIn our first example of aggregate analysis, we analyze stacks that have been augmented with anew operation.
Section 10.1 presented the two fundamental stack operations, each of whichtakes O(1) time:PUSH(S, x) pushes object x onto stack S.POP(S) pops the top of stack S and returns the popped object.Since each of these operations runs in O(1) time, let us consider the cost of each to be 1. Thetotal cost of a sequence of n PUSH and POP operations is therefore n, and the actual runningtime for n operations is therefore Θ(n).Now we add the stack operation MULTIPOP(S,k), which removes the k top objects of stack S,or pops the entire stack if it contains fewer than k objects. In the following pseudocode, theoperation STACK-EMPTY returns TRUE if there are no objects currently on the stack, andFALSE otherwise.MULTIPOP(S, k)1 while not STACK-EMPTY(S) and k ≠ 02do POP(S)3k → k - 1Figure 17.1 shows an example of MULTIPOP.Figure 17.1: The action of MULTIPOP on a stack S, shown initially in (a). The top 4 objectsare popped by MULTIPOP(S, 4), whose result is shown in (b).
The next operation isMULTIPOP(S, 7), which empties the stack—shown in (c)—since there were fewer than 7objects remaining.What is the running time of MULTIPOP(S, k) on a stack of s objects? The actual running timeis linear in the number of POP operations actually executed, and thus it suffices to analyzeMULTIPOP in terms of the abstract costs of 1 each for PUSH and POP. The number ofiterations of the while loop is the number min(s, k)of objects popped off the stack.
For eachiteration of the loop, one call is made to POP in line 2. Thus, the total cost of MULTIPOP ismin(s,k), and the actual running time is a linear function of this cost.Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an initially emptystack. The worst-case cost of a MULTIPOP operation in the sequence is O(n), since the stacksize is at most n. The worst-case time of any stack operation is therefore O(n), and hence asequence of n operations costs O(n2), since we may have O(n) MULTIPOP operations costingO(n) each.
Although this analysis is correct, the O(n2) result, obtained by considering theworst-case cost of each operation individually, is not tight.Using aggregate analysis, we can obtain a better upper bound that considers the entiresequence of n operations. In fact, although a single MULTIPOP operation can be expensive,any sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack cancost at most O(n). Why? Each object can be popped at most once for each time it is pushed.Therefore, the number of times that POP can be called on a nonempty stack, including callswithin MULTIPOP, is at most the number of PUSH operations, which is at most n.
For anyvalue of n, any sequence of n PUSH, POP, and MULTIPOP operations takes a total of O(n)time. The average cost of an operation is O(n)/n = O(1). In aggregate analysis, we assign theamortized cost of each operation to be the average cost. In this example, therefore, all threestack operations have an amortized cost of O(1).We emphasize again that although we have just shown that the average cost, and hencerunning time, of a stack operation is O(1), no probabilistic reasoning was involved.
Weactually showed a worst-case bound of O(n) on a sequence of n operations. Dividing this totalcost by n yielded the average cost per operation, or the amortized cost.Incrementing a binary counterAs another example of aggregate analysis, consider the problem of implementing a k-bitbinary counter that counts upward from 0. We use an array A[0 k -1] of bits, wherelength[A] = k, as the counter. A binary number x that is stored in the counter has its lowest-order bit in A[0] and its highest-order bit in A[k - 1], so that.
Initially, x = 0, andthus A[i] = 0 for i = 0, 1, ..., k - 1. To add 1 (modulo 2k) to the value in the counter, we use thefollowing procedure.INCREMENT(A)1 i ← 02 while i < length[A] and A[i] = 13do A[i] ← 04i ← i + 15 if i < length[A]6then A[i] ← 1Figure 17.2 shows what happens to a binary counter as it is incremented 16 times, startingwith the initial value 0 and ending with the value 16. At the start of each iteration of the whileloop in lines 2–4, we wish to add a 1 into position i. If A[i] = 1, then adding 1 flips the bit to 0in position i and yields a carry of 1, to be added into position i + 1 on the next iteration of theloop. Otherwise, the loop ends, and then, if i < k, we know that A[i] = 0, so that adding a 1into position i, flipping the 0 to a 1, is taken care of in line 6. The cost of each INCREMENToperation is linear in the number of bits flipped.Figure 17.2: An 8-bit binary counter as its value goes from 0 to 16 by a sequence of 16INCREMENT operations.
Bits that flip to achieve the next value are shaded. The running costfor flipping bits is shown at the right. Notice that the total cost is never more than twice thetotal number of INCREMENT operations.As with the stack example, a cursory analysis yields a bound that is correct but not tight. Asingle execution of INCREMENT takes time Θ(k) in the worst case, in which array A containsall ′s. Thus, a sequence of n INCREMENT operations on an initially zero counter takes timeO(nk) in the worst case.We can tighten our analysis to yield a worst-case cost of O(n) for a sequence of nINCREMENT's by observing that not all bits flip each time INCREMENT is called.
AsFigure 17.2 shows, A[0] does flip each time INCREMENT is called. The next-highest-orderbit, A[1], flips only every other time: a sequence of n INCREMENT operations on an initiallyzero counter causes A[1] to flip ⌈n/2⌉ times. Similarly, bit A[2] flips only every fourth time,or ⌈n/4⌉ times in a sequence of n INCREMENT's. In general, for i = 0, 1, ..., ⌈lg n⌉, bit A[i]flips ⌈n/2i⌉ times in a sequence of n INCREMENT operations on an initially zero counter.For i > ⌈lg n⌉, bit A[i] never flips at all. The total number of flips in the sequence is thusby equation (A.6). The worst-case time for a sequence of n INCREMENT operations on aninitially zero counter is therefore O(n).
The average cost of each operation, and therefore theamortized cost per operation, is O(n)/n = O(1).Exercises 17.1-1If the set of stack operations included a MULTIPUSH operation, which pushes k items ontothe stack, would the O(1) bound on the amortized cost of stack operations continue to hold?Exercises 17.1-2Show that if a DECREMENT operation were included in the k-bit counter example, noperations could cost as much as Θ(nk) time.Exercises 17.1-3A sequence of n operations is performed on a data structure. The ith operation costs i if i is anexact power of 2, and 1 otherwise.
Use aggregate analysis to determine the amortized cost peroperation.17.2 The accounting methodIn the accounting method of amortized analysis, we assign differing charges to differentoperations, with some operations charged more or less than they actually cost. The amount wecharge an operation is called its amortized cost. When an operation's amortized cost exceedsits actual cost, the difference is assigned to specific objects in the data structure as credit.Credit can be used later on to help pay for operations whose amortized cost is less than theiractual cost.
Thus, one can view the amortized cost of an operation as being split between itsactual cost and credit that is either deposited or used up. This method is very different fromaggregate analysis, in which all operations have the same amortized cost.One must choose the amortized costs of operations carefully. If we want analysis withamortized costs to show that in the worst case the average cost per operation is small, the totalamortized cost of a sequence of operations must be an upper bound on the total actual cost ofthe sequence. Moreover, as in aggregate analysis, this relationship must hold for all sequencesof operations. If we denote the actual cost of the ith operation by ci and the amortized cost ofthe ith operation by , we require(17.1)for all sequences of n operations.
The total credit stored in the data structure is the differencebetween the total amortized cost and the total actual cost, or. By inequality(17.1), the total credit associated with the data structure must be nonnegative at all times. Ifthe total credit were ever allowed to become negative (the result of undercharging earlyoperations with the promise of repaying the account later on), then the total amortized costsincurred at that time would be below the total actual costs incurred; for the sequence ofoperations up to that time, the total amortized cost would not be an upper bound on the totalactual cost. Thus, we must take care that the total credit in the data structure never becomesnegative.Stack operationsTo illustrate the accounting method of amortized analysis, let us return to the stack example.Recall that the actual costs of the operations werePUSH1,POP1,MULTIPOP min(k, s) ,where k is the argument supplied to MULTIPOP and s is the stack size when it is called.
Letus assign the following amortized costs:PUSH2,POP0,MULTIPOP 0.Note that the amortized cost of MULTIPOP is a constant (0), whereas the actual cost isvariable. Here, all three amortized costs are O(1), although in general the amortized costs ofthe operations under consideration may differ asymptotically.We shall now show that we can pay for any sequence of stack operations by charging theamortized costs.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
