4

的背景

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

它还提供了一种替代方法，您可以在其中下沉/涓涓细流/向下渗透/向下层叠/向下堆积/向下冒泡元素的前半部分/上半部分，从中间元素开始，到第一个元素结束，这是O( n )，一个更好的复杂度。这种复杂性的证明取决于每个元素的接收器复杂性取决于它在二进制堆中的高度：如果它靠近底部，它会很小，可能为零；如果它靠近顶部，它可能很大，可能是 log n。关键是这个过程中下沉的每个元素的复杂度不是log n，所以整体复杂度远小于O( n log n )，实际上是O( n）。我们称其为接收器算法。

问题

为什么插入算法的复杂度与接收器算法的复杂度不同，原因相同？

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

这些节省听起来就像接收器算法获得的节省，那么为什么两种算法的计算不一样呢？

4

4 回答 4

5

实际上，当 n=2^x - 1（最低级别已满）时，n/2 个元素可能需要在插入算法中进行 log(n) 交换（成为叶节点）。所以你只需要 (n/2)(log(n)) 交换叶子，这已经使它成为 O(nlogn)。

在另一种算法中，只有一个元素需要 log(n) 交换，2 个需要 log(n)-1 交换，4 个需要 log(n)-2 交换，等等。维基百科证明它会导致一系列收敛到常数代替对数。

于 2013-01-20T06:24:40.323 回答
1

虽然 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)。

于 2013-01-21T04:42:32.547 回答
1

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

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

此外，总结和等等。最好渐近地考虑在插入任意大的 n 集合的后半部分元素时会发生什么。

于 2013-01-22T07:07:01.413 回答
0

昨天遇到了同样的问题。我试着想出某种形式的证据来满足自己。这有道理吗？

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

叶子之上的一个级别的最坏情况运行时间是：

k*( n / 2 h )*h

其中 h 是高度（叶子为 0，顶部为 log(n) ）k 是一个常数（仅用于良好的测量）。所以 ( n / 2 h ) 是每个级别的节点数， h 是每个插入的“下沉”操作的最大数量

有 log(n) 个级别，因此，总运行时间将是

h 从 1 到 log(n) 的总和：n* k* ( h / 2 h )

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

总和是一个简单的算术几何级数，结果为 2。所以你得到 k*n*2 的运行时间，即 O(n)

每个级别的运行时间严格来说并不是我所说的那样，但严格来说比这要少。有什么陷阱吗？

于 2014-07-24T08:04:31.783 回答