用Fibonacci数的大小调整动态数组的大小

Question

我们有一个Fibonacci数大小的动态数组。假设F(k)是数组的当前大小(F(K)是斐波那契级数的第k个数)。我们这里有两个规则:1)如果在数组中插入一个元素后，数组元素的数量是F(k-1)，我们创建一个大小为F(k+1)的新数组，并将前面的元素复制到新数组中。2)如果从数组中删除一个元素后，数组元素的数量为F(k-3)，我们创建一个大小为F(k-1)的新数组，并将之前的元素复制到新数组中。

首先，数组是空的，大小为2。我们想要证明，对于每个操作序列(插入或删除)，每个操作都有O(1)的摊销时间复杂度。

为了解决这个问题，我意识到在两个数组增长操作之间至少有F(k-1)-F(k-2)操作，复制元素需要O(F(k-1))时间。此外，在两个数组收缩动作之间至少有F(k-2)+F(k-3)个动作，复制元素需要O(F(k-3))时间。你能帮我解决这个问题吗？

Answer 1

摊销分析是对复制的每一次求和，如果我们假设为n = F(k)，则为T(n) = F(1) + F(2) + ... + F(k)。我们知道T(n) = F(k+2) -1。

作为T(n) = F(k+2) - 1 = F(k+1) + F(k) - 1 = 2F(k) + F(k-1) - 1= 2*n + F(k-1) - 1< 3n - 1，因此摊销成本是T(n)/n < 3，它意味着摊销意义上的T(n) = Theta(1)。