java - Integer set ADT的摊销分析(Java考试)

Question

如果我没有误解摊销分析，那么这道试题真的很狡猾。所以我想我误会了。

“实现一个容量为n的集合ADT，可以包含所有小于等于n的正整数。需求:

新集合(n) - O(n)

插入(i) - O(1)

成员(i) - O(1)

union(s) - O(1)，其中 s 是相同类型的 Set。如果愿意，您可以销毁 s。

对操作进行运行时间分析。如果需要，请使用摊销分析。”

您可以将其实现为大小为 n 的 boolean 数组。十分简单。唯一难点是联合操作。我想不通，解决方案建议使用 for 循环执行“size(s)”AND 操作，这显然是 O(n)。但是在 for 循环之后，他们将 s 的 boolean 数组设置为 null，并声称这使得分摊运行时间为 O(1)!

当然，如果你继续将你的新集合与相同的集合 s 联合 n 次，你的平均运行时间为 O(1)，因为只有一个操作是 O(n)，其余的是常数.但是我们为什么要关心这个呢？您如何证明这种分析的合理性？进行 n 次无意义的操作如何成为摊销分析的公平基准？

Answer 1

让我们暂时忽略 insert(i) 和 member(i) 查询，只关注创建新集合和形成联合。

诀窍在于，如果您在执行并集之后销毁 s，那么在任何新的集合创建和并集操作序列中，永远不可能执行比集合创建更多的并集:每个并集操作要求当前至少存在 2 个集合，并将存在的集合总数减少 1。

考虑任何 c 个新集合创建序列和 u < c 个并集操作:这将花费 O(nc+nu+c+u) = O(nc+nu) 时间。 (集合创建允许为 O(n)，这也是直接联合计算的时间。)我们知道 u < c 的事实意味着我们可以设计一个新的成本系统，其中，对于 任何这样的序列，我们都可以将每个联合操作与之前发生的不同集合创建相匹配，并收取联合的时间与其匹配的集合创建。在这个新的成本系统中，所有并集操作都需要时间 O(1)，所有与后面的并集操作匹配的集合创建都需要时间 O(n+1)+O(n+1) = O(n)，而不匹配集合创建需要时间 O(n+1) = O(n) 和以前一样。请注意，尽管个别成本有所变动，但此新系统下的总成本与原始系统相同:O(2nu+n(c-u)+c+u) = O(nc+nu ).

因此，如果悲观地假设每个 集合创建都将被计入某些 future 的联合操作，那么每个集合创建的成本变为(或者更确切地说，保持)O(n+1)+O (n+1) = O(n)，并且每个联合操作的成本变为 O(1)，这个甚至更新的成本将是新成本系统的上限(即永远不会低估)，这是真正的成本集合创建和联合操作的任何序列。