摊销分析分堆？ [英] amortized analysis on min-heap?

问题描述

如果对空分堆，我们做的 N 任意插入和删除操作，（与删除最小堆给定的位置）。为何将摊销分析 O（1）键，删除是 O（log n）的？

If on empty min heap we doing n arbitrary insert and delete operations, (with given location of delete in min-heap). why the amortized analysis for insert is O(1) and delete is O(log n)?

a) insert O(log n), delete O(1)

b) insert O(log n), delete O(log n) 

c) insert O(1), delete O(1)

d) insert O(1), delete O(log n)

任何人能澄清一下吗？

any person could clarify it for me?

推荐答案

根据您的问题和应对的意见，我将承担二叉堆。

Based on your question and responses to comments, I'm going to assume a binary heap.

首先，将最坏的情况下的插入是O（log n）的和最坏的情况下为除去最小项目为O（log n）的。这遵循从堆的树结构。也就是说，对于n个项的堆，有在树的log（n）的水平。

First, the worst case for insertion is O(log n) and the worst case for removal of the smallest item is O(log n). This follows from the tree structure of the heap. That is, for a heap of n items, there are log(n) levels in the tree.

插入包括（逻辑）加入该项目的最低最右边的树中的节点，然后沸腾起来所要求的水平。如果新的项比所述根小，那么它必须气泡一路顶端 - 所有的log（n）的水平。所以，如果你插入的数字10，9，8，7，6，5，4，3，2，1成分堆，你会打的最糟糕的情况下，每一个插入。

Insertion involves (logically) adding the item as the lowest right-most node in the tree and then "bubbling" it up to the required level. If the new item is smaller than the root, then it has to bubble all the way to the top--all log(n) levels. So if you insert the numbers 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 into a min-heap, you'll hit the worst case for every insertion.

拆卸的最小元素涉及的最后一项替代最低项（根），然后选择筛选的项目到它应有的位置。同样，这可能需要多达日志（n）的操作。

Removal of the smallest element involves replacing the lowest item (the root) with the last item and then "sifting" the item down to its proper position. Again, this can take up to log(n) operations.

这是最坏的情况。的的平均值的情况有很大不同。

That's the worst case. The average case is much different.

请记住，在二叉堆，有一半的节点都是叶子 - 他们没有孩子。因此，如果你在插入随机的物品，一半的时间的要插入所属的最低水平，不存在泡沫起来的项目来做。因此，有一半的时间你的插入操作是O（1）。另一半，一半的的这些的将属于第二个层次上了。等等。你其实记录的唯一时间（n）的插入操作是，当你插入产品比现有的根项目小。这是很可能的，那么，所观察到运行时的行为是插入为O（1）。事实上，这将是的行为，如果你插入一个排序的数组到一个最小堆。即，如果你要按照该顺序插入的值1，2，3，4，5，6，7，8，9，10

Remember that in a binary heap, half of the nodes are leafs--they have no children. So if you're inserting items in random order, half the time the item you're inserting will belong on the lowest level and there is no "bubble up" to do. So half the time your insert operation is O(1). Of the other half, half of those will belong on the second level up. And so on. The only time you actually do log(n) operations on insert is when the item you're inserting is smaller than the existing root item. It's quite possible, then, that the observed runtime behavior is that insertion is O(1). In fact that will be the behavior if you insert a sorted array into a min-heap. That is, if you were to insert the values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 in that order.

从给分堆最小的项目时，你从堆取最后一个项目，并从顶部筛下来。而一半的时间的规则发挥作用了，但这次是对你的工作。从堆了这最后一个项目可能属于那里的最低水平。所以，你必须筛选便一路回落，这需要的log（n）操作。 有一半的时间的你必须做的所有的log（n）操作。剩下的你需要做的一切，但他们等了一个，其实你要筛选下来，将取决于树的深度级别的最小数目的一半。例如，如果你的堆有三个以上的项目，那么你的知道的，取消最小的项目将需要至少一个筛下操作，因为下一个最低的产品总是在树的第二级

When removing the smallest item from a min-heap, you take the last item from the heap and sift it down from the top. The "half the time" rule comes into play again, but this time it's working against you. That last item you took from the heap probably belongs down there on the lowest level. So you have to sift it all the way back down, which takes log(n) operations. Half the time you'll have do to all log(n) operations. Half of the remaining you'll need to do all but one of them, etc. And in fact the minimum number of levels you have to sift down will depend on the depth of the tree. For example, if your heap has more than three items then you know that removing the smallest item will require at least one sift-down operation because the next-lowest item is always on the second level of the tree.

事实证明，那么，在一般情况下，插入到二叉堆需要为O少得多（log n）的时间。很可能接近O（1）。而去除二元堆是非常接近的O（log n）的。

It turns out, then, that in the average case insertion into a binary heap takes much less than O(log n) time. It's likely closer to O(1). And removal from a binary heap is much closer to the worst case of O(log n).

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