在摊销分析中使用潜力和会计方法 [英] Using the potential and the accounting methods in amortized analysis

问题描述

我已经阅读了有关会计和潜在方法的信息，但仍无法解决以下问题:

解决方案

直觉

通过分析每个操作的昂贵情况和便宜情况，您可以了解如何为每个操作收费(然后您可能需要一些小的修正来固定"数字)

通过查看数据结构的重要参数，您可以构建一个潜在函数(例如，这里是s2中的元素数)

• 此外，在这里看到许多示例确实有帮助

记帐方法:

让每次插入收取两个硬币:一个用于从s2弹出元素，第二个用于将元素插入s1并让每个删除收取一个硬币，该硬币将用于删除s1中的元素.

然后请注意，银行中的贷方不能为负，因为如果s1不为空，则我们仅支付操作的实际成本(这是s1的唯一删除项)，并且s1为空，则操作从s2弹出并插入到我们已经收费的s1中.(重要的是，我们假设我们从空数据结构开始，或者说，我们对数据结构的每个初始状态都有适当的信誉)

现在您可以看到，对于每组操作，我们的总信用3n覆盖了操作的实际成本(并且我们在s2中获得了其余元素的信用保证金)，因此这些是有效的摊销范围./p>

要使用潜在函数进行求解，请考虑以下函数:

电位(DataStructure)= 2 * s2中的元素数

回想一下我们是这样计算的:

OP.A的摊销成本= OP.A的实际成本+电位(DS之后)-电位(DS之前)

所以我们得到了(表示k中s2中的元素数):

用于插入: 1 + 2(k + 1)-2k = 3

廉价删除: 1 + 2k-2k = 1

用于昂贵的删除: 1 + 2k + 0-2k = 0(实际成本是1 + 2k，因为我们从s2弹出并向s1插入每个元素，然后从s1弹出一个元素)

I have read about the accounting and the potential methods but I still having trouble solving such questions:

解决方案

Intuition

By analyzing for each operation its expensive case and cheap case you can build an idea of how to charge each operation (then you may need some small fixes to 'fix' the numbers)

By looking at the important parameter of the data structure you can build a potential function (here for example it is the number of the elements in s2)

• Also, seeing many examples really helps here

The accounting method:

Lets charge each insertion two coins: one will be used to pop the element from s2, the second will be used to insert the element to s1 and Lets charge each deletion one coin that will be used to delete the element from s1.

Then note that the credit in the bank cannot be negative because if s1 is not empty then we are paying only for the actual cost of the operation (which is the only deletion from s1) and if s1 is empty then the operations are popping from s2 and inserting to s1 which we already charged for. (it is important to note that we assume we start from empty data structure, OR, that we got the proper credit for every initial state of the data structure)

Now you can see that for each set of operations our total credit of 3n covers the actual cost of the operations (and we got a margin of the credit of the remaining elements in s2) and hence these are valid amortized bounds.

To solve with potential function lets consider the function:

Potential(DataStructure) = 2 * Number of elements in s2

Recall that we compute like this:

amortized cost of OP.A = actual cost of OP.A + Potential(DS after)-Potential(DS before)

So we got (denote number of elements in s2 in k):

For insertion: 1 + 2(k+1)-2k = 3

For cheap deletion: 1 + 2k - 2k = 1

For Expensive deletion: 1+2k + 0 - 2k = 0 (the actual cost is 1+2k because we pop from s2 and insert to s1 each element and then pop one element from s1)

这篇关于在摊销分析中使用潜力和会计方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！