当我跑到this topic的时候。
我在5-1页底部的book中读到,二项式队列、fibonacci堆和斜堆有o(1)插入操作的摊余成本和o(log n)删除操作的摊余成本。接下来,作者写道,配对堆有o(1)插入操作的摊余成本和o(log n)删除操作的摊余成本。
关于这个homework的第三(3)个赋值和关于这个的解
link不定义要插入的堆写o(log n)的类型
和O(1)删除。
在这篇作业中,作者说二项式堆有O(log n)用于插入操作,O(1)用于删除操作的摊余成本。
问题是,哪一个是正确的我很困惑。

最佳答案

由于堆具有非负数量的元素,因此如果从空堆开始,通常情况下会出现插入数大于删除数的情况在分期偿还的时间范围内,o(1)insert/o(log n)delete因此意味着o(logn)insert/o(1)delete,通过更改记帐,使insert预付其相应的delete(如果存在)。没有矛盾。

08-08 06:30