0

我们有一个斐波那契数大小的动态数组。假设 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)) 时间。你能帮我解决这个问题吗？

4

1 回答 1

0

T(n) = F(1) + F(2) + ... + F(k)如果我们假设，摊销分析是每次复制的总和n = 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)摊销。

于 2018-12-12T14:49:42.767 回答