程序代写代做代考 data structure Java algorithm Algorithms and Data

Algorithms and Data
15: Amortized Analysis Professor Kevin Gold

In amortized analysis, we argue that the running time of the worst case

isn’t as bad as it seems, because operations are only infrequently expensive — even in the worst case.

Lots of cheap calls make up for an expensive call
As opposed to finding average case running time, amortized analysis

is still about the worst case, but counts more carefully


If some calls to a method are more expensive than others, it may make sense to try to compute the total work done across N calls, T(N)
Aggregate Analysis and
Amortized Cost
In such “aggregate analysis,” the amortized cost of the

method is the average across all calls, T(N)/N.

But it’s still an upper bound on the work done — as opposed to expected running time, which is the “average” running time people usually talk about
Thinking about amortized cost can avoid big-O bounds

that are too loose.


Multipop, Lazy Analysis
Suppose we have a stack with the usual push and pop

operations.
Push and pop are both O(1) – just change head of list
Now suppose we add “multipop” which is an operation that can pop k items, just by calling pop() k times. This is O(N) in the worst case (everything is in the stack and we pop it all)

So is the worst case time to do N push, pop, and

multipop operations O(N) * O(N) = O(N2)?

Multipop, 
 Aggregate Analysis
Aggregate analysis sums the total operations done over multiple calls The number of pop operations (including in multipop) is bounded by the

(often, N calls) to find the average work done per operation in the worst case

number of push operations.
• • •
• •
So we have at most O(N) pop operations of any kind Combined with O(N) pushes, that’s still O(N) work
So the amortized cost of all of these operations is O(N)/N = O(1). Multipop’s amortized cost is constant.
We expect N calls to take O(N) work, not O(N2).
This is a worst-case bound — no probability involved.


Suppose we’re incrementing a binary number from 0 up to a 
 k-bit number N. How many times do we flip bits?
In a worst case, we flip all k bits in one step (0111..1 becomes 1000…0)

Incrementing a Binary
Counter
So a first pass analysis says the

running time is O(kN) = O(N log N)


Amortized Analysis of
Flipping Bits in the Counter
To the right, the bits highlighted are those that change on the next step
Notice a pattern?
k-1 i ∞ i
Σi=0 (n/2) < n Σi=0 (1/2) = 2n = O(n) N increments take O(N) flips, so the amortized number of flips per increment is O(1). • • • The “Accounting Method” An interesting analysis trick is to actually assign different numbers from the actual costs of operations — “charging” more or less operations than they actually cost. • The algorithm’s “credit” is the amount it has been charged • for operations, minus its actual number of operations. • As long as the algorithm’s credit never goes negative, we can use what we “charged” as a bound on the actual number of operations. For example, we can “prepay” for operations that will • happen later, making analysis easier. The Accounting Method with Multipop Suppose we assign amortized costs of 2 to push, 0 to • pop, 0 to multipop. With push, we essentially “prepay” for the pop or multipop • operation that would remove the element we push. Every sequence of actions we can legally take keeps our • credit positive. • Thinking about the worst case of N push/pop/multipop calls, we get 2N = O(N) operations, or an amortized cost of O(1) operations per call. • An Accounting Method Analysis of Bit-Flipping Let the amortized cost of setting a bit to 1 be 2, and the • cost of flipping it back to 0 be 0. “Prepay” for flipping the bit back Our credit remains positive - bit can’t flip to 0 before it’s 1 Every time there is an increment, we set at most 1 bit to 1 - either the rightmost bit (no carry), or we carry until a bit to the left is set to 1. • • So N increments have an amortized number of flips of 2N = • O(N), matching our analysis from before. • • • Deriving the Potential Method How do we find good amortized costs to charge for ops?
 In analyzing multipop, notice how our costs for the accounting method were 
 Push: 1 + 1 = 2 Pop: 1 - 1 = 0 Multipop: k - k = 0 • The potential method is one way • (true cost) + ((stack elements after op) - (stack elements before op)) Define the potential Φ(s) of a stack to be the number of elements in it. That • represents how many operations we’ve prepaid for. Then our amortized costs can all have the form c + Φ(s’) - Φ(s), where Φ(s’) is • the new potential after the operation and Φ(s) is the old potential. • • • • The Potential Method in General In the potential method, there is some function Φ(s) that takes a data structure involved in the algorithm and returns a non-negative number. Also, Φ(s0) = 0 ... no potential saved up to start. Setting the amortized costs of operations to
 c + Φ(s’) - Φ(s), where c is the true cost, s’ is the data structure after the operation, and s is the data structure before the operation, creates a set of costs that is guaranteed to sum to an upper bound of the true cost. Σi (ci + Φ(si) - Φ(si-1)) = (Σi ci) + Φ(sN) - Φ(s0) ≥ Σi ci “telescoping sum” to true cost and non- negative potential diifference Sum of amortized costs Potential Method for Counting Bit Flips Let the potential Φ(s) be the number of 1’s in the binary • counter. This starts 0 and is non-negative. Suppose increment i resets ti bits to 0. We argued before that The difference in potentials Φ(si) - Φ(si-1) between the previous • there can be at most 1 bit set to 1. • step and the current step is therefore 1 - ti. (gained 1, lost ti) • And the actual work done is ti + 1. So set the amortized cost of increments to (ti + 1) + (1 - ti)= 2, • making the bits flipped for N increments O(N). ArrayList.add() Sometimes Requires ArrayList.size() operations ArrayList allows constant time access to its elements because it’s really an • array “under the hood” But arrays have a fixed size, while ArrayList allows us to Add() arbitrarily many elements? • many elements. So what happens to this array when we try to add too • Memory immediately adjacent to the array is probably being used for other program stuff, and we don’t want to fragment the array (speed issues). We’ve got to ask for a contiguous block of memory and copy all the elements into this bigger array Common choice: copy to an array twice as big. (Java spec is vague) • Copying a whole array is O(N) operations, so it looks at first as if adding N • elements may be O(N2) in the worst case • • • lg N Work for N adds: N + Σ 2j = N + “11111...1” < N + 2N = 3N j=0 So amortized cost of an add() is constant: 3. ArrayList.Add(): Aggregate Analysis Let’s assume we recopy to an array twice the size of the For N elements, the array will double lg N times • current one when we’ve run out of room • The cost of the jth doubling is 2j if we start from size 0 Also, N basic array assignments for N elements • (unlikely start, but this is an upper bound) 1+lg N • • • • • The Three Amortized Operations of Add() Can think about this amortized cost this way — assume we have just • expanded to a size m array and have no “credit” stored up. m/2 elements currently in the array Budgeting 3 operations for each of the next m/2 adds “pays” for: The actual insertion of this element in the array Moving this element once, when the array is expanded again Moving one of the m/2 elements that already used up their “saved credit” on the last move. When the array is doubled, the budgeted costs will match the exact costs • again — no credit left. • The preceding analysis shows how the fullness of the array (“load factor”) can act as a potential function, representing saved up amortized costs • • • Potential Function Analysis of Add() Let Φ(N) = 2N - array.length 0 for N = 0 or array.length == 2N 2N - N = N when array full Amortized cost without an array doubling is then 
 • c + (Φ(s’) - Φ(s)) = (1 + increase potential by 2) = 3 Amortized cost with array doubling because of extra element is
 • c + (Φ(s’) - Φ(s)) = (1 + N) + (lose N potential, then gain 2) = 3 What are These Potential Functions For, Again? We could try the “accounting method” and “prepay” for some operations, but it may not be obvious how to appropriately “cost” operations such that we’re never cheating and paying less than the actual number of operations. Rather than trying to think about sequences of operations remaining net positive, it can be easier to define a function on the data structure that is clearly 0 at first and always non-negative. Then setting the amortized cost of an operation to its true cost plus the change to the potential guarantees that “cheating” never happens in the accounting. We’re about to see a case where a different method would be tough. We had a nice closed-form formula for the amortized cost of add() with our • aggregate analysis, but such exact analysis is hard sometimes. • • • • • Removing Elements From a Growable Array Consider still an ArrayList-like structure If we remove enough elements, maybe we should • move to a smaller array to free up memory Should we move to a smaller array if we drop below • array.length/2 elements? • If we double the array adding element length/2+1 and halve the array on deleting it, we could end up “thrashing” as we add, delete, add, delete, performing Ө(N) copy operations each time. Shrinking at Length/2 Elements is Terrible No amount of amortization saves us from this worst case. • N operations would be Ө(N2). • Amortization only results in lower running times when there is some guarantee the expensive operations are somewhat infrequent, their costs proportional to the work already done. Using Amortization to Think About the Deletion Problem We need to have done enough operations to “pay for” the • contraction of the array. (meaning, change our strategy to make deletion less • relatively frequent) Just after doubling, we had zero potential. There haven’t been • enough operations to “fund” a deletion. Let’s change our potential function so that deletions also • contribute to the “fund” for future expensive ops And change our policy to require a buildup in the “fund” before • downsizing A Potential Function for Dynamic Array Expansion & Contraction Change in policy: shrink array when the number of • elements hits array.length/4 • • • • • Φ(N) = 2N - array.length if N >= array.length/2 Φ(N) = array.length/2 – N if N < array.length/2 Φ(N) = 0 when N = array.length/2 Φ(N) = N when N = array.length Φ(N) = array.length/4 when N = array.length/4 Calculating Amortized Costs of Normal Adds and Deletes Φ(N) = 2N - array.length if N >= array.length/2 Φ(N) = array.length/2 – N if N < array.length/2 Add with N >= array.length/2:
 1 + (2 potential change) = 3
• • •
Add with N < array.length/2:
 Delete with N >= array.length/2:


1 + (-1 potential change) = 0

1 + (-2 potential change) = -1 (we overcharged on the add!)
Delete with N < array.length/2:
 • 1 + (+1 potential change) = 2 Calculating Amortized Costs of the Big Adds and Deletes Φ(N) = 2N - array.length if N >= array.length/2 Φ(N) = array.length/2 – N if N < array.length/2 Add with N = array.length, need to resize up:
 1 + N + (-N+2 potential change) = 3 • • • Remove to get N = array.length/4, resize down:
 • 1 + array.length/4 + (-array.length/4 potential) = 1 • All operations’ amortized costs are bounded by a constant — so add() and delete() are amortized cost O(1) in these growable, shrinkable arrays. Analyzing Splay Trees A splay tree is a binary search tree that shifts This can make accesses for real data very fast, since • elements up to the root whenever they’re accessed. • recently used data tends to be used again soon Splay trees are in the worst case linear time to • access, since they could be totally unbalanced But amortized analysis will show the worst case is • better thought of as O(log n) • and Rotations In a binary search tree node, left.key <= this.key <= right.key Binary Search Trees We can preserve this property while changing which node is the parent of • which in a local area This is called a “rotation” of the tree. If B is A’s parent, make A B’s parent, • handing off A’s child to B if necessary. 4 25 rotate about 2&4 2 4 1 13 35 • the root: • • • Zig, Zig-Zig, Zig-Zag Zig: do this if parent is root. See prev slide, where we “zig” on 2. Zig-Zig: do this if a left-child of a left child, or right child of a right child. Rotate to move parent above grandparent, then rotate above parent. Zig-Zag: otherwise, rotate to move above parent, then rotate to move A splay tree uses the following operations to get an accessed node up to above former grandparent. 4 1 2 251 4 2 4 5 13 Zig-Zig 3 5 3 • the root: • • • Zig, Zig-Zig, Zig-Zag Zig: do this if parent is root. See prev slide, where we “zig” on 2. Zig-Zig: do this if a left-child of a left child, or right child of a right child. Rotate to move parent above grandparent, then rotate above parent. Zig-Zag: otherwise, rotate to move above parent, then rotate to move A splay tree uses the following operations to get an accessed node up to above former grandparent. 4 25 4 35 2 3 24 13 Zig-Zag 1 15 Some Splay Tree Operations Splay node: zig, zig-zig, or zig-zag until a node is • at the root. Access node: Binary search down tree, then splay • accessed node. Insert node: Recur down tree to insert node, then • splay node. Amortized Cost of Splaying • • • Let Φ(T) = Σt rank(t). Assume x is target node, p parent, g grandparent Zig amortized cost = 
 1 + (rank’(x) - rank(x)) + (rank’(p) - rank(p)) =
 1 + rank’(p) - rank(x) ≤ 1 + rank’(x) - rank(x) Define size(t) to be the number of nodes in the subtree • rooted at node t. Define rank(t) to be lg(size(t)). We’ll use rank’(t) to signify • rank after an operation. rank’(x) = rank(p) rank’(p) < rank’(x) Amortized Cost of Splaying Define rank(t) to be lg(size(t)). We’ll use rank’(t) to signify rank after an operation. Let Φ(T) = Σt rank(t). Zig-zig amortized cost = 
 2 + (rank’(x) - rank(x)) + (rank’(p) - rank(p)) + (rank’(g) - rank(g))
 • • • • • Similar calculation for zig-zag operation — the change in potential is at most 
 2 (rank’(x)-rank(x)) The sum of costs over the splay is ≤ Σ(2 + 2(rank’(x)-rank(x))) 
 ≤ Σ3(rank’(x)-rank(x))) over the path of x. The terms telescope and the final amortized cost is ≤ 3(rank(root)-rank(x)) which is at most 3(lg(N) - 0) = O(lg N). Cancel rank(g) and rank’(x): rank(x) < rank(p): rank’(x) > rank’(p):
rank’(g) < rank’(x): = 2 + rank’(p)+rank’(g)-rank(x)-rank(p)
 ≤ 2 + rank’(p)+rank’(g) - 2 rank(x)
 ≤ 2 + rank’(x)+rank’(g) - 2 rank(x)
 ≤ 2 + 2 (rank’(x)-rank(x)) Summary: Amortized Costs Amortized costs are a way of getting closer to the true Three methods: • number of operations that a series of operations will take. • Aggregate analysis: Sum all operations over N • operations, find the average cost Accounting method: Come up with a cost structure such • that some operations “overpay” to account for future ops Potential method: Create a potential function on the data • structure that tracks what our remaining “balance” is