7

假设我们有一个包含 n 个元素的二叉堆，并希望插入 n 个更多元素（不一定一个接一个）。这需要多少时间？

我认为它是θ（n logn），因为一次插入需要logn。

4

3 回答 3

6

给定：n 个元素的堆和要插入的 n 个更多元素。所以最后会有 2*n 个元素。因为堆可以通过 2 种方式创建：1. 连续插入和 2. 构建堆方法。在这些构建堆方法中，构建堆需要 O(n) 时间，这在 如何构建堆是 O(n) 时间复杂度中进行了解释？. 所以所需的总时间是 O(2*n) 与 O(n) 相同

于 2013-01-23T04:59:53.860 回答
4

假设我们得到：

  • 由标准二进制堆H实现的优先级队列（在数组上实现）
  • n当前堆大小

我们有以下插入属性：

  • W(n) = WorstCase(n) = Θ(lg n) (Theta)。-> W(n)=Ω(lg n) 和 W(n)=O(lg n)
  • A(n) = AverageCase(n) = Θ(lg n) (Theta)。-> W(n)=Ω(lg n) 和 W(n)=O(lg n)
  • B(n) = BestCase(n) = Θ(1) (Theta)。-> W(n)=Ω(1) 和 W(n)=O(1)

所以对于每种情况，我们都有

  • T(n) = Ω(1) 和 T(n) = O(lg n)

最坏的情况是，我们插入新的最小值，所以上堆必须遍历整个分支。

最佳情况是，对于最小堆（顶部最小的堆），我们插入 BIG（更新分支上最大）值（因此向上堆立即停止）。

您已经询问了关于已经包含 n 个元素的堆上的一系列 n 操作，它的大小会增长

from n to 2*n

什么是渐近...

n=Θ(n)
2*n=Θ(n)

什么简化了我们的方程式。（我们不必担心n的增长，因为它的增长是常数因子）。

所以，我们有“for n 次插入”的操作：

  • Xi(n) = X_for_n_insertions(n)
    • Wi(n) = Θ(n lg n)
    • Ai(n) = Θ(n lg n)
    • Bi(n) = Θ(n)
  • 它意味着，对于“所有情况”：
    • Ti(n) = Ω(n) 和 Ti(n) = O(n lg n)

PS 要显示 Theta Θ 、 Omega Ω 符号，您需要安装/兼容 UTF-8。

于 2012-01-09T15:06:24.423 回答
1

它不是theeta（nlogn）...它的顺序（nlogn），因为某些插入可能花费的时间少于精确的logn时间...因此对于n次插入，它将花费时间<=nlogn

=> 时间复杂度=O(nlogn)

于 2011-12-28T13:08:33.413 回答