程序代写代做代考 Java data structure graph C c++ algorithm Amortised analysis

Amortised analysis
Amortised analysis COMP4500/7500
Advanced Algorithms & Data Structures
September 17, 2018
September 17, 2018 1/53

Amortised analysis
Overview of today
Admin/reminders Amortised analysis
1 Aggregate method
2 Accounting method
3 Potential method
Examples:
1 Stack operations
2 Incrementing a binary counter
3 Resizing arrays
September 17, 2018 2/53

Amortised analysis
Amortised analysis
We have so far analysed algorithms for “one-off” use However often we use a data structure (object) for a purpose that involves many uses of its methods.
E.g. priority queue in Dijkstra’s shortest path algorithm.
DIJKSTRA(G, w, s)
1 2 3 4 5 6 7 8 9
/ G is the graph, w the weight function, s the source vertex INIT-SINGLE-SOURCE(G,s)
S=∅ //Sisthesetofvisitedvertices
Q = G.V // Q is a priority queue maintaining G.V − S whileQ̸=∅
u = EXTRACT-MIN(Q)
S = S ∪ {u}
for each vertex v ∈ G.Adj[u]
RELAX(u,v,w)
September 17, 2018 3/53

Amortised analysis
Amortised analysis
Consider an object x with multiple operations. the “worst” is worst-case O(n).
you design an algorithm that uses x’s methods n times Naive analysis: O(n2)
However, you may know that the worst case cannot happen n times in a row.. how can you prove your implementation is actually better than O(n2)?
Amortised analysis considers sequences of operations, typically that successively modify a data structure
September 17, 2018 4/53

Amortised analysis
Amortised analysis
Examples:
1 Java’s ArrayList class: “The add operation runs in amortized constant time”
2 Java’s ArrayDeque class: “Most … operations run in amortized constant time”
3 C++ vector class: Operation push_back: “Complexity [is] Constant (amortized time, reallocation may happen)”
September 17, 2018 5/53

Amortised analysis
Motivating example: dynamic table
Store an initially unknown number of elements in an array. Double the size of the array when it runs out of space
Typically inserting an element is constant time; however sometimes one must
Allocate a new, larger array (twice the size)
Copy all elements to the new array, including the new element
September 17, 2018 6/53

Amortised analysis
Example of a dynamic table
1. INSERT
2. INSERT overflow
1
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.3
September 17, 2018 7/53

Amortised analysis
Example of a dynamic table
1. INSERT
2. INSERT overflow
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.4
1
1
September 17, 2018 8/53

Amortised analysis
Example of a dynamic table
1. INSERT 2. INSERT
1
1
2
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.5
September 17, 2018 9/53

Amortised analysis
Example of a dynamic table
1. INSERT
2. INSERT
3. INSERT overflow
1
1
2
2
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.6
September 17, 2018 10/53

Amortised analysis
Example of a dynamic table
1. INSERT
2. INSERT
3. INSERT overflow
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.7
1
2
September 17, 2018 11/53

Amortised analysis
Example of a dynamic table
1. INSERT 2. INSERT 3. INSERT
1
2
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.8
September 17, 2018 12/53

Amortised analysis
Example of a dynamic table
1. INSERT 2. INSERT 3. INSERT 4. INSERT
1
2
3
4
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.9
September 17, 2018 13/53

Amortised analysis
Example of a dynamic table
1
2
3
4
1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT
overflow
October 31, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L13.10
September 17, 2018 14/53

Amortised analysis
Example of a dynamic table
1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT
overflow
1
2
3
4
October 31, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L13.11
September 17, 2018 15/53

Amortised analysis
Example of a dynamic table
1
2
3
4
1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT
October 31, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L13.12
September 17, 2018 16/53

Amortised analysis
Example of a dynamic table
1
2
3
4
5
6
7
1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT 6. INSERT 7. INSERT
October 31, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L13.13
September 17, 2018 17/53

Amortised analysis
Dynamic table
After n operations (inserting a new element) there are n elements in the array
Inserting an element when the capacity is full (worst case n=2i forsomei)isΘ(n).
Thus, inserting n elements
INSERT(A); INSERT(B); . . . INSERT(M); INSERT(N);
is Θ(n2)? No: it is still Θ(n)
September 17, 2018 18/53

Amortised analysis
Dynamic table
We are analysing: 1 fori=1..n
2 INSERT(ei )
for some sequence of elements e1, e2, .., en.
The vast majority of the insertions are constant time
How many are not, and what is their cost? This depends on i
September 17, 2018 19/53

Amortised analysis
Tighter analysis
Let ci = the cost of the i th insertion
i ifi–1isanexactpowerof2, 1 otherwise.
=
i sizei ci
1 2 3 4 5 6 7 8 9 10 1 2 4 4 8 8 8 8 16 16 1231511191
October 31, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.15
September 17, 2018 20/53

Amortised analysis
Tighter analysis
Let ci = the cost of the i th insertion
i ifi–1isanexactpowerof2, 1 otherwise.
=
i sizei
ci
1 2 3 4 5 6 7 8 9 10
1 2 4 4 8 8 8 8 16 16
1111111111 1248
October 31, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.16
September 17, 2018 21/53

Amortised analysis
Dynamic table: aggregate method
Inserting the 2nd, 3rd, 5th, 9th, … elements
(when the array has size 1, 2, 4, 8 …)
has an additional cost equal to the size of the array.
In general, how many resizes are there in a sequence of n INSERT operations, for n ≥ 1?
⌈lg n⌉
How much does the jth resize operation cost? 2j −1
September 17, 2018 22/53

Amortised analysis
Dynamic table: aggregate method
Cost of n insertions is
􏰇 ni = 1 c i
≤ n+􏰇⌈lgn⌉2j−1 j=1
≤ 3n = Θ(n)
The average cost of each dynamic-table operation is Θ(n)/n = Θ(1).
September 17, 2018 23/53

Amortised analysis
Example: stack operations
Consider standard stack operations PUSH and POP, plus MULTIPOP(S,k) // Assumes S is not empty and k > 0
1 whileSisnotemptyandk>0 2 POP(S)
3 k=k−1
MULTIPOP(S,k) can be O(n) (n is the size of the stack) if k=n
Hence, any sequence of n stack operations must be O(n2) But can we prove a better bound?
Intuition:
MULTIPOP will only iterate while the stack is not empty. Each element is pushed exactly once and popped exactly once, hence after m pushes there can be at most m pops
September 17, 2018 24/53

Amortised analysis
Stack operations: aggregate method
Analyse:
1 fori=1..n
2 PUSH(..)
or
3 POP(..)
or
4 MULTIPOP(..)
Arguing this is O(n) is clumsy using the aggregate method. Consider more sophisticated techniques:
accounting method – focus on the operations potential method – focus on the data structure
September 17, 2018 25/53

Amortised analysis
Stack operations: accounting method
1 Calculate the actual cost, ci , of each operation:
1 PUSH: 1
2 POP: 1
3 MULTIPOP(S, K): k′, where k′ = min(SIZE(S), k)
2 Assign an amortised cost, cˆi , to each method.
1 PUSH: 2
2 POP: 0
3 MULTIPOP(S, K): 0
For any sequence of stack operations, the amortised cost must be an upper bound on the actual cost
Then, one can use the amortised cost in place of the (more complicated) actual cost.
In the above case every operation has constant amortised cost, hence a sequence of n operations is O(n).
September 17, 2018 26/53

Amortised analysis
Stack operations: accounting method
We must show that the total amortised cost minus the total actual cost is never negative:
􏰃n􏰄􏰃n􏰄 􏰀cˆi ≥ 􏰀ci
i=1 i=1
(for all sequences of all possible lengths n)
actual cost amortised cost
op ci cˆi PUSH 1 2 POP 1 0 MULTIPOP(S,k) k′ 0
= MIN(#S,k)
Intuition: the extra credit in PUSH pays for the later (MULTI)POP.
September 17, 2018 27/53

Amortised analysis
Potential method
Focus on the data structure instead of the operations.
1 As before, determine the actual cost, ci , of each operation
2 Define a potential function, Φ, on the data structure.
3 The amortised cost, cˆi , of an operation is the actual cost
plus the change in potential
cˆi =ci +(Φ(Di)−Φ(Di−1))
For any sequence of stack operations, the amortised cost must be an upper bound on the actual cost.
Since
􏰔􏰇ni=1 cˆi 􏰕 = 􏰔􏰇ni=1 ci + (Φ(Di ) − Φ(Di−1))􏰕
= 􏰔􏰇ni=1ci􏰕+(Φ(Dn)−Φ(D0))
the obligation is to show that Φ(Di) ≥ Φ(D0) after every operation. This is trivially true if Φ(D0) = 0 and Φ(Di) ≥ 0.
September 17, 2018 28/53

Amortised analysis
Stack operations: potential method
1 Actual cost is as before (1/1/k′)
2 Φ(S) = #S (size of the stack)
3 Change in potential (Φ(Di) − Φ(Di−1)):
1 PUSH: 1 (the size has increased by one)
2 POP: -1 (the size has decreased by one)
3 MULTIPOP: −k′ (the size has decreased by k′)
4 Amortised cost (actual cost + change in potential):
1 PUSH: 2(=1+1)
2 POP: 0(=1+-1)
3 MULTIPOP:0(=k′+−k′)
Obligation: Φ(Di) ≥ Φ(D0) = 0, which is trivial.
Therefore, all operations have constant amortised time.
For this simple example, potential and accounting method give almost exactly the same intuition
September 17, 2018 29/53

Amortised analysis
Incrementing a binary counter
INCREMENT(A,k) 1i=0
2 3 4 5 6
whilei 0.
3 Determine the amortised cost of each operation from Φ.
September 17, 2018 40/53

Amortised analysis
Potential analysis of table
doubling
Define the potential of the table after the ith insertion by Φ(Di) = 2i – 2⎡lg i⎤. (Assume that 2⎡lg 0⎤ = 0.)
Note:
• Φ(D0 ) = 0,
• Φ(Di) ≥ 0 for all i. Example:
Φ = 2·6 – 23 = 4
•
•
•
•
•
•
•
•
•
•
•
•
( accounting method)
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.30
$0 $0 $0 $0 $2 $2
$0 $0 $0 $0 $2 $2
September 17, 2018 41/53

Amortised analysis
Calculation of amortized costs
The amortized cost of the i th insertion is ĉi = ci + Φ(Di) – Φ(Di–1)
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.31
September 17, 2018 42/53

Amortised analysis
Calculation of amortized costs
The amortized cost of the i th insertion is ĉi = ci + Φ(Di) – Φ(Di–1)
i ifi–1isanexactpowerof2, 1 otherwise;
=
+ (2i – 2⎡lg i⎤) – (2(i –1) – 2⎡lg (i–1)⎤)
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.32
September 17, 2018 43/53

Amortised analysis
Calculation of amortized costs
The amortized cost of the i th insertion is ĉi = ci + Φ(Di) – Φ(Di–1)
i ifi–1isanexactpowerof2, 1 otherwise;
=
+ (2i – 2⎡lg i⎤) – (2(i –1) – 2⎡lg (i–1)⎤)
i ifi–1isanexactpowerof2,
=
+ 2 – 2⎡lg i⎤ + 2⎡lg (i–1)⎤ .
1 otherwise;
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.33
September 17, 2018 44/53

Amortised analysis
Calculation
Case 1: i – 1 is an exact power of 2. ĉi =i+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.34
September 17, 2018 45/53

Amortised analysis
Calculation
Case 1: i – 1 is an exact power of 2. ĉi =i+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
= i + 2 – 2(i – 1) + (i – 1)
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.35
September 17, 2018 46/53

Amortised analysis
Calculation
Case 1: i – 1 is an exact power of 2. ĉi =i+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
= i + 2 – 2(i – 1) + (i – 1) = i + 2 – 2i + 2 + i – 1
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.36
September 17, 2018 47/53

Amortised analysis
Calculation
Case 1: i – 1 is an exact power of 2. ĉi =i+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
= i + 2 – 2(i – 1) + (i – 1) = i + 2 – 2i + 2 + i – 1 =3
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.37
September 17, 2018 48/53

Amortised analysis
Calculation
Case 1: i – 1 is an exact power of 2. ĉi =i+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
= i + 2 – 2(i – 1) + (i – 1) = i + 2 – 2i + 2 + i – 1 =3
Case 2: i – 1 is not an exact power of 2. ĉi =1+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
= 3 (since 2⎡lg i⎤ = 2⎡lg (i–1)⎤ )
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.39
September 17, 2018 50/53

Amortised analysis
Calculation
Case 1: i – 1 is an exact power of 2. ĉi =i+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
= i + 2 – 2(i – 1) + (i – 1) = i + 2 – 2i + 2 + i – 1 =3
Case 2: i – 1 is not an exact power of 2. ĉi =1+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
=3
Therefore, n insertions cost Θ(n) in the worst case.
October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.40
September 17, 2018 51/53

Amortised analysis
Calculation
Case 1: i – 1 is an exact power of 2. ĉi =i+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
= i + 2 – 2(i – 1) + (i – 1) = i + 2 – 2i + 2 + i – 1 =3
Case 2: i – 1 is not an exact power of 2. ĉi =1+2–2⎡lgi⎤ +2⎡lg(i–1)⎤
=3
Therefore, n insertions cost Θ(n) in the worst case.
Exercise: Fix the bug in this analysis to show that the amortized cost of the first insertion is only 2. October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.41
September 17, 2018 52/53

Amortised analysis Recap
Amortised analysis
1 Aggregate method
2 Accounting method
3 Potential method
For when you are implementing a data structure and a set of operations that modify/query it, rather than a specific operation (such as sorting a list).
Find an upper bound on the complexity (cost) which still gives the desired result
Examples:
1 Stack operations
2 Incrementing a binary counter
3 Resizing arrays
Accounting and potential method are ways of structuring proofs (operation- or data-structure-focused, respectively), which are essentially the aggregate method underneath
September 17, 2018 53/53

Related Posts