在堆摊销分析 [英] Amortized analysis on Heap

问题描述

当我跑到这个话题。

我在今天的书第5-1页底部的>二项队列的斐波纳契堆和斜堆的有O（1）摊余成本进行的插入的操作和O（log n）的摊销的删除的操作成本。接下来，作者写的配对堆的有O（1）摊余成本进行插入操作和O（log n）的摊余成本进行删除操作。

I read in this book on the bottom of page 5-1 that Binomial Queues, Fibonacci Heap and Skew Heap have O(1) amortized cost for insert operations and O(log n) amortized cost of delete operations. Next the authors write that the Pairing Heap has O(1) amortized cost for insert operations and O(log n) amortized cost for delete operations.

在此功课中的三（3）分配和解决方案，在这 没有定义堆型链接写了O（日志N ），用于插入 和O（1）删除。

on this homework the third (3) assignment and solution on this link without defining the type of heap wrote O(log n) for insert and O(1) to delete.

在此作业另一个作者的二项式说：堆的有O（log n）的用于插入操作和O（1）摊余成本进行删除操作。

on this homework another the author says a Binomial Heap has O(log n) for insert operations and O(1) amortized cost for delete operations.

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

The question is, which one is correct? I'm quite confused.

推荐答案

由于堆有元素的非负数，它总是#inserts与GE的情况; #deletes如果我们开始与空堆。随着分期时间界限，O（1）插入/ O（log n）的删除，因此意味着O（log n）的插入/ O（1）删除，通过改变会计使插入prepays其相应的删除（如果现存）。有没有矛盾存在。

Since the heap has a nonnegative number of elements, it's always the case that #inserts ≥ #deletes if we start with an empty heap. With amortized time bounds, O(1) insert/O(log n) delete hence implies O(log n) insert/O(1) delete, by changing the accounting so that an insert prepays its corresponding delete (if extant). There's no contradiction there.

这篇关于在堆摊销分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！