我已经阅读了一些关于摊销分析的帖子,但在理解潜力法(potential method)方面仍有一些疑问。
主要问题在于如何开发一种正式的潜力函数?以及如何评估潜力函数的正确性?
例如,有一个问题:
对数据结构执行n个操作的序列。如果i是2的幂,则第i个操作的成本为i,否则为1。使用潜力法确定每个操作的平摊代价。
采用潜力函数,我们首先应该提出一个潜力函数:Φ = 2 * (number of expensive operations) - (total number of operations)。有人告诉我这很直观,但即使经过几个小时的思考,我也想不到这个答案...
我发现有一个类似的问题:需要使用潜力函数方法找到序列的平摊成本。然而,我认为答案是关于记账法(account method)的。
主要问题在于如何开发一种正式的潜力函数?以及如何评估潜力函数的正确性?
例如,有一个问题:
对数据结构执行n个操作的序列。如果i是2的幂,则第i个操作的成本为i,否则为1。使用潜力法确定每个操作的平摊代价。
采用潜力函数,我们首先应该提出一个潜力函数:Φ = 2 * (number of expensive operations) - (total number of operations)。有人告诉我这很直观,但即使经过几个小时的思考,我也想不到这个答案...
我发现有一个类似的问题:需要使用潜力函数方法找到序列的平摊成本。然而,我认为答案是关于记账法(account method)的。
k
是2
的幂时,它必须支付k
单位的费用。 因此,我们可以将这些k
摊销到以前的k/2
单位中。通过这种方式,我们开发出了一个具有常数2
的势能函数。 - chain ro