在decrease-key斐波那契堆的操作中，如果允许s > 1在切割节点并将其融合到根列表（提升节点）之前丢失子节点，这是否会改变整体运行时复杂度？我认为复杂性没有变化，因为潜力的变化是一样的。但我不确定我是否正确。
摊销分析如何证明这一点？
问问题
184 次
1 回答
0
更改斐波那契堆中节点可能丢失的子节点数量确实会影响运行时间，但我怀疑如果您小心操作方式，您仍然会获得相同的渐近运行时间。
如果您允许每个节点在被提升回根之前丢失多个子节点，那么潜在功能将保持不变，这是正确的。然而，势函数并不是斐波那契堆效率的来源。我们执行级联切割（在减少键期间将多个节点提升到根级别）的原因是为了确保具有 n 阶的树中有许多节点，这些节点在 n 中是指数的。这样，当执行 dequeue-min 操作并将树合并在一起以使每个顺序最多有一个树时，存储所有节点所需的树总数与节点数成对数。标准标记方案确保每棵 n 阶树至少有 Θ(φ n ) 节点，其中 φ 是黄金比例（大约 1.618...）
如果您允许在将它们提升回根之前从每棵树中删除更多节点，我怀疑如果您将丢失子节点的数量限制在某个常数上，您仍然应该获得相同的渐近时间界限，但可能使用更高的常数因子（因为每棵树拥有更少的节点，因此需要更多的树）。如果您想要一个精确的值，可能值得写出数学来查看每棵树中节点数的递归关系。
希望这可以帮助！
于 2013-09-11T00:37:18.783 回答