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

Question

背景

维基百科和其他我找到的来源都表明，通过从空的二叉堆开始并将n个元素插入其中来构建二叉堆的时间复杂度为O(nlogn)，因为二叉堆插入是O(logn)，而您要进行n次操作。让我们称之为“插入”算法。

它还提出了一种替代方法，即沉降/向下渗漏/向下过滤/向下堆化/向下冒泡前半部分元素，从中间元素开始，以第一个元素结束，这是O(n)的复杂度，比较好。这种复杂性的证明在于沉降每个元素的复杂性取决于其在二叉堆中的高度：如果它靠近底部，则很小，可能为零； 如果它靠近顶部，则可以很大，可能为logn。关键在于此过程中每个元素的复杂度不是logn，因此总体复杂度远小于O(nlogn)，实际上是O(n)。让我们称之为“沉降”算法。

问题

为什么插入算法的复杂度不是出于同样的原因与沉降算法相同？

考虑插入算法中前几个元素实际执行的工作。第一个插入的成本不是logn，而是零，因为二叉堆是空的！第二次插入的成本最多为一次交换，第四次插入的成本最多为两次交换，等等。插入元素的实际复杂度取决于二叉堆的当前深度，因此大多数插入的复杂度都小于O(logn)。甚至在所有n个元素都被插入之后，插入成本也没有达到O(logn) [对于最后一个元素，它是O(log(n-1))]！

这些节省听起来就像沉降算法所得到的节省，那么为什么不对两种算法都计算相同的节省呢？

- sleepytea

---

你的逻辑听起来很合理。 - Jerry Coffin

@indil，由于大O符号用于描述最坏情况下的渐近时间复杂度，您需要考虑插入操作最昂贵的场景，即从升序列表中构建最大堆。将有O(n/2)个元素添加到"叶子"位置，每个元素都会在堆的整个高度上进行"上浮"，即O(log n)。因此，在最坏情况下，这将导致O(n*log(n))的时间复杂度。 - 808sound

正如@808sound所写，维基百科页面隐含地假设了最坏情况的考虑。 - Michael Foukarakis

我不遵循维基百科文章中的复杂数学计算。我自己想到了一个公式：对于深度为d（从0开始计数）的完美二叉树，最坏情况下交换次数为2^d * (floor(log2 n) - d)，其中n为节点数量，d取值范围是0到floor(log2 n)。我不知道如何将其简化为O(n)。但我并不擅长这种数学计算。如果我能理解它，就能够在纸上得出O(n)了。但是，我也编写了上述求和公式的代码，观察到其中的复杂度确实是O(n)。 - sleepytea

感谢大家的评论和回答！ - sleepytea

类似：build-heap-complexity - nawfal

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次交换，以此类推。维基百科展示了一个证明，表明这会导致一个收敛于常数而非对数的级数。

- Maciej Stachowski

Answer 2

虽然log(n-1)比log(n)小，但差距不足以产生影响。

数学上：插入第i个元素的最坏情况成本是ceil(log i)。因此，插入元素1到n的最坏情况成本是sum(i = 1..n, ceil(log i)) > sum(i = 1..n, log i) = log 1 + log 1 + ... + log n = log(1 × 2 × ... × n) = log n! = O(n log n)。

- Raymond Chen

Answer 3

直觉是，下沉算法只移动了一些东西（那些在堆/树顶部的小层中的东西）距离log(n)，而插入算法移动了许多东西（那些在堆底部的大层中的东西）距离log(n)。

为什么下沉算法可以这样做的直觉是，插入算法也满足一个额外的（好的）要求：如果我们在任何时候停止插入，部分形成的堆必须是（并且是）有效的堆。对于下沉算法，我们得到的是一个奇怪的畸形堆的底部部分。有点像被砍掉了顶部的松树。

此外，还有一些总结和啥啥啥的。最好从渐近的角度来考虑，比如说，在任意大的大小为n的集合中插入最后一半元素时会发生什么。

- Andrew W.

Answer 4

昨天遇到了同样的问题。我试图想出一些证明来满足自己。这有任何意义吗？

如果你从底部开始插入，叶子节点将具有恒定的插入时间-只需将其复制到数组中。

上面一层的最坏情况运行时间为：

k*(ⁿ/_2^h)*h

其中h是高度（叶子为0，顶部为log（n）），k是常数（仅供参考）。因此，(ⁿ/_2^h)是每个级别的节点数，h是每次插入的最大“下沉”操作次数

有log（n）个级别，因此总运行时间为

从1到log（n）的h求和：n*k*(^h/_2^h)

这是k*n * SUM h=[1,log(n)]: (^h/_2^h)

这个总和是一个简单的算术几何级数，结果为2。因此，您将获得k*n*2的运行时间，即O(n)。

每个级别的运行时间并不严格符合我所说的，但它严格小于那个值。有什么需要注意的吗？

- 2bigpigs