我正在尝试使用潜在方法对斐波那契堆进行摊销分析。我正在努力理解对 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) ...这没有任何意义！我相当肯定，根据大 O 的定义，这是不可能的。尽管如此，这仍然是他在视频中为 popmin 操作摊销成本的理由。
任何人都可以用 O(m + d) - m 来解释他的意思，或者如果没有，可以用一种分析斐波那契堆中的 popmin 操作以获得 O(log n) 的摊销运行时间的方法吗？