在斐波纳契堆的decrease-key操作中，如果允许在切割节点并将其合并到根列表之前丢失s > 1个 child (提升节点)，这会改变整体运行时的复杂性吗？我认为复杂性没有变化，因为潜力的变化是相同的。但我不确定我是否正确。
摊销分析如何证明这一点？
最佳答案
更改 Fibonacci 堆中的节点可以丢失的子节点数量确实会影响运行时间，但我怀疑如果你小心处理它，你仍然会得到相同的渐近运行时。
您是正确的，如果您允许每个节点在被提升回根之前失去多个子节点，则潜在的功能将不会改变。然而，势函数并不是斐波那契堆效率的来源。我们执行级联切割(在递减键期间将多个节点提升回根级别)的原因是为了确保具有 n 阶的树中的节点数量在 n 中呈指数级增长。这样，当执行 dequeue-min 操作并将树合并在一起使得每个顺序最多只有一棵树时，存储所有节点所需的树总数是节点数的对数。标准标记方案确保每棵 n 阶树至少有 Θ(φn) 个节点，其中 φ 是黄金比例(大约 1.618...)
如果您允许在将每棵树提升回根节点之前从每棵树中删除更多节点，我怀疑如果您将缺失子节点的数量限制在某个常数，您仍然应该获得相同的渐近时间范围，但是可能具有更高的常数因子(因为每棵树拥有更少的节点，因此需要更多的树)。如果您想要一个精确的值，可能值得写出数学以查看每棵树中的节点数得到的递推关系。
希望这对您有所帮助!
关于algorithm - 在已经失去 2 个或更多 child 后升级节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18278541/