为什么不通过插入O(n)来构建二进制堆的时间复杂度？

Question

的背景

根据维基百科和我发现的其他来源,通过从空的二进制堆开始并将n个元素插入其中来构建n个元素的二进制堆是O(n log n),因为二进制堆插入是O(log n)你做了n次.我们称之为插入算法.

它还提供了一种替代方法,您可以向下/向下/向下/向下堆积/向下堆积/向下压缩元素的第一个/上半部分,从中间元素开始并以第一个元素结束,这是O(n),复杂度要高得多.这种复杂性的证明取决于每个元素的接收器复杂性取决于它在二进制堆中的高度的洞察力:如果它接近底部,它将很小,可能为零; 如果它靠近顶部,它可能很大,也许是log n.关键是在这个过程中沉没的每个元素的复杂性不是log n,因此整体复杂度远小于O(n log n),实际上是O(n).我们称之为接收器算法.

这个问题

出于同样的原因,为什么插入算法的复杂性与sink算法的复杂度不同？

考虑插入算法中前几个元素的实际工作.第一次插入的成本不是log n,它是零,因为二进制堆是空的!第二次插入的成本最差的是一次交换,第四次的成本最差是两次交换,依此类推.插入元素的实际复杂性取决于二进制堆的当前深度,因此大多数插入的复杂性小于O(log n).在插入所有n个元素之后,插入成本甚至在技术上都达不到O(log n)[它是最后一个元素的O(log(n - 1)]]!

这些节省听起来就像接收器算法所节省的成本一样,那么为什么它们对两种算法都没有统计？

Answer 1

实际上,当n = 2 ^ x - 1(最低级别已满)时,n/2个元素可能需要插入算法中的log(n)交换(成为叶子节点).因此,您只需要(n/2)(log(n))交换叶子,这已经使它成为O(nlogn).

在另一个算法中,只有一个元素需要log(n)交换,2个需要log(n)-1个交换,4个需要log(n)-2交换等.维基百科显示了一个证据,它导致一个系列收敛到一个常数代替对数.