Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 81
Текст из файла (страница 81)
Since Φ(D0) = b0 and Φ(Dn) = bn, the total actual cost of nINCREMENT operations isNote in particular that since b0 ≤ k, as long as k = O(n), the total actual cost is O(n). In otherwords, if we execute at least n = Ω(k) INCREMENT operations, the total actual cost is O(n),no matter what initial value the counter contains.Exercises 17.3-1Suppose we have a potential function Φ such that Φ(Di) ≥ Φ(D0) for all i, but Φ(D0) ≠ = 0.Show that there exists a potential function Φ′ such that Φ′(D0) = 0, Φ′(Di) ≥ 0 for all i ≥ 1, andthe amortized costs using Φ′ are the same as theamortized costs using Φ.Exercises 17.3-2Redo Exercise 17.1-3 using a potential method of analysis.Exercises 17.3-3Consider an ordinary binary min-heap data structure with n elements that supports theinstructions INSERT and EXTRACT-MIN in O(lg n) worst-case time.
Give a potentialfunction Φ such that the amortized cost of INSERT is O(lg n) and the amortized cost ofEXTRACT-MIN is O(1), and show that it works.Exercises 17.3-4What is the total cost of executing n of the stack operations PUSH, POP, and MULTIPOP,assuming that the stack begins with s0 objects and finishes with sn objects?Exercises 17.3-5Suppose that a counter begins at a number with b 1's in its binary representation, rather than at0.
Show that the cost of performing n INCREMENT operations is O(n) if n = Ω(b). (Do notassume that b is constant.)Exercises 17.3-6Show how to implement a queue with two ordinary stacks (Exercise 10.1-6) so that theamortized cost of each ENQUEUE and each DEQUEUE operation is O(1).Exercises 17.3-7Design a data structure to support the following two operations for a set S of integers:INSERT(S, x) inserts x into set S.DELETE-LARGER-HALF(S) deletes the largest ⌈S/2⌉ elements from S.Explain how to implement this data structure so that any sequence of m operations runs inO(m) time.17.4 Dynamic tablesIn some applications, we do not know in advance how many objects will be stored in a table.We might allocate space for a table, only to find out later that it is not enough.
The table mustthen be reallocated with a larger size, and all objects stored in the original table must becopied over into the new, larger table. Similarly, if many objects have been deleted from thetable, it may be worthwhile to reallocate the table with a smaller size. In this section, we studythis problem of dynamically expanding and contracting a table. Using amortized analysis, weshall show that the amortized cost of insertion and deletion is only O(1), even though theactual cost of an operation is large when it triggers an expansion or a contraction.
Moreover,we shall see how to guarantee that the unused space in a dynamic table never exceeds aconstant fraction of the total space.We assume that the dynamic table supports the operations TABLE-INSERT and TABLEDELETE. TABLE-INSERT inserts into the table an item that occupies a single slot, that is, aspace for one item. Likewise, TABLE-DELETE can be thought of as removing an item fromthe table, thereby freeing a slot. The details of the data-structuring method used to organizethe table are unimportant; we might use a stack (Section 10.1), a heap (Chapter 6), or a hashtable (Chapter 11). We might also use an array or collection of arrays to implement objectstorage, as we did in Section 10.3.We shall find it convenient to use a concept introduced in our analysis of hashing (Chapter11).
We define the load factor α (T) of a nonempty table T to be the number of items stored inthe table divided by the size (number of slots) of the table. We assign an empty table (onewith no items) size 0, and we define its load factor to be 1. If the load factor of a dynamictable is bounded below by a constant, the unused space in the table is never more than aconstant fraction of the total amount of space.We start by analyzing a dynamic table in which only insertions are performed.
We thenconsider the more general case in which both insertions and deletions are allowed.17.4.1 Table expansionLet us assume that storage for a table is allocated as an array of slots. A table fills up when allslots have been used or, equivalently, when its load factor is 1.[1] In some softwareenvironments, if an attempt is made to insert an item into a full table, there is no alternativebut to abort with an error.
We shall assume, however, that our software environment, likemany modern ones, provides a memory-management system that can allocate and free blocksof storage on request. Thus, when an item is inserted into a full table, we can expand the tableby allocating a new table with more slots than the old table had. Because we always need thetable to reside in contiguous memory, we must allocate a new array for the larger table andthen copy items from the old table into the new table.A common heuristic is to allocate a new table that has twice as many slots as the old one.
Ifonly insertions are performed, the load factor of a table is always at least 1/2, and thus theamount of wasted space never exceeds half the total space in the table.In the following pseudocode, we assume that T is an object representing the table. The fieldtable[T] contains a pointer to the block of storage representing the table. The field num[T]contains the number of items in the table, and the field size[T] is the total number of slots inthe table. Initially, the table is empty: num[T] = size[T ] = 0.TABLE-INSERT (T , x)1 if size[T ] = 02then allocate table[T] with 1 slot3size[T] ← 14 if num[T] = size[T]5then allocate new-table with 2 · size[T] slots6insert all items in table[T] into new-table7free table[T]8table[T] → new-table9size[T] → 2 · size[T]10 insert x into table[T]11 num[T] → num[T] + 1Notice that we have two "insertion" procedures here: the TABLE-INSERT procedure itselfand the elementary insertion into a table in lines 6 and 10.
We can analyze the running timeof TABLE-INSERT in terms of the number of elementary insertions by assigning a cost of 1to each elementary insertion. We assume that the actual running time of TABLE-INSERT islinear in the time to insert individual items, so that the overhead for allocating an initial tablein line 2 is constant and the overhead for allocating and freeing storage in lines 5 and 7 isdominated by the cost of transferring items in line 6.
We call the event in which the thenclause in lines 5–9 is executed an expansion.Let us analyze a sequence of n TABLE-INSERT operations on an initially empty table. Whatis the cost ci of the ith operation? If there is room in the current table (or if this is the firstoperation), then ci = 1, since we need only perform the one elementary insertion in line 10. Ifthe current table is full, however, and an expansion occurs, then ci = i: the cost is 1 for theelementary insertion in line 10 plus i - 1 for the items that must be copied from the old table tothe new table in line 6.
If n operations are performed, the worst-case cost of an operation isO(n), which leads to an upper bound of O(n2) on the total running time for n operations.This bound is not tight, because the cost of expanding the table is not borne often in thecourse of n TABLE-INSERT operations. Specifically, the ith operation causes an expansiononly when i - 1 is an exact power of 2. The amortized cost of an operation is in fact O(1), aswe can show using aggregate analysis. The cost of the ith operation isThe total cost of n TABLE-INSERT operations is thereforesince there are at most n operations that cost 1 and the costs of the remaining operations forma geometric series. Since the total cost of n TABLE-INSERT operations is 3n, the amortizedcost of a single operation is 3.By using the accounting method, we can gain some feeling for why the amortized cost of aTABLE-INSERT operation should be 3.
Intuitively, each item pays for 3 elementaryinsertions: inserting itself in the current table, moving itself when the table is expanded, andmoving another item that has already been moved once when the table is expanded. Forexample, suppose that the size of the table is m immediately after an expansion. Then, thenumber of items in the table is m/2, and the table contains no credit. We charge 3 dollars foreach insertion. The elementary insertion that occurs immediately costs 1 dollar.
Anotherdollar is placed as credit on the item inserted. The third dollar is placed as credit on one of them/2 items already in the table. Filling the table requires m/2 - 1 additional insertions, and thus,by the time the table contains m items and is full, each item has a dollar to pay for itsreinsertion during the expansion.The potential method can also be used to analyze a sequence of n TABLE-INSERToperations, and we shall use it in Section 17.4.2 to design a TABLE-DELETE operation thathas O(1) amortized cost as well. We start by defining a potential function Φ that is 0immediately after an expansion but builds to the table size by the time the table is full, so thatthe next expansion can be paid for by the potential.
The function(17.5)is one possibility. Immediately after an expansion, we have num[T] = size[T]/2, and thus Φ(T)= 0, as desired. Immediately before an expansion, we have num[T] = size[T], and thus Φ(T) =num[T], as desired. The initial value of the potential is 0, and since the table is always at leasthalf full, num[T] ≥ size[T]/2, which implies that Φ(T) is always nonnegative. Thus, the sum ofthe amortized costs of n TABLE-INSERT operations is an upper bound on the sum of theactual costs.To analyze the amortized cost of the ith TABLE-INSERT operation, we let numi denote thenumber of items stored in the table after the ith operation, sizei denote the total size of thetable after the ith operation, and Φi denote the potential after the ith operation. Initially, wehave num0 = 0, size0 = 0, and Φ0 = 0.If the ith TABLE-INSERT operation does not trigger an expansion, then we have sizei = sizei1 and the amortized cost of the operation is= ci + Φi - Φi-1= 1 + (2 · numi -sizei) - (2 · numi-1 -sizei-1)= 1 + (2 · numi -sizei) - (2(numi -1) - sizei)= 3.If the ith operation does trigger an expansion, then we have sizei = 2 · sizei-1 and sizei-1 = numi1 = numi-1, which implies that sizei = 2 · (numi-1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
