O（1）平均情况下堆插入的复杂度的参数 [英] Argument for O(1) average-case complexity of heap insertion

问题描述

在二进制堆的维基百科页面上的声明是插入是O（log n ），但平均水平为O（1）：

The claim on the Wikipedia page for binary heaps is that insertion is O(log n) in the worst case, but O(1) on average:

所需的操作次数取决于仅在级别数上，新元素必须上升以满足堆栈属性，因此插入操作的最坏情况时间复杂度为O（log n ），但平均情况下复杂度为O（log 1）。

The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a worst-case time complexity of O(log n) but an average-case complexity of O(1).

链接的页面试图证明这一点，如下所示：

The linked page attempts to justify this as follows:

但是，平均而言，新插入的元素不会移动得很远在树上。尤其是，假设密钥分布均匀，则它有比父密钥大一半的机会。考虑到它比其祖父母更大，它有比其祖父母更大的一半的机会；考虑到它比其祖父母更大，它有一半的机会比其曾祖父母更大，依此类推，因此在平均情况下，插入需要花费恒定的时间

However, on average, the newly inserted element does not travel very far up the tree. In particular, assuming a uniform distribution of keys, it has a one-half chance of being greater than its parent; it has a one-half chance of being greater than its grandparent given that it is greater than its parent; it has a one-half chance of being greater than its great-grandparent given that it is greater than its parent, and so on [...] so that in the average case insertion takes constant time

这当然是胡说吗？在我看来，如果树是随机排序的，那么新元素比其父元素大的可能性就为50/50。但这是因为，从粗略讲，大元素下降到了底部，所以随着堆的增长，机会大大少于50/50。

This is surely nonsense, though? It seems to me that if the tree were randomly ordered then there would be a 50/50 chance that a new element was greater than its parent; but that since, roughly speaking, the large elements sink to the bottom, the chances are much less than 50/50 as the heap grows.

是吗？

类似于Wikipedia上的几个月……

It's been like that on Wikipedia for several months...

推荐答案

关于平均时间堆插入为O（1）的说法有更好的参考：1991年的论文 通过重复插入进行堆建的平均案例分析，作者：Hayward& McDiarmid。 （本文链接在Wikipedia文章的当前参考文献4中。）该论文又引用了Porter& 1975年的论文。 Simon， 在优先级队列结构中随机插入，它涉及到在堆，并证明平均情况为O（1）。

There is a much better reference for the claim that average time heap insertion is O(1): the 1991 paper "Average Case Analysis of Heap Building by Repeated Insertion" by Hayward & McDiarmid. (This paper is linked in what is currently reference 4 of the Wikipedia article.) That paper in turn references a 1975 paper by Porter & Simon, "Random insertion into a priority queue structure" which deals with a single insertion into a heap, and demonstrates that the average case is O(1).

直觉上，该参数很简单。堆的一半是叶子，叶子往往更大。如果我们暂时假设叶子是堆中最大的元素（而不是趋于更大），那么我们可以说一个新元素将是叶子的概率-即，它在上半部分值范围内的-恰好是0.5。如果新元素不是堆的叶子（概率也为0.5），我们可以使用仅由原始堆中的非叶子节点组成的截短的堆重复该过程，因此新元素位于第二个元素的概率为-最低水平将是剩余水平的一半：0.25。因此，它处于第三级的可能性为0.125，依此类推。那么我们必须搜索的期望级别数将是1 * 0.5 + 2 * 0.25 + 3 * 0.125 ...，即2。

Intuitively, the argument is simple. Half of the heap is a leaf, and the leaves tend to be larger. If we assume for a moment that leaves are the largest elements in the heap (rather than tending to be larger), then we could say that the probability that a new element will be a leaf -- i.e., that it is in the upper half of the range of values -- would be exactly 0.5. If the new element is not a leaf of the heap (also probability 0.5), we can repeat the process with the truncated heap consisting only of non-leaf nodes in the original heap, so the probability that the new element is at the second-lowest level will be half of what remains: 0.25. And thus the probability that it is at the third level would be 0.125, and so on. Then the expected number of levels we would have to search through would be 1*0.5 + 2*0.25 + 3*0.125..., which is 2.

，则随机新元素大于随机第二级父元素的概率实际上不是0.5；实际上少了一点。但是，只要它以常数为界，计算期望比较次数的幂级数之和仍将以常数为界。事实证明，常数约为2.6。

Of course, the probability that the random new element is greater than a random second-level parent is not really 0.5; it's actually a little less. But, as long as it is bounded by a constant, the sum of the power series which computes the expected number of comparisons will still also be bounded by a constant. And it turns out that the constant is around 2.6.

另请参见此有用答案，在讨论堆的复杂性并将其与BST进行对比时，给出了对堆中恒定平均插入时间的详细图形分析。

Also see this useful answer that, while discussing complexities of heaps, and contrasting them with those of BST, gives a detailed graphical analysis of the constant average insertion time in heaps.

这篇关于O（1）平均情况下堆插入的复杂度的参数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！