摊销分析 - 正确的方法？

Question

学习考试并偶然发现此练习。我无法用三种方法解决它。以下是文本：

假设我们在一系列n次操作下维护数据结构。设f（k）表示第k个操作的实际运行时间。对于以下每个函数f，确定单个操作产生的分摊成本。 （对于实际应用中，尝试在本说明中描述的方法的全部 。）

的（a）F（k）为最大的整数i，使得2^I分歧ķ。

来源：https://courses.engr.illinois.edu/cs473/fa2013/notes/14-amortize.pdf

我做了一个小桌子，试图得到一个概述

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 
f(k) 0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 ... 

我没有看到潜在的方法可以帮助这里的操作只是变得更昂贵随着时间的推移。因为同样的原因，银行家的方法似乎也不适用。所以我认为聚合方法是最合适的。

是我想出了n个操作的序列，但是我似乎无法改变它，这让我怀疑它是否是正确的做法。

编辑：所以它看起来像我误解了这个问题，我认为正确的表是这样的：

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 
f(k) 0 1 0 2 0 1 0 3 0 1 0 1 0 1 0 4 ... 

Answer 1

的情况下，任何人

快速回答使用银行家的方法，你可以“拯救网上搜寻这

'不变的信用额度（在这种情况下，每次操作2次就可以工作），并轻松支付更多的费用。

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 
f(k) 0 1 0 2 0 1 0 3 0 1 0 1 0 1 0 4 ... 
cr 2 3 5 5 7 8 10 9 11 12 14 15 17 18 20 18 ...