动态数组的扩容为什么经常是两倍扩容

摘要: 动态扩容数组的分析

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

我们在编程中经常会用到数组。初始化一个数组时需要分配一块连续的内存空间，那么这就需要在分配的时候知道数组的长度，但业务场景中往往事先不知道对数组长度的需求是多少，因此只能拍脑袋定一个长度。如果定的过长，开出来的空间会有很多闲置浪费，如果定的过短，那么开出来的空间无法满足需求。

因此一种处理方式是，初始化一个空数组时，先分配比较少的空间，随着插入的进行，当空间不够的时候再扩容。我们经常用的 C++ 的 vector 和 Python 的 list 中都有这种动态扩容机制，其它的语言和组件中也很常见。如果编程经验多的话，会发现扩容的策略经常是两倍扩容，即新分配的连续内存空间长度是上一次长度的两倍。

前面几篇文章我们已经介绍了摊销分析的相关知识，对动态扩容数组，我们依然可以进行摊销分析。本文我们先介绍一下两倍扩容的动态扩容数组，然后进行摊销分析，得出该数组上的任意操作序列上，每个操作都是摊销 $O(1)$ 的。然后我们再对比一下其它的扩容策略，比如每次扩容固定长度，就可以发现两倍扩容在时间复杂度上的好处。

两倍扩容的动态扩容数组

现在用动态扩容数组 $A$ 来存储表 $S$ 中的元素，为了分析方便，假设数组只有一个 add(x) 操作，即在数组末尾插入元素 x。

在创建数组时，需要指定数组长度 $N$，然后进行插入过程，已经插入的元素数记为 $n$，当 $n=N$ 且调用 add 时，就会触发扩容，根据两倍扩容的策略，动作如下：

(1) 分配一个容量为 $2N$ 的新数组 $B$。
(2) 将 $A[i]$ 拷贝到 $B[i]$，$i=0,1,\cdots,N-1$。
(3) 释放 $A$ 的空间。

初看上去，这个数组替换策略似乎是很低效的，因为替换一个长 $n$ 的数组需要的运行时间为 $\Theta(n)$，但是实践经验表明在一个空的动态扩容数组上进行一系列插入操作是非常有效，下面我们来分析一下。

为了分析简单，我们不考虑原数组的垃圾回收问题。

摊销分析

前面的文章中我们知道，摊销分析常见的方法有聚合分析法、记账法和势函数法，这里用记账法进行分析。一元可以支付一个常数时间的计算，在执行一个操作时，银行中的钱应该足够支付该操作所需的时间。

定理

设 $S$ 是由动态扩容数组 $A$ 实现的表，初始时 $S$ 是空表，$A$ 是大小 $N=1$ 的数组，后续进行 $n$ 个 add 操作在最坏情况的时间复杂度为 $O(n)$。

证明

假设一元可以支付 $S$ 上每个操作的执行，但不包括数组扩容的时间。同时，假设大小为 $k$ 的数组扩展成大小为 $2k$ 的数组需要 $k$ 元来复制 $k$ 个元素。

现在对 add 操作收取 3 块钱，这样对于没有造成扩容的 add 操作，多收了两块钱，将其存入银行。

扩容的触发条件是调用 add 时数组大小为 $2^{i}$，$i\geq 0$，此时需要支付 $2^{i}$ 块钱，这需要从银行取钱，考虑此时银行的钱是否足够支付。

上一次在银行取钱实在元素个数第一次大于 $2^{i-1}$ 的时候，从上次取钱到这次取钱这期间存入银行的钱肯定是还没用过的，这期间插入的元素存储在 $2^{i-1}$ 到 $2^{i}-1$ 这些位置，共 $2^{i}-2^{i-1}$ 个元素，在插入这些元素时，每个元素额外存入了 2 块钱，因此这部分元素存下来的钱为：$2 (2^{i} - 2^{i-1}) = 2^{i}(2 - 1) = 2^{i}$ 元，刚好够支付此次扩容需要额外支付的钱。

因此这是一个有效的摊销方案，即每次调用 add 支付 3 块钱即可支付所有所需的算力。即：用 $3n$ 块钱即可支付 $n$ 个 add 操作所需的算力。

$\Box$

固定增量扩容

表在扩容时，除了扩大一倍，还有一个最直接的方法是指定一个增量参数 $k$，当数组扩容时，新的数组将固定地增加 $k$ 个位置。但是这种策略慎用，对于大多数应用，倍增式的扩容策略是正确的。

下面我们进行摊销分析。由于场景比较简单，直接用聚合分析即可。

摊销分析

定理

如果创建一个固定增量扩容参数 $k > 0$ 的空表，后续进行 $n$ 个 add 操作的时间复杂度为 $\Omega(n^{2})$ 时间。

证明

令 $c_{0}$ 为数组的初始大小。当表中元素个数为 $c_{0} + ik$ 时，一个 add 操作将引起扩容，其中 $i=0,1,\cdots,m-1$，$m = \lfloor\frac{n-c_{0}}{k}\rfloor$，因此处理扩容的总时间为：

$$\sum\limits_{i=0}\limits^{m-1}(c_{0} + ki) = c_{0}m + k\sum\limits_{i=0}\limits^{m-1}i = c_{0}m + k\frac{m(m-1)}{2}$$

而 $m = \Omega(n)$，因此 $n$ 个 add 操作的总时间为 $\Omega(n^{2})$。

总结

倍增式的动态扩容策略比固定增量的扩容策略时间复杂度要好，在常见的语言和组件中，倍增的倍数常见的是 2，但是也有其它的倍数。

---