摊销分析中会计方法与潜在方法的区别

Question

我正在阅读Cormen et al.In的算法介绍，这一章的标题是摊销分析，会计方法和潜在方法的区别如下

会计方法在数据结构的早期就对一些操作进行过高收费，将超额收费作为“预付信用证”存储在数据结构中的特定对象上。..。势方法将信用保持为整个数据结构的“势能”，而不是将信用与数据结构中的单个对象联系起来。

我试着使用可调整大小数组的例子来理解这一点，当没有空间插入element.What时，这个数组的大小会加倍，我无法理解的是下面这句话

将超额收费作为“预付信用证”存储在数据结构中的特定对象上

采用会计方法：

I=第一次操作的费用

c'i =第一次行动的摊销费用

I操作后的Si =数组大小

bi =第一次操作后的信贷余额

i   1  2  3  4  5  6  7  8  9 10
si  1  2  4  4  8  8  8  8 16 16
ci  1  2  3  1  5  1  1  1  9  1
c'i 3  3  3  3  3  3  3  3  3  3
bi  2  3  3  5  3  5  7  9  3  5

在这里，“存储在数据结构中的特定对象”到底是什么意思？

在势方法中，如果我使用phi为2n-m，其中n=数组中的currebt元素数和m=array大小。

                n     m    phi
empty            0     0    0 
add first elem   1     1    1
add secondelem   2     2    2
add third elem   3     4    2
add fourth elem  4     4    4
add fifth  elem  5     8    2

在这种情况下，数据结构作为一个整体的"...the“势能意味着什么，而不是将信用与数据结构中的单个对象联系起来。

Answer 1

会计方法：

会计方法的工作是确定一些额外的时间单位的支付，每个单独的业务，以使所有付款的总和不超过总实际成本。

你可以把它想象成一个银行账户，你对每个账户收取的费用略高于实际成本，而在一个池中的银行额外收费，这样很高成本的运营费用就可以低于实际成本，由储蓄池支付。这就把高成本的业务扩展到了整个过程中。

每次操作的费用必须足够大，使帐户余额保持为正，同时又足够小，这样才不会明显超出实际成本。

问题:帮助理解这一点: 在数据结构 中将超额收费存储为特定对象的“预付信用证”。回答: : 插入的成本是1 ，当表加倍时移动每个值的成本是1 。每个插入的插入1:成本=1(插入: 1)费用=3 bankedAmount= 2 bankBalance =2 注意: bankedAmount与此事务相关，但只是放入帐户--这是数据结构中特定对象的预付信用。插入#2: 成本=2 (doubleTableAndMove: 1*1 = 1)收费=3 bankedAmount= 1 bankBalance =3 插入#3 (doubleTableAndMove: 2*1 = 2，插入: 1)收费=3 bankedAmount= 0 bankBalance =3 插入#4: 成本=1(插入: 1)收费=3 bankedAmount= 2 =5 成本=5(：4*1 = 4，插入: 1)电荷=3 bankedAmount= -2 bankBalance =3 等。

潜在方法：

问:在这种情况下，什么是数据结构整体的"...the“势能，而不是将信用与数据结构中的单个对象联系起来。答:它类似于会计方法中的银行账户概念。势函数跟踪操作序列中任何时间的总额外时间，但它只基于结构的当前状态，而不管将其放入状态的所有操作。

还有更详细的这里进一步解释。

Answer 2

理解摊销最坏情况分析的最简单方法是将其看作是一长串调用中最坏情况的平均性能。特定的调用可能比值执行得更差或更好，但是所有调用的平均值将决定性地接近该值。