介绍
动态数组在每次容量用尽时，重新申请 2 倍于当前数组的空间，并将原数组中的内容拷贝到新的空间，然后释放原数组的内存空间。对于动态数组，每次插入的花费有两种情况：
- 容量够用，我们只需要存储新的元素
- 容量不够用，创建新的空间，拷贝原数组进新的空间，再存储这个新的元素
分析方法有许多，统称为：amortized analysis（分摊分析）
Lecture 21: Amortized Analysis
统计分析（aggregate method）
把 n 词操作花费求和，然后取平均值。
每次扩容时，后半部分元素统一进行第一次移动，而这些元素之后的所有移动操作也是一起发生的，因而我们发现元素是以组为单位，组内的元素移动次数相同。那么有多少个这种组呢？第一组是单个元素，第二组也是单个元素，第三组是两个元素，第四组是四个元素，第五组是 8 个元素，... ，以此类推。而：
$$
1 + 1 + 2+ 2^2 + \cdots + 2^i = n
$$
$$
i = \log_2 n -1
$$
而这些组的移动次数分别是多少呢？最后一组元素只移动一次，倒数第二组元素移动 2 次，以此类推。所以总的移动次数是：
$$
1\times 2^i+2\times 2^{i-1}+3\times 2^{i-2}+\cdots+k\times 1
$$
$$
k = \log_2n + 1
$$
这个式子挺有规律的，我们可以将其分为很多个组，第一组是：
$$
1 + 1 + 2+ 2^2 + \cdots + 2^i = n
$$
第二组是：
$$
1 + 1 + 2+ 2^2 + \cdots + 2^{i-1} = \frac{n}{2}
$$
以此类推。
于是我们得到上式的等价表示：
$$
n + \frac{n}{2} + \cdots + 1 = 2n-1
$$
所以移动的平均次数是：$\frac{2n-1}{n}$，也就是每个元素最多移动 2 次，加上插入操作，最多三个操作。
银行算法（banker method）
对动态数组的插入来说，大部分（后半部分）插入操作是不需要重新分配内存的，是廉价的操作。而少部分操作是需要重新分配内存的，是复杂的操作。我们可以试着想象在每次廉价操作的时候存储额外的费用，相当于存款，来支付复杂操作的费用。
我们假设一次基本的操作费用是一个硬币，当我们插入了一个下标为 n 的元素时：
- 我们要花费第一个硬币，作为基本的插入操作花费
- 我们还要存储第二个硬币，作为新插入的 n 在重新分配内存时移动它的费用
- 最后我们要存储第三个硬币，作为数组的前半部分的某个对应元素重新分配内存时移动费用
这样来计算，每个插入操作最多需要付出三个硬币，而第一个元素是不需要第三个硬币的。所以费用总数是：3n-1。
势能算法（Potential Method）
首先说明一下，目前我对这个方法还是无法直观的理解。先祭出这个势能函数：
$$
\Phi(h) = 2n-m
$$
其中 n 是当前数组元素的个数，m 是当前数组内存空间大小。
每次插入的费用函数定义为：
$$
c+\Phi(h')-\Phi(h)
$$
c 表示当前插入操作的总的花费，$\Phi(h')$是插入后的势能函数，$\Phi(h)$是插入前的势能函数。
这里分为两种情况：
- 如果
n<m，不必扩容，c=1，势能函数相差 2，所以加起来是 3 - 如果
n=m，那么就要扩容，c=n+1，$\Phi(h')=2(n+1)-2n$，$\Phi(h)=2n-n$，加起来还是 3
所以费用函数其实是一个等于 3 的常数函数。