动态数组的分摊分析

介绍

动态数组在每次容量用尽时，重新申请 2 倍于当前数组的空间，并将原数组中的内容拷贝到新的空间，然后释放原数组的内存空间。对于动态数组，每次插入的花费有两种情况：

1. 容量够用，我们只需要存储新的元素
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 }_{2}n+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 的元素时：

1. 我们要花费第一个硬币，作为基本的插入操作花费
2. 我们还要存储第二个硬币，作为新插入的 n 在重新分配内存时移动它的费用
3. 最后我们要存储第三个硬币，作为数组的前半部分的某个对应元素重新分配内存时移动费用

这样来计算，每个插入操作最多需要付出三个硬币，而第一个元素是不需要第三个硬币的。所以费用总数是：3n-1。

势能算法（Potential Method）

首先说明一下，目前我对这个方法还是无法直观的理解。先祭出这个势能函数：

$$\mathrm{\Phi }(h)=2n-m$$

其中 n 是当前数组元素的个数，m 是当前数组内存空间大小。

每次插入的费用函数定义为：

$$c+\mathrm{\Phi }(h^{\prime })-\mathrm{\Phi }(h)$$

c 表示当前插入操作的总的花费， $\mathrm{\Phi }(h^{\prime })$ 是插入后的势能函数， $\mathrm{\Phi }(h)$ 是插入前的势能函数。

这里分为两种情况：

1. 如果n<m，不必扩容，c=1，势能函数相差 2，所以加起来是 3
2. 如果n=m，那么就要扩容，c=n+1， $\mathrm{\Phi }(h^{\prime })=2(n+1)-2n$ ， $\mathrm{\Phi }(h)=2n-n$ ，加起来还是 3

所以费用函数其实是一个等于 3 的常数函数。