向已包含 n 个元素的二叉堆插入 n 个元素的渐近时间复杂度

Question

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

我认为它是 theta (n logn)，因为一次插入需要 logn。

Answer 1

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

Answer 2

假设我们给出：

• 由标准二叉堆实现的优先级队列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 的增长，因为它的增长是按常数因子计算的）。

因此，我们有“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/兼容。

Answer 3

它不是 theeta(nlogn)...它的 order(nlogn) 因为某些插入可能需要比精确的 logn 时间更短的时间...因此对于 n 次插入，它将花费时间 <=nlogn

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