15-451 Algorithms 09/21/04
* Amortized analysis
mini2 due tonight
quiz1 next week (30 min)
----------------------------------------------------------------------------
So far we have been looking at static problems where you are given an
input (like an array of n objects) and the goal is to produce an
output with some desired property (e.g., the same objects, but
sorted). For next few lectures, we're going to turn to problems where
we have a *series* of operations, and goal is to analyze time per
operation. E.g., binary search trees, hash tables.
Today, we'll talk about a useful kind of analysis, called *amortized
analysis* for problems of this sort. Before getting to what this
is, let's motivate it with a simple example.
Example #1: implementing a stack as an array
--------------------------------------------
Say we want to use an array to implement a stack. We have an array
A, with a variable "top" that points to top of stack (so A[top] is the
next free cell).
-> to do push(x), just need to do A[top] = x; top++;
-> to do x=pop(), just need to do top--; x = A[top];
(and first check to see if top==0 of course...)
What if the array is full and we need to push a new element on? In
that case we can allocate a new larger array, copy the old one over,
and then go on from there. This is going to be an expensive
operation, so a push that requires us to do this is going to cost a
lot. But maybe we can "amortize" the cost over the previous cheap
operations that got us to this point. So, on average over the
sequence of operations, we're not paying too much.
DEFINITION: Amortized cost of n operations is the total cost divided by n.
Say our cost model is: inserting into array costs 1, taking element
out of array costs 1, and the cost of resizing the array is the number
of elements moved. (could make it 2x this)
Q: What if when we resize we just increase the size by 1. Is that a good
idea? How much could pushing n elements cost? How much is this on
average per operation?
Q: What if we decide to double the size of the array?
Can analyze like this: if we do n operations, the total cost for
inserting/removing is <= n. Total cost for doubling is at worst
n + n/2 + n/4 + .... <= 2n. So, amortized cost per operation is <= 3.
Another way of analyzing it: say that every time we perform a push
operation, we pay $1 to perform it, and we put $2 into a piggy bank.
Any time we need to double the array, from size L to 2L, we must have
$L in the piggy bank [why?]. So, we can use the money in the piggy
bank to pay the $L that it costs to resize the array. So amortized
cost <=3.
This last one is a really useful way of analyzing problems like this.
The "piggy bank" is often called a "potential function", since it's
like potential energy that you can use later. The potential function
is the amount of money in the bank. In this case, it's 2*(number of
elements in the array after the midpoint).
Def: Potential function: a function of the state, generally should be
non-negative and start at 0, used to smooth out analysis.
Amortized cost = actual cost + change in potential. In the "piggy
bank" view, the amortized cost is the out-of-pocket cost per
operation. E.g., in our case, the amortized cost of a push was $3,
even if you resize (since resizing was paid for fully out of the
bank-account/potential-function), and the amortized cost of a pop was $-1.
===========================================================================
Motivation of amortized analysis is that a worst-case-per-operation
analysis can give overly pessimistic bound if the only way of having
an expensive operation is to have a lot of cheap ones before it.
NOTE: this is DIFFERENT from our usual notion of "average case
analysis" -- we're not making any assumptions about inputs being
chosen at random -- we're just averaging over time.
==============================================================================
Another example: a binary counter
---------------------------------
Say we want to store a big binary counter in an array A. All entries
start at 0. Cost model: when we increment counter, we pay $1 for
every bit we need to flip.
A[m] A[m-1] ...... A[3] A[2] A[1] A[0] cost
---------------------------------------- ----
0 0 0 0 0 0
$1
0 0 0 0 0 1
$2
0 0 0 0 1 0
$1
0 0 0 0 1 1
$3
0 0 0 1 0 0
$1
0 0 0 1 0 1
$2
In a sequence of n increments, worst-case cost per increment is O(log n)
since at worst we flip log(n) bits.
But, what is our *amortized* cost per increment? Answer: <= 2.
Proof 1: every time you flip 0 --> 1, cost is $1, plus put $1 into
piggy bank. (so total spent is $2). Every time flip 1-->0, use money
in bank to pay for it. On a given increment, how many 0 --> 1 flips
do we make? So, we just pay $2 (amortized) per increment.
In this case, "potential function" is the number of 1's in the current
count.
Proof 2: how often do we flip A[0]? Answer: every time. how often do
we flip A[1]? Answer: every other time. How often do we flip A[2]?
Answer: every 4th time. Etc. So, total cost spent on flipping A[0]
is n, total cost of A[1] is n/2, total cost on A[2] is n/4, etc. So,
total cost total is at most 2n.
=============================================================
What if it costs us $2^k to flip the kth bit?
Then in a sequence of n increments, a single increment could cost as
much as $n, but claim is amortized cost is just O(log n) per
increment. Probably easiest to see by 1st argument -- A[0] gets
flipped every time for cost of $1 each, or $n total. A[1] gets
flipped every other time for cost of $2 each, or $n total,... ,
A[log(n)-1] got flipped once for cost of $n. So, total is O(n log n),
which is O(log n) amortized per increment.
Neat amortized dictionary data structure:
In next class we will look at a balanced tree data structure for
storing information with O(log n) cost for search and inserts. Here
is a method that's really simple, with O(log^2(n)) search (so, a
little worse than others), and O(log n) amortized cost per insert.
We'll have a collection of arrays, array i has size 2^i. Each array
is either empty or full, and each is in sorted order (but no
relationship between different arrays). E.g., if we had 11 numbers,
it might look like this
A0: [5]
A1: [4,8]
A2: empty
A3: [2, 6, 9, 12, 13, 16, 20, 25]
To search, just do binary search in each occupied array. In worst
case, takes time O( log(n/2) + log(n/4) + log(n/8) + ... + 1) =
O(log^2(n)).
What about inserts? We'll do this like mergesort. To insert the
number 10, we first create an array that just has 10 in it. We now
see if A0 is empty. If so we make this A0. But it's not, so we merge
this with contents of A0 into a new array (which now has [5, 10]).
Then we see if A1 is empty. If so, we make this A1. But it's not so
we merge this with A1 into another new array. Finally, A2 is empty so
we make this be A2. So, now we have:
A0: [-]
A1: [--,--]
A2: [4, 5, 8, 10]
A3: [2, 6, 9, 12, 13, 16, 20, 25]
If insert again, just put into A0. Claim: O(log n) amortized per
insert. Proof: just the same as binary counter with 2^k cost for
counter k.