Post on 30-May-2018
8/14/2019 Cormen Algo-lec13
1/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.1
Introduction to Algorithms
6.046J/18.401J
LECTURE 13Amortized Analysis
Dynamic tables
Aggregate method Accounting method
Potential method
Prof. Charles E. Leiserson
8/14/2019 Cormen Algo-lec13
2/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.2
How large should a hash
table be?Goal: Make the table as small as possible, butlarge enough so that it wont overflow (orotherwise become inefficient).
Problem: What if we dont know the proper size
in advance?
IDEA: Whenever the table overflows, grow itby allocating (via malloc ornew) a new, largertable. Move all items from the old table into the
new one, and free the storage for the old table.
Solution:Dynamic tables.
8/14/2019 Cormen Algo-lec13
3/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.3
Example of a dynamic table
1. INSERT 1
2. INSERT overflow
8/14/2019 Cormen Algo-lec13
4/42October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.4
Example of a dynamic table
1. INSERT 11
2. INSERT overflow
8/14/2019 Cormen Algo-lec13
5/42October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.5
Example of a dynamic table
1. INSERT 11
2. INSERT 2
8/14/2019 Cormen Algo-lec13
6/42October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.6
Example of a dynamic table
1. INSERT 11
2. INSERT 22
3. INSERT overflow
8/14/2019 Cormen Algo-lec13
7/42October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.7
Example of a dynamic table
1. INSERT2
1
2. INSERT3. INSERT overflow
8/14/2019 Cormen Algo-lec13
8/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.8
Example of a dynamic table
1. INSERT 1
2. INSERT 2
3. INSERT
8/14/2019 Cormen Algo-lec13
9/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.9
Example of a dynamic table
1. INSERT
2. INSERT3. INSERT
4. INSERT4
3
2
1
8/14/2019 Cormen Algo-lec13
10/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.10
Example of a dynamic table
1. INSERT 1
2. INSERT 233. INSERT
4. INSERT5. INSERT
4
overflow
8/14/2019 Cormen Algo-lec13
11/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.11
Example of a dynamic table
1. INSERT
2. INSERT
4
3
2
1
3. INSERT
4. INSERT5. INSERT overflow
8/14/2019 Cormen Algo-lec13
12/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.12
Example of a dynamic table
1. INSERT
2. INSERT
1
2
33. INSERT
4. INSERT5. INSERT
4
8/14/2019 Cormen Algo-lec13
13/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.13
Example of a dynamic table
1. INSERT
2. INSERT3. INSERT
4. INSERT
6. INSERT 65. INSERT 5
4
3
2
1
77. INSERT
8/14/2019 Cormen Algo-lec13
14/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.14
Worst-case analysis
Consider a sequence ofn insertions. The
worst-case time to execute one insertion is(n). Therefore, the worst-case time forninsertions is n (n) = (n2).
WRONG! In fact, the worst-case cost forn insertions is only (n) (n2).
Lets see why.
8/14/2019 Cormen Algo-lec13
15/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.15
Tighter analysis
Let ci = the cost of the i th insertion
=i ifi 1 is an exact power of2,
1 otherwise.
i 1 2 3 4 5 6 7 8 9 10
sizei 1 2 4 4 8 8 8 8 16 16
ci 1 2 3 1 5 1 1 1 9 1
8/14/2019 Cormen Algo-lec13
16/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.16
Tighter analysis
Let ci = the cost of the i th insertion
=i ifi 1 is an exact power of2,
1 otherwise.
i 1 2 3 4 5 6 7 8 9 10
sizei 1 2 4 4 8 8 8 8 16 16
1 1 1 1 1 1 1 1 1 11 2 4 8
ci
8/14/2019 Cormen Algo-lec13
17/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.17
Tighter analysis (continued)
)(
3
2
)1lg(
0
1
n
n
n
c
n
j
j
n
i
i
=
+
=
=
=
Cost ofn insertions
.
Thus, the average cost of each dynamic-table
operation is (n)/n = (1).
8/14/2019 Cormen Algo-lec13
18/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.18
Amortized analysis
An amortized analysis is any strategy foranalyzing a sequence of operations to
show that the average cost per operation issmall, even though a single operationwithin the sequence might be expensive.
Even though were taking averages, however,probability is not involved!
An amortized analysis guarantees theaverage performance of each operation inthe worst case.
8/14/2019 Cormen Algo-lec13
19/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.19
Types of amortized analyses
Three common amortization arguments:
the aggregate method,
the accountingmethod, thepotentialmethod.
Weve just seen an aggregate analysis.
The aggregate method, though simple, lacks the
precision of the other two methods. In particular,the accounting and potential methods allow aspecific amortized costto be allocated to each
operation.
8/14/2019 Cormen Algo-lec13
20/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.20
Accounting method
Charge i th operation a fictitious amortized costi, where $1pays for1 unit of work (i.e., time).
This fee is consumed to perform the operation. Any amount not immediately consumed is storedin the bankfor use by subsequent operations.
The bank balance must not go negative! Wemust ensure that
==
n
ii
n
ii cc 11
for all n. Thus, the total amortized costs provide an upperbound on the total true costs.
A ti l i f
8/14/2019 Cormen Algo-lec13
21/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.21
Accounting analysis of
dynamic tables
$0$0 $0$0 $0$0 $0$0 $2$2 $2$2
Example:
$2 $2
Charge an amortized cost ofi = $3 for the i thinsertion.
$1pays for the immediate insertion. $2 is stored for later table doubling.
When the table doubles, $1pays to move arecent item, and $1pays to move an old item.
overflow
Acco nting anal sis of
8/14/2019 Cormen Algo-lec13
22/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.22
Accounting analysis of
dynamic tables
Example:
Charge an amortized cost ofi = $3 for the i thinsertion.
$1pays for the immediate insertion. $2 is stored for later table doubling.
When the table doubles, $1pays to move arecent item, and $1pays to move an old item.
overflow
$0$0 $0$0 $0$0 $0$0 $0$0 $0$0 $0$0 $0$0
Accounting analysis of
8/14/2019 Cormen Algo-lec13
23/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.23
Accounting analysis ofdynamic tables
Charge an amortized cost ofi = $3 for the i thinsertion.
$1pays for the immediate insertion. $2 is stored for later table doubling.
Example:
When the table doubles, $1pays to move arecent item, and $1pays to move an old item.
$0$0 $0$0 $0$0 $0$0 $0$0 $0$0 $0$0 $0$0 $2 $2 $2
Accounting analysis
8/14/2019 Cormen Algo-lec13
24/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.24
Accounting analysis(continued)
Key invariant: Bank balance never drops below 0.Thus, the sum of the amortized costs provides an
upper bound on the sum of the true costs.
i
sizei
ci
i
banki
1 2 3 4 5 6 7 8 9 10
1 2 4 4 8 8 8 8 16 16
1 2 3 1 5 1 1 1 9 1
2 3 3 3 3 3 3 3 3 3
1 2 2 4 2 4 6 8 2 4
*
*Okay, so I lied. The first operation costs only $2, not $3.
8/14/2019 Cormen Algo-lec13
25/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.25
Potential method
IDEA: View the bank account as the potentialenergy ( laphysics) of the dynamic set.
Framework:
Start with an initial data structureD0.
Operation i transformsDi1 toDi. The cost of operation i is ci. Define apotential function : {Di} R,
such that (D0 ) = 0 and (Di ) 0 for all i. The amortized costi with respect to is
defined to be
i = ci + (Di) (Di1).
8/14/2019 Cormen Algo-lec13
26/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.26
Understanding potentials
i = ci + (Di) (Di1)
potential difference i
If i > 0, then i > ci. Operation i storeswork in the data structure for later use.
If i< 0, then
i< c
i. The data structure
delivers up stored work to help pay foroperation i.
The amortized costs bound
8/14/2019 Cormen Algo-lec13
27/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.27
The amortized costs boundthe true costs
The total amortized cost ofn operations is
( ) =
=+=
n
iiii
n
ii DDcc
11
1
)()(
Summing both sides.
The amortized costs bound
8/14/2019 Cormen Algo-lec13
28/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.28
The amortized costs boundthe true costs
The total amortized cost ofn operations is
( )
)()(
)()(
01
11
1
DDc
DDcc
n
n
ii
n
iiii
n
ii
+=
+=
=
=
=
The series telescopes.
The amortized costs bound
8/14/2019 Cormen Algo-lec13
29/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.29
The amortized costs boundthe true costs
The total amortized cost ofn operations is
( )
=
=
=
=
+=
+=
n
ii
n
n
ii
n
iiii
n
ii
c
DDc
DDcc
1
01
11
1
)()(
)()(
since (Dn) 0 and(D0 ) = 0.
8/14/2019 Cormen Algo-lec13
30/42
8/14/2019 Cormen Algo-lec13
31/42
C l l i f i d
8/14/2019 Cormen Algo-lec13
32/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.32
Calculation of amortized costs
The amortized cost of the i th insertion is
i = ci +
(Di)
(Di1)
i ifi 1 is an exact power of2,
1 otherwise;+ (2i 2lg i)(2(i 1) 2lg (i1))
=
C l l ti f ti d t
8/14/2019 Cormen Algo-lec13
33/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.33
Calculation of amortized costs
The amortized cost of the i th insertion is
i = ci +
(Di)
(Di1)
i ifi 1 is an exact power of2,
1 otherwise;
=
+ (2i 2lg i)(2(i 1) 2lg (i1))
i ifi 1 is an exact power of2,1 otherwise;
=
+ 2 2lg i
+ 2lg (i1)
.
8/14/2019 Cormen Algo-lec13
34/42
C l l ti
8/14/2019 Cormen Algo-lec13
35/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.35
Calculation
Case 1: i 1 is an exact power of2.
i = i + 2 2lg i + 2lg (i1)
= i + 2 2(i 1) + (i 1)
C l l ti
8/14/2019 Cormen Algo-lec13
36/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.36
Calculation
Case 1: i 1 is an exact power of2.
i = i + 2 2lg i + 2lg (i1)
= i + 2 2(i 1) + (i 1)= i + 2 2i + 2 + i 1
C l l ti
8/14/2019 Cormen Algo-lec13
37/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.37
Calculation
Case 1: i 1 is an exact power of2.
i = i + 2 2lg i + 2lg (i1)
= i + 2 2(i 1) + (i 1)= i + 2 2i + 2 + i 1= 3
Calculation
8/14/2019 Cormen Algo-lec13
38/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.38
Calculation
Case 1: i 1 is an exact power of2.
i = i + 2 2lg i + 2lg (i1)
= i + 2 2(i 1) + (i 1)= i + 2 2i + 2 + i 1= 3
Case 2: i 1 is notan exact power of2.i = 1 + 2 2
lg i + 2lg (i1)
8/14/2019 Cormen Algo-lec13
39/42
Calculation
8/14/2019 Cormen Algo-lec13
40/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.40
Calculation
Case 1: i 1 is an exact power of2.
i = i + 2 2lg i + 2lg (i1)
= i + 2 2(i 1) + (i 1)= i + 2 2i + 2 + i 1= 3
Case 2: i 1 is notan exact power of2.i = 1 + 2 2
lg i + 2lg (i1)
= 3
Therefore, n insertions cost (n) in the worst case.
Calculation
8/14/2019 Cormen Algo-lec13
41/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.41
Calculation
Case 1: i 1 is an exact power of2.
i = i + 2 2lg i + 2lg (i1)
= i + 2 2(i 1) + (i 1)= i + 2 2i + 2 + i 1= 3
Case 2: i 1 is notan exact power of2.i = 1 + 2 2
lg i + 2lg (i1)
= 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.
Conclusions
8/14/2019 Cormen Algo-lec13
42/42
October 31, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.42
Conclusions
Amortized costs can provide a clean abstractionof data-structure performance.
Any of the analysis methods can be used whenan amortized analysis is called for, but eachmethod has some situations where it is arguablythe simplest or most precise.
Different schemes may work for assigning
amortized costs in the accounting method, orpotentials in the potential method, sometimesyielding radically different bounds.