斐波纳契堆的命令符号减法

Question

可以单独订购符号意味着：

$ o（d（n））+ o（t（h）） - t（h）= o（d（n））$

我的猜测是，由于o（h））中的常量如果常量为0.

，则不能在减法之后仍然存在。

嗯，这实际上是这种情况，但有潜在的因素。此等式出现在CLRS（518）中的Fibonacci堆分析中。此步骤的理由来自潜在的潜在功能。根据作者，“我们可以扩展潜力的单位来统治隐藏在 $ o（t（h））$ ”中。我想知道这种情况如何，但并不真正知道如何问这个复杂的问题。

Answer 1

正如您指出，第一个等式不一定是正确的。

让我通过显式添加乘法常量来重写它： $ \ alpha d（n）+ \ beta t（h） - \ gamma t（h）= o（d（n））$ ，其中 $ \ gamma= 1 $ 。 这里的问题是 $ \ beta $ 可能大于 $ \ gamma= 1 $ 。

作者说的是，而不是认为一个单位 在您的潜在函数 $ \ phi（h）$ 贡献一个潜力单位，您可以想象它实际上代表了 $ \ gamma $ 潜力单位。 使用新的潜在函数 $ \ phi'（h）$ 定义为 $ \ phi'（ h）=gamma \ cdot \ phi（h）$ 。如果这样做，那么您可以控制上述等式中 $ \ gamma $ 的值，而 $ \ Beta $ 保持不变。

挑选 $ \ gamma \ ge \ beta $ 确保这一点 $ \ alpha d（n）+ \ beta t（h） - \ gamma t（h）=alpha d（n） - \ undbrace {（\ gamma - \ beta）} _ {\ ge 0} t（h）\ le \ alpha d（n）= o（d（n））$ ，如需要。