algorithm - 空单的摊销分析示例

Question

我们希望有一组n线性列表来执行以下操作：

Insert(x,i)x：在列表中插入新元素i，此操作的成本为1。

Sum(i) :计算 list 中所有元素的总和，i并用计算的 替换list 中的所有元素，当我们使用此操作时sum，成本等于 list 中的元素数。i

如果我们从空列表开始并以任意方式进行上述操作，那么每个操作的摊销成本是多少：

1)insert : 2, sum : 1
2)insert : 1, sum : 2
3)insert : 1, sum : n
4)insert : n, sum : 1

谁能帮我理解如何解决这个例子，正确答案是什么？

Answer 1

(1) 为真，

暗示：

d deallocateNode 操作的总时间为 O(d) ，deallocateNode 的摊销复杂度为 O(d/d) = O(1) 。因此，一系列 allocateNode 和 d deallocateNode 操作的实际复杂度为 O(a+d)。

你可以使用潜在的方法。

Answer 2

这里所有操作的摊销成本是O(1)：

1. 根据问题陈述，该insert操作具有时间复杂度。O(1)

2. 该sum操作具有O(1)摊销时间复杂度，因为每个元素只处理一次（之后它被sum查询结果替换并且不再使用）。