In [1]:
%matplotlib inline
import pandas as pd
import numpy as np
from __future__ import division
import itertools
import matplotlib.pyplot as plt
import seaborn as sns
import logging
logger = logging.getLogger()
In an amortized analysis, we averget the time required to perform a sequence of data-structure operations over all the operations performed.
Amortized analsis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the _average performance of each operation in the worst case__.
Bear in mind that the charges assigned during an amortized analysis are for analysis purposes only.
When we perform an amortized analysis, we often gain insight into a particular data structure, and this insight can help us optimize the design.
In [2]:
plt.imshow(plt.imread('./res/fig17_2.png'))
Out[2]:
In general, for $i = 0, 1, \dotsc, k-1$, bit $A[i]$ flips $\lfloor \frac{n}{2^i} \rfloor$ times in a sequence of $n$ INCREMENT operations on an initially zero counter.
\begin{align} \sum_{i=0}^{k-1} \lfloor \frac{n}{2^i} \rfloor &< n \sum_{i=0}^{\infty} \frac{1}{2^i} \\ &= 2n \end{align}credit: the cost that an operation's amortized cost $\hat{c_i}$ exceeds its actual cost $c_i$.
requriments: $$\sum_{i=1}^{n} \hat{c_i} \geq \sum_{i=1}^{n} c_i$$
| $c_i$ | $\hat{c_i}$ | |
|---|---|---|
| PUSH | 1 | 2 |
| POP | 1 | 0 |
| MULTIPOP | min(k,s) | 0 |
$2 \times O(n) = O(n)$
set a bit to 1: 2
set a bit to 0: 0
The INCREMENT procedure sets at most one bit, $2 \times O(n) = O(n)$
Let $D_i$ be the data structure that results after applying the $i$th operation to data structure $D_{i-1}$.
potential function $\phi$: maps each data structure $D_i$ to a real number $\phi(D_i)$.
$\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1})$
hence, the total amortized cost of the $n$ operations is:
$$\sum_{i=1}^n \hat{c_i} = \sum_{i=1}^n c_i + \phi(D_n) - \phi(D_0)$$
Different potential functions may yield different amortized costs yet still be upper bounds on the actual costs. The best potential function to use depends on the disired time bounds.
define: $\phi$ to be the number of objects in the stack.
for PUSH: \begin{align} \hat{c_i} &= c_i + \phi(D_i) - \phi(D_{i-1}) \\ &= 1 + (s+1) - s \\ &= 2 \end{align}
for POP: \begin{align} \hat{c_i} &= c_i + \phi(D_i) - \phi(D_{i-1}) \\ &= 1 + (s-1) - s \\ &= 0 \end{align}
for MULTIPOP: \begin{align} \hat{c_i} &= c_i + \phi(D_i) - \phi(D_{i-1}) \\ &= k + (s-k) - s \\ &= 0 \end{align}
define: $\phi$ to be $b_i$, the number of 1s in the counter after the $i$th operation.
Suppose: the $i$th INCREMENT operation reset $t_i$ bits.
for INCREMENT: \begin{align} \hat{c_i} &= c_i + \phi(D_i) - \phi(D_{i-1}) \\ &= (t_i + 1) + (b_{i-1} - t_i + 1) - b_{i-1} \\ &= 2 \end{align}
load factor: $$\alpha(T) = \frac{\|\text{items of T}\|}{\|T\|}$$
insert an item into a full table, we expand the table with twice spaces.
The cost of the $i$th operation is: \begin{equation} c_i = \begin{cases} i \quad & \text{expand: if i - 1 is an exact power of 2} \\ 1 \quad & \text{otherwise} \end{cases} \end{equation}
The total cost of $n$ TABLE-INSERT operations is therefore: \begin{align} \sum_{i=1}^{n} c_i &\leq n + \sum_{j=0}^{\lfloor \lg n \rfloor} 2^j \\ &< n + 2n \\ &= 3n \end{align}
Halve the table size when deleting an item causes the table to become less than 1/4 full, rather than 1/2 full as before(引起振荡).