使用斐波那契数的大小调整动态数组的大小
Resizing dynamic array with the size of Fibonacci numbers
我们有一个大小为斐波那契数列的动态数组。假设 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)) 时间。
你能帮我解决这个问题吗？
如果我们假设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)。
我们有一个大小为斐波那契数列的动态数组。假设 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)) 时间。 你能帮我解决这个问题吗？
如果我们假设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)。