势法对斐波那契堆的摊销分析
Amortized Analysis of Fibonacci Heap with Potential Method
我正在尝试使用势法对斐波那契堆进行摊销分析。我正在努力理解 pop min / delete min 操作的分析。
在教程中，我可以找到限制“pop min”操作的分摊复杂度的方法，such as this one，教程作者将势设置为“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) 的分摊运行时间的方法？
我在标记 30:35 附近发现了答案 in this video。他指出，您只需取其大 O 隐藏的摊销操作的所有常量的最大值，并将其乘以潜在函数。
我正在尝试使用势法对斐波那契堆进行摊销分析。我正在努力理解 pop min / delete min 操作的分析。
在教程中，我可以找到限制“pop min”操作的分摊复杂度的方法，such as this one，教程作者将势设置为“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) 的分摊运行时间的方法？
我在标记 30:35 附近发现了答案 in this video。他指出，您只需取其大 O 隐藏的摊销操作的所有常量的最大值，并将其乘以潜在函数。