本文介绍了插入n个元素为二进制堆已含有n个元素的渐近时间复杂度的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

假设我们有n个元素的二进制堆和希望插入n多元素(不一定是另外一个后)。什么是为此所需的总时间?

Suppose we have a binary heap of n elements and wish to insert n more elements(not necessarily one after other). What would be the total time required for this?

我觉得这是THETA(N LOGN)作为一个插入需要LOGN。

I think it's theta (n logn) as one insertion takes logn.

推荐答案

假设我们给出:

    通过标准的二叉堆实施
  • 在优先级队列中的 ^ h 在数组实现
  • N 堆当前大小
  • priority queue implemented by standard binary heap H (implemented on array)
  • n current size of heap

我们有如下的插入属性:

  • 在W(N)=最坏情况(N)=Θ(LG N)(西塔)。 - > W(N)=Ω(LG n)和W(N)= O(LG N)
  • A(N)= AverageCase(N)=Θ(LG N)(西塔)。 - > W(N)=Ω(LG n)和W(N)= O(LG N)
  • B(N)= BestCase(N)=Θ(1)(西塔)。 - > W(N)=Ω(1)和W(N)= O(1)

因此​​,对于的任何情况下的,我们有

So for every case, we have

  • T(N)=Ω(1)和T(N)= O(LG N)

最坏情况是,当我们插入新的最小值,因此向上堆有出行整个分支。

WorstCase is when, we insert new minimal value, so up-heap has to travel whole branch.

BestCase是时,对于最小堆(堆以最小的顶部),我们插入大(最大的更新分支)值(所以向上堆立即停止)。

BestCase is when, for minimal-heap (heap with minimal on top) we insert BIG (biggest on updated branch) value (so up-heap stops immediately).

您已经询问了N系列的操作上已经包含n个元素的堆,它的大小将增长

You've asked about series of n operations on heap containing already n elements,it's size will grow

from n to 2*n

什么渐近就是...

what asymptotically is ...

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

什么简化了我们的方程式。 (我们不担心增长的 N 的,因为它的增长是恒定的因素)。

What simplifies our equations. (We don't have to worry about growth of n , as it's growth is by constant factor).

所以,我们有n个插入操作:

So, we have "for n insertions" of operation:

  • 在熙(N)= X_for_n_insertions(N)
    • 在无线网络(N)=Θ(N LG N)
    • 在艾(N)=Θ(N LG N)
    • 双(N)=Θ(N)
    • Xi(n) = X_for_n_insertions(n)
      • Wi(n) = Θ(n lg n)
      • Ai(n) = Θ(n lg n)
      • Bi(n) = Θ(n)
      • 钛(N)=Ω(n)和钛(N)=为O(n LG N)

      P.S。为了显示西塔Θ,欧米茄Ω符号,你需要有UTF-8安装/兼容。

      P.S. For displaying Theta Θ , Omega Ω symbols, you need to have UTF-8 installed/be compatible.

      这篇关于插入n个元素为二进制堆已含有n个元素的渐近时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-28 18:33