CS计算机代考程序代写 Amortized Analysis

Amortized Analysis
Nishant Mehta
219
Lecture 18
s

Amortized Analysis
Amortized analysis is a way of doing worst-case analysis by bounding the average cost to perform each operation (averaged over the sequence of operations)
Motivation: Some operations might be very expensive, but they happen infrequently, so on average each operation might have low cost
Amortized Analysis is not related to Average-Case Analysis; amortized analysis doesn’t use probability or expected value

The peril of per-operation worst-case analysis Example: Stack S
OCI ) 0111
Suppose that in addition to having the usual PUSH and POP operation, we also have an operation KPOP
KPOP(S, k): Pop top k elements on stack (or all elements if less than k elements are on stack)
01kt
Worst-case cost of sequence of n PUSH, POP, and KPOP
Worst-case cost of KPOP operation?
operations?
Oink
)

Aggregate analysis
Aggregate analysis bounds worst-case runtime in aggregate (over whole sequence of operations), rather than giving worst-case bounds for each operation separately (without consideration of previous operations)
Example: Stack with KPOP
• •

Cost of each KPOP is simply the number of actual pops that happen within it
Total number of pops is at most total number of pushes (at most n)
So, any sequence of n pushes, pops, and KPOPs takes at most O(n) time

Aggregate analysis
Aggregate analysis bounds worst-case runtime in aggregate (over whole sequence of operations), rather than giving worst-case bounds for each operation separately (without consideration of previous operations)
Example: Stack with KPOP
• •

Cost of each KPOP is simply the number of actual pops that happen within it
Total number of pops is at most total number of pushes (at most n)
So, any sequence of n pushes, pops, and KPOPs takes at most O(n) time

Accounting method
In the accounting method, for each operation we charge an amortized cost

For the ith operation:
ci is actual cost ˆci is amortized cost
we charge the actualcost Ci Interpretation of ˆci > ci ? plus credit (Ei – ci)
Goal: select amortized costs such that we have:
The amortized cost of an operation can be greater than (or less than!!) the actual cost
Actual cost
Xn Xn Upper bound on runtime! ci ˆci
i=1 i=1

Accounting Method – Stack with KPOP example
ith operation
if ith operation if ith op.
=L
( Pdt
if
i s PUSH
:
E,
the
is
Pop : §.
(already paid fr by some Push! [Ci- I)
is Krol :
di
– –
fan
pops
are
already paidfor)
§, I.
some actual costs Ci though I i small
large ,
=
O

e E?– an
1 for actual cost g. =/ and prepay l b/c eventually
element might be popped)
pushed
Even
all dmoritired costs ^ are
a re

Incrementing binary counter example
k-bit counter with INCREMENT
INCREMENT:
i =0
while i < k and A[i] == 1 decimal 00000000 :0 00000001 00000010 00000011 00000100 4 00000101 g- 00000110 , 00000111 7- K -- 8 A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] A[i] = 0 i = i +1 if i < k A[i] = 1 analysis " naive case operation is Ock) 0 0(0 0 1 0 0 0 → o O O O O O 00 → nk)- worst- case ofn increments worst - when increment A- llllllll 3 Worst-case cost of n INCREMENT operations? i cost e Aggregate analysis: A- lo l A- Cll A fin : I changes changes changes n times 12 times 7, time ' total Ii = 2n en !II. on Incrementing binary counter example k-bit counter with INCREMENT INCREMENT: i =0 while i < k and A[i] == 1 A[i] = 0 i = i +1 if i < k A[i] = 1 ci -00000000 100000001 200000010 100000011 300000100 100000101 200000110 100000111 400001000 A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] Worst-case cost of n INCREMENT operations? Accounting method: Incrementing binary counter example k-bit counter with INCREMENT INCREMENT: i =0 while i < k and A[i] == 1 A[i] = 0 i = i +1 if i < k A[i] = 1 ci -00000000 100000001 200000010 100000011 300000100 100000101 200000110 100000111 400001000 A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] -$1 -$1 -$1 -$1 Worst-case cost of n INCREMENT operations? Accounting method: 0 will be set to l . In one operation at most a single k$1 for actual o → I , ) di E ' = 2n when a when , charge $2 O is set to l i $1 to prep¥ay for I→ O ? Ci e en, I is set to 0 , charge $0 . total cost , Incrementing binarfy counter example cumulation t - - I 2 3 4 46 7- 8 8 10 10 12 11 14 1516 k-bit counter with INCREMENT INCREMENT: ˆci ci --00000000 2100000001 2200000010 2100000011 2300000100 2100000101 2200000110 2100000111 2400001000 cumulative A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] i =0 while i < k and A[i] == 1 A[i] = 0 i = i +1 if i < k A[i] = 1 -$1 -$1 -$1 -$1 Worst-case cost of n INCREMENT operations? Accounting method: 0 will be set to l . In one operation at most a single k$1 for actual o → I , ) di E ' = 2n when a when , charge $2 O is set to l i $1 to prep¥ay for I→ O ? Ci e en, l is set to 0 , charge $0 . total cost , Dynamic tables We want a table which can support a stream of INSERT and DELETE operations Like with hash tables, we define the load factor of table T to be: ↵(T) = When the load factor is 1 and a new INSERT operation arrives, we need to increase the size of the table. We also want the load factor to be lower bounded by a positive constant (let’s use 1/2) to ensure that we are using at least a constant fraction of the allocated space. [# of elements stored in T] [size of T] Dynamic tables T. How can we insert an element x when the load factor is 1 (so the table T is full)? We need to resize the table. For simplicity let’s suppose the table is of size at least 1. INSERT(T, x ): if T.n == T.size slots n - * of n = stored T # of elements in table Allocate new table Tnew of size 2 · T.size gotra: Insert all items in T into Tnew in T = Tnew Insert x into T T.n = T.n + 1 Dynamic Tables - Accounting Method credit - prepaying Each insertion - charge $3, broken down as: • $1 for the insertion itself (this is the actual cost) • $1 credit for moving this item $2 credit for use upon resize operation: • • $1 credit for moving an item that has already been moved (such an item has no credit anymore as it used up its credit when it was moved the first time) - $4 DAios Insertion redistributed wealth y, each has insertion amortized cost A §. =3 Koki i:$ iI# I$ D itto T#$ol$ol$ol$4XTHX Dynamic Tables - Accounting Method What about shrinking the table once the table is too empty? By symmetry, you might think “let’s halve the table when it’s less than half empty,” but this is problematic. Two ways to see why: (1) Consider what happens when the load factor is right around 1/2. A deletion triggers a halving, at which point the table is now nearly full. Two insertions trigger a doubling, and the table is right around 1/2 again. Two deletions trigger a halving, etc. This is too expensive! Dynamic Tables - Accounting Method What about shrinking the table once the table is too empty? By symmetry, you might think “let’s halve the table when it’s less than half empty,” but this is problematic. Two ways to see why: (1) Consider what happens when the load factor is right around 1/2. A deletion triggers a halving, at which point the table is now nearly full. Two insertions trigger a doubling, and the table is right around 1/2 again. Two deletions trigger a halving, etc. This is too expensive! (2) A halving can happen soon after a doubling (since a doubling brings the load factor close to 1/2). But, after a doubling, nearly all elements have no credit on them. So, we don’t have enough to pay for a halving. Dynamic Tables - Accounting Method (2) A halving can happen soon after a doubling (since a doubling brings the load factor close to 1/2). But, after a doubling, nearly all elements have no credit on them. So, we don’t have enough to pay for a halving. Ah, why don’t we postpone halving until after we have built up enough credit. Let’s charge $2 for each deletion: • $1 for the actual deletion itself (this is the actual cost) • $1 credit to pay for moving an item upon a halving operation When have we earned enough credit to do a halving? When the table has load ≤ 1/4. Why? Since the most recent doubling operation, we have deleted at least a quarter of the table. Thus, we have enough credit to move a quarter of the table upon deletion. Deletion# generates 1 Ftl F -delete in ' q delete - -- di ,Tignoring# delete T$ol$ol$ol$HXfXlX T§$ll$o/XlxlxlxIX TH$oIX1X extra $ 2 --2 . a = ( Delete n %,, I3 =it : For runtime sequence di s of any Insert operations § max -13,27 = , CiEIi . =3n Dynamic Tables - Accounting Method (2) A halving can happen soon after a doubling (since a doubling brings the load factor close to 1/2). But, after a doubling, nearly all elements have no credit on them. So, we don’t have enough to pay for a halving. Ah, why don’t we postpone halving until after we have built up enough credit. Let’s charge $2 for each deletion: • $1 for the actual deletion itself (this is the actual cost) • $1 credit to pay for moving an item upon a halving operation When have we earned enough credit to do a halving? When the table has load ≤ 1/4. Why? Since the most recent doubling operation, we have deleted at least a quarter of the table. Thus, we have enough credit to move a quarter of the table upon deletion.