假设我们有一个包含n个元素的二叉堆，并希望插入另外n个元素(不一定是连续的)。这将需要多少总时间？
我认为时间复杂度为theta(n logn)，因为每次插入需要logn时间。
我认为时间复杂度为theta(n logn)，因为每次插入需要logn时间。
向二叉堆中插入n个元素的渐进时间复杂度（已包含n个元素）
8
- user966892
1
我认为现有堆的大小应该以某种方式输入结果。 - Kerrek SB
3个回答
6
给定：n个元素的堆和另外n个要插入的元素。最终将有2*n个元素。由于堆可以通过两种方式创建，即连续插入和构建堆方法。在这些方法中，构建堆方法需要O(n)时间来构建堆，这在如何使构建堆具有O(n)时间复杂度？中有所解释。因此，所需的总时间为O(2*n)，与O(n)相同。
- Hegde
4
假设我们有以下内容：
最佳情况是，对于最小堆（顶部为最小值的堆），我们插入BIG（更新分支中最大的值）（因此向上堆立即停止）。
您询问了包含n个元素的堆上一系列n个操作，其大小将增长
简化我们的方程。 (我们不必担心n的增长，因为它的增长是通过常数因子实现的)。
因此，我们有“对于n次插入”的操作：
- Xi(n) = 对于n次插入的X - Wi(n) = Θ(n lg n) - Ai(n) = Θ(n lg n) - Bi(n) = Θ(n)
这意味着，在“所有情况”下：
- Ti(n) = Ω(n)且Ti(n) = O(n lg n)
附注：为了显示Theta Θ，Omega Ω符号，您需要安装/兼容UTF-8。
- 由标准二叉堆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) = 对于n次插入的X - Wi(n) = Θ(n lg n) - Ai(n) = Θ(n lg n) - Bi(n) = Θ(n)
这意味着，在“所有情况”下：
- Ti(n) = Ω(n)且Ti(n) = O(n lg n)
附注：为了显示Theta Θ，Omega Ω符号，您需要安装/兼容UTF-8。
- Grzegorz Wierzowiecki
1
这不是 Θ(nlogn)… 它是 O(nlogn)，因为有些插入可能需要少于精确的 logn 时间… 因此对于 n 个插入，它将花费时间 <=nlogn
=> 时间复杂度=O(nlogn)
- shahbaz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接