algorithm - 堆上的摊销分析

Question

当我跑到这个话题时。

我在本书第 5-1 页底部读到，二项式队列、斐波那契堆和倾斜堆具有 O(1) 的插入操作摊销成本和 O(log n) 的删除操作摊销成本。接下来作者写道，配对堆的插入操作摊销成本为 O(1)，删除操作的摊销成本为 O(log n)。

在此作业中，此链接上的第三 (3) 个分配和解决方案 没有定义堆的类型，写入 O(log n) 用于插入，O(1) 用于删除。

在这个作业中，另一位作者说二项式堆对于插入操作具有 O(log n) 和对于删除操作具有 O(1) 摊销成本。

问题是，哪一个是正确的？我很困惑。

Answer 1

由于堆有非负数的元素，如果我们从一个空堆开始，总是会出现 #inserts ≥ #deletes 的情况。在分期付款的时间范围内，O(1) 插入/O(log n) 删除因此意味着 O(log n) 插入/O(1) 删除，通过更改记帐以便插入预付其相应的删除（如果存在）。那里没有矛盾。