Unit 6: Amortized Analysis
․Course contents: ⎯ ⎯ ⎯
Aggregate method Accounting method Potential method
․Reading: ⎯
Unit 6
Chapter 17
Y.-W. Chang
1
Amortized Analysis
․Why Amortized Analysis? ⎯
Find a tight bound of a sequence of data structure operations.
․No probability involved, guarantees the average performance of each operation in the worst case. ․Three popular methods ⎯ ⎯ ⎯
Unit 6
Aggregate method Accounting method Potential method
Y.-W. Chang
2
Methods for Amortized Analysis
․Aggregate method ⎯ ⎯
n operations take T(n) time. Average cost of an operation is T(n)/n time.
․Accounting method ⎯ ⎯ ⎯ ⎯
Charge each operation an amortized cost. Store the amount not used in “bank.” Use the stored amount for later operations. Must guarantee nonnegative balance!!
․Potential method ⎯
Unit 6
View “stored amount” as “potential energy.”
Y.-W. Chang
3
Aggregate method: MULTIPOP ․ n operations take T(n) time ⇒ average cost of an operation is T(n)/n time. ․ Consider a sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack. ⎯ ⎯
Worst-case analysis: a MULTIPOP operation takes O(n). Aggregate method: Any sequence of n PUSH, POP, MULTIPOP costs at most O(n) time (why?) ⇒ amortized cost of an operation: O(n)/n=O(1). MULTIPOP(S, k) 1.while not Stack-Empty(S) and k > 0 2. Pop(S); 3. k ← k-1;
Unit 6
Y.-W. Chang
4
Incrementing a Binary Counter
․Increment an initially zero k-bit binary counter.
Increment(A) 1. i ← 0; 2. while i < length[A] and A[i]=1 3. A[i] ← 0; 4. i ← i + 1; 5. if i < length[A] 6. A[i] ← 1;
Unit 6
Y.-W. Chang
5
Aggregate method: Incrementing a Binary Counter
․Worst case: an INCREMENT operation takes O(k) time. ․The amortized cost: O(1) time. ⎯
⎯
Unit 6
A[0], A[1], A[2], …: flips each time, every other time, every fourth time,... that INCREMENT is called. ⎢⎣lg n ⎥⎦ ⎢ n ⎥ # Flips = ∑ i =0 ⎢ i ⎥ < 2n ⇒ Amortized Cost = O(n)/n = O(1). ⎣2 ⎦
Y.-W. Chang
6
Accounting method ․ Stack operations (s: stack size):
For any sequence of n operations, total actual cost ≤ total amortized cost = O(n). ․ Incrementing a binary counter ⎯ Charge an amortized cost of $2 to set a bit to 1. ⎯
⎯ ⎯
Don't charge anything to reset a bit to 0 (-$1 from credit). For n increment operations, total credit = # of 1's in the counter ≥ 0,
Unit 6
1 → actual cost 1 → credit
Total actual cost ≤ total amortized cost = O(n) Y.-W. Chang
7
The Potential Method ․ View the prepaid work as “potential” that can be released to pay for future operations. ⎯
Potential is associated with the whole data structure, not with specific items in the data structure.
․ The potential method: ⎯
⎯ ⎯
D0: initial data structure Di: data structure after applying the i-th operation to Di-1 ci: actual cost of the i-th operation Define the potential function φ : Di → R. ˆ i , cˆ i = ci + φ(Di) - φ(Di-1). Amortized cost c
∑ cˆ ∑ c n
⎯ ⎯
Unit 6
n
≥ i =1 i Pick φ(Dn) ≥ φ(D0) to make i =1 i Often define φ(D0) = 0 and then show that φ(Di) ≥ 0, ∀ i. Y.-W. Chang
8
The Potential Method: Stack Operations
․Amortized cost of each operation = O(1). ․φ(D) = # of objects in the stack D; φ(D0)=0, φ(Di) ≥ 0. ․PUSH: cˆ i = ci + φ(Di) - φ(Di-1) = 1 + (s+1) - s = 2. ․POP: cˆ i = ci + φ(Di) - φ(Di-1) = 1 + (-1) = 0. ․MULTIPOP(S, k): k' = min(k, s) objects are popped off.
cˆ
Unit 6
i
= ci + φ(Di) - φ(Di-1) = k' - k' = 0.
Y.-W. Chang
9
Potential Method: Incrementing a Binary Counter
․Amortized cost of each operation = O(1). ․φ(D)= # of 1's in the counter D; let bi = φ(Di) ≥ 0. ․Suppose the i-th increment operation resets ti bits. ci ≤ ti + 1 bi ≤ bi-1 - ti +1.
․Amortized cost
cˆ
i
= ci + φ(Di) - φ(Di-1) ≤ (ti + 1) - ti + 1 =
2. ․For b0 ≤ k, let n = Ω(k).
Unit 6
Y.-W. Chang
10
Dynamic Table Expansion ․ Insertion only for the timing being. ․ Goal: Try to make table as small as possible. ․ Idea: Allocate more memory when needed Initialize table size m = 1. 2. Insert elements until the # of elements > m. 3. Generate a new table of size 2m. 4. Copy old elements into a new table. 5. Goto Step 2. Actual costs: ci= ith insertion. 1.
․
․ One Insertion can be costly, but in total? ⎯
Unit 6
Worst-case cost of an insertion = O(n) ⇒ total time for n insertions =O(n2). Not tight!! Y.-W. Chang
11
Expansion: Aggregate and Accounting Analyses
․Aggregate analysis: amortized cost of an operation < 3.
․Accounting analysis: amortized cost of an operation < 3. ⎯ Charge each operation $3 (amortized cost): $1 for immediate insertion and store $2. ⎯ When table doubles, $1 for a re-inserting item and $1 for re-inserting another old item. ⎯ Total runtime = # of dollars spent ≤ # of dollars entered table = 3n. Unit 6
Y.-W. Chang
12
Expansion: Potential Analyses ․ num[T]: # of elements in T; size[T]: size of the table T. ․ φ(T)= 2 num[T] - size[T] Right before expansion: φ(T) = num[T]. ⎯ Right after expansion: φ(T) = 0. ․ φ0 = 0; φi ≥ 0. ․ Table is always at least half full: num[T] ≥ size[T]/2 ⇒ φ(T) ≥ 0. ․ If i-th operation does not trigger an expansion (sizei = sizei-1): cˆ i = ci + φi - φi-1 = 1 + (2 numi - sizei) - (2 numi-1 - sizei-1) = 1 + (2 numi - sizei) - (2 (numi-1) - sizei) = 3. ․ If i-th operation trigger an expansion (sizei /2 = sizei-1 = numi - 1): cˆ i = ci + φi - φi-1 = numi + (2 numi - sizei) - (2 numi-1 - sizei-1) = numi + (2 numi - (2 numi -2)) - (2 (numi -1) - (numi -1)) = 3. ⎯
Unit 6
Y.-W. Chang
13
Effect of Expansion
․φ(T)= 2 num[T] - size[T] ⎯ ⎯
Right before expansion: φ(T) = num[T]. Right after expansion: φ(T) = 0.
․φ0 = 0; φi ≥ 0. ․Table is always at least half full: num[T] ≥ size[T]/2 ⇒ φ(T) ≥ 0.
Unit 6
Y.-W. Chang
14
Expansion and Contraction: Accounting Analysis ․ Bad idea: Double the table when overflow (as before), halve it when table < full /2. ⎯
⎯
Cause thrashing when repeatedly halve and double it if repeatedly insert and delete 2 items. n = 2k: insert n/2 items and then I D D I I D D … ⇒ amortized cost of an operation = θ(n).
․ Better idea: Double the table when overflow and halve it when table < full /4. ․ Accounting analysis ⎯ ⎯
Unit 6
Charge $3 for each insertion (as before). Charge $2 for deletion: Store extra $1 in emptied slot, use later to pay to copy remaining items to a new table when shrink the table.
Y.-W. Chang
15
Potential Analysis: Expansion and Contraction ․ Load factor: α(T) = num[T]/size[T] if num[T] > 0; α(T) = 1 if num [T] = 0.
․ Define the potential function φ(T):
⎯ ⎯ ⎯ ⎯
Unit 6
num0 = 0, size0 = 0, α0 = 1, φ0 = 0, φi ≥ 0. α = 1 ⇒ φ(T) = num[T]: sufficient potential for expansion. α = 1/2 ⇒ φ(T) = 0. α = 1/4 ⇒ φ(T) = num[T]: sufficient potential for contraction.
Y.-W. Chang
16
Potential Analysis: Insertion ․ i-th operation is an insertion: numi = numi-1 + 1 ⎯ ⎯
⎯
Unit 6
αi-1 ≥ 1/2: cˆ i ≤ 3 (as before) αi-1 < 1/2, αi < 1/2: cˆ i = ci + φi - φi-1 = 1 + (sizei /2 - numi) - (sizei-1/2 - numi-1) = 1 + (sizei /2 - numi) - (sizei /2 - (numi - 1)) = 0. αi-1 < 1/2, αi ≥ 1/2: cˆ i = 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 - 3sizei-1/2 + 3 = 3 αi-1 sizei-1 - 3sizei-1/2 + 3 < 3sizei-1/2 - 3sizei-1/2 + 3 = 3. Y.-W. Chang
17
Potential Analysis: Deletion
․i-th operation is a deletion: numi = numi-1 - 1 ⎯
⎯
⎯
Unit 6
αi-1 < 1/2, αi ≥ 1/4: no contraction ⇒ sizei = sizei-1 cˆ i = ci + φi - φi-1 = 1 + (sizei /2 - numi) - (sizei-1/2 - numi-1) = 1 + (sizei /2 - numi) - (sizei /2 - (numi + 1)) = 2. αi-1 < 1/2, αi < 1/4: with contraction ⇒ sizei /2 = sizei-1 /4 = numi + 1 cˆ i = ci + φi - φi-1 = (numi + 1) + (sizei /2 - numi) - (sizei-1/2 - numi-1) = (numi + 1) + ((numi + 1) - numi) – ((2numi + 2) - (numi + 1)) = 1. αi-1 ≥ 1/2 : cˆ i ≤ some constant.
Y.-W. Chang
18
B*-tree Packing Revisited
․ x-coordinates can be determined by the tree structure. ⎯ ⎯
Left child: the lowest, adjacent block on the right (xj = xi + wi). Right child: the first block above, with the same x-coordinate (xj = xi).
․ y-coordinates? b5 b b11
n0
b6 b3
b2
b10
n7
b4
n1
n8
x1=x0 b00
n2 n5
b9 b8
b11
n11 n9
n3
n6
b7 (x0,y0)
w0 Unit 6
x7=x0+w0 Y.-W. Chang
n10
n4 19
Computing y-coordinates
․Reduce the complexity of computing a y-coordinate to amortized O(1) time. horizontal contour vertical contour b10
b1 b3 b 4
b0
b9 b8
b11 b7
Unit 6
Y.-W. Chang
20