为考试而学习，偶然发现了这个练习。我无法用所有三种方法解决它。正文如下:
Suppose we are maintaining a data structure under a series of n operations. Let f(k) denote the actual running time of the kth operation. For each of the following functions f, determine the resulting amortized cost of a single operation. (For practice, try all of the methods described in this note.)
(a) f(k) is the largest integer i such that 2^i divides k.
来源: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 ...
最佳答案
快速回答以防有人用谷歌搜索
使用银行家的方法，您可以“节省”固定数量的信用(在这种情况下，每次操作 2 个信用就可以了)，并且可以轻松地弥补 future 更昂贵信用的成本。
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 ...
关于algorithm - 摊销分析 - 正确的方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42445917/