algorithm - 动态数组大小调整的摊销分析

Question

关于调整动态数组大小（作为 ArrayList ADT 的一部分）的问题让我很困惑。

文本设置了将元素添加到数组末尾的场景。当数组达到其容量时，它的大小会增加一倍。新的较大数组使用旧数组的元素进行初始化。该过程的摊销分析给出了 O(n) 的复杂度。

然后提出以下问题：

当容量为 N 的数组已满时，不是将 N 个元素复制到容量为 2N 的数组中，而是将它们复制到具有 N/4 个附加单元的数组中，即容量为 (N + N/4) 的数组。证明对数组执行 n 次加法的序列仍然在 O(n) 中运行。

任何提示，如何解决这个问题的帮助都非常感谢。我不知道如何处理这样一个事实，即满容量的数组的大小增加了其当前大小的一小部分，而不是当前大小的倍数。

Answer 1

连续副本的大小为 N, N(5/4), N(5/4)^2, ...

因此，在 K 份拷贝之后，拷贝的总成本为

sum(i=0,K-1){ N(5/4)^i } 

此时数组具有 size N(5/4)^(K-1)。

所以剩下的就是证明

O( [ sum(i=0,K-1){ N(5/4)^i } ] / [ N(5/4)^(K-1) ] ) = O(1) .

换句话说，这是复制每个数组元素的总成本，即摊销成本。

证明等式为真非常简单，其逻辑与显示加倍的类似关系非常相似：

O( [ sum(i=0,K-1){ N(2)^i } ] / [ N(2)^(K-1) ] )

我不会剥夺你的乐趣。