动态数组大小调整的摊销分析
Amortized analysis of dynamic array resizing
关于调整动态数组大小（作为 ArrayList ADT 的一部分）的问题让我很困惑。
文本设置了一个场景，其中元素被添加到数组的末尾。当数组达到其容量时，它的大小会加倍。新的较大数组使用旧数组的元素进行初始化。对该过程的摊销分析给出了 O(n) 的复杂性。
然后问下面的问题：
When the array of capacity N is full, instead of copying the N elements into an array of capacity 2N, they are copied into an array with N/4 additional cells, i.e an array of capacity (N + N/4). Show that performing a sequence of n additions to
the array still runs in O(n).
非常感谢有关如何解决此问题的任何提示和帮助。我不知道如何处理这样一个事实，即满容量阵列的大小增加了其当前大小的一小部分，而不是其当前大小的倍数。
连续副本的大小为 N，N(5/4)，N(5/4)^2，...
因此，复制K次后，复制的总成本为
sum(i=0,K-1){ N(5/4)^i }
此时数组的大小为 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) ] )
我不会带走你的乐趣。
关于调整动态数组大小（作为 ArrayList ADT 的一部分）的问题让我很困惑。
文本设置了一个场景，其中元素被添加到数组的末尾。当数组达到其容量时，它的大小会加倍。新的较大数组使用旧数组的元素进行初始化。对该过程的摊销分析给出了 O(n) 的复杂性。
然后问下面的问题：
When the array of capacity N is full, instead of copying the N elements into an array of capacity 2N, they are copied into an array with N/4 additional cells, i.e an array of capacity (N + N/4). Show that performing a sequence of n additions to the array still runs in O(n).
非常感谢有关如何解决此问题的任何提示和帮助。我不知道如何处理这样一个事实，即满容量阵列的大小增加了其当前大小的一小部分，而不是其当前大小的倍数。
连续副本的大小为 N，N(5/4)，N(5/4)^2，...
因此，复制K次后，复制的总成本为
sum(i=0,K-1){ N(5/4)^i }
此时数组的大小为 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) ] )
我不会带走你的乐趣。