我正在尝试使用潜在方法对斐波那契堆进行平摊分析。我正在努力理解pop min/delete min操作的分析。
在教程中，我可以找到限制"pop min"平摊复杂度的方法。操作，比如这一个，教程作者将势能设置为"phi(fib heap) =根节点数+ 2 *失败节点数";。然后分析popmin操作的两个步骤:
-
在第一步中，它删除最小节点并将最小节点的子节点放到根列表中。通过对树的分析(任何节点都不允许丢失一个以上的子节点)，您知道这只需要O(log n)次操作。这部分我明白了。
-
在第二步中，您通过迭代地合并所有相同大小的树来执行清理。对我来说，这就是分析令人困惑的地方:
在平摊分析中，成本总是"实际成本+潜在变化"。他们分析实际成本为O(t + m + d)——m图是合并次数，d图是合并后的树数，而t图是在对根列表进行线性扫描后进行清理之前的节点数。势的变化在上面用-m表示——根列表的大小随着合并次数的减少而减小。t = m + d，所以运算是O(m + d)，到目前为止，我遵循。
然后，在链接的教程中，他将电势的变化加上O(m + d)，得到O(m + d) - m = O(d)…这毫无意义!我很确定，根据大0的定义，这是不可能的。尽管如此，这仍然是他对视频中popmin操作的平摊代价的解释。
谁能解释一下他说的O(m + d) - m是什么意思，或者，如果不能解释，一种分析fibonacci堆中的popmin操作的方法，以获得O(log n)的平摊运行时间?
我在这个视频中找到了答案，大约在mark 30:35。他说，你只需取所有平摊操作的常数的最大值隐藏在它们的大0中，并将其乘以势函数。