动态数组的增长

动态数组，例如C++的vector，有自动增长的机制，当容量不够，就会自动成倍增长，有2倍，有1.5倍，这样很容易得出两个问题

假设有n个元素

如果是成倍增长，倍增因子为m，则 $m^i = n$ ，分配次数 $i = \log_{m}n$ ，第 $i$ 次扩容，将会复制 $m^i$ 个元素，则该次push_back的时间复杂度为O(n)，为最糟糕的时间复杂度

$\sum_{i=1}^{\log_{m}n}m^i \approx \frac{nm}{m-1} = O(n)$

但是根据平摊分析，n个操作仍可以在O(n)时间内完成，因此每个操作的平摊耗费为$O(n)/n = O(1)$

假设每次增长k个，那么$ki = n$, 分配次数为 $i = \frac{n}{k}$ ,第 $i$ 次扩容，将会复制 $ki$ 个元素，则该次push_back的时间复杂度为$O(n^2)$

$\sum_{i = 1}^{\frac{n}{k}}ki \approx ni = O(n^2)$

均摊下来得到 $O(n^2) /n = O(n)$

因此选择成倍增长

1.5还是2？

假设$a_1 = 4, q = 2$

当选择2的时候，第n次扩容，需要的内存为

$a_n = a_1*q^{n-1} = 4*2^{n-1}$

假设释放的内存块都以最佳的情况分布(连续)，当进行第n次分配时，由于前面释放的内存是连续分布的，因此拥有一块大块的空闲内存，其大小为

$S_n = a_1*\frac{1-q^{n-1}}{1-q}=4*2^{n-1}-4$

当进行第n次扩容的时候，所需$a_n$

$a_n - S_n = 4 > 0$

因此，即使之前释放的内存块都是连续排列的，也无法满足该次的分配

$a_n - S_n = 8 - 4*1.5^{n-1}$

当n增长到一定的数值后，差值就会变为小于0，此时便可以复用之前所释放的所有内存空间