从未排序数组生成二进制堆的时间复杂度

Question

任何人都可以解释为什么使用自下而上堆构造从未排序数组生成二进制堆的时间复杂度为O(n)？

(到目前为止找到的解决方案:我在Thomas和Goodrich的书中发现,构建堆时内部节点的路径大小总和是2n-1,但仍然不理解他们的解释)

谢谢.

Answer 1

正常的BUILD-HEAP从未排序的数组生成二进制堆的过程实现如下:

BUILD-HEAP(A)
 heap-size[A] ? length[A]
  for i ? length[A]/2 downto 1
   do HEAPIFY(A, i)

这里HEAPIFY过程需要O(h)时间,其中h是树的高度,并且有O(n)这样的调用使得运行时间为O(nh).考虑到h = lg n,我们可以说 BUILD-HEAP过程需要O(n lg n)时间.

为了进行更严格的分析,我们可以观察到大多数节点的高度很小.实际上,在任何高度h,最多可以有CEIL(n /(2 ^ h +1))节点,我们可以通过归纳轻松证明这些节点.因此,BUILD-HEAP的运行时间可写为,

lg n                     lg n
? n/(2^h+1)*O(h)  = O(n* ? O(h/2^h)) 
h=0                      h=0  

现在,

?   
? k*x^k = X/(1-x)^2
k=0              
               ? 
Putting x=1/2, ?h/2^h = (1/2) / (1-1/2)^2 = 2
               h=0     

因此,运行时间变成,

lg n                     ?   
O(n* ? O(h/2^h))  = O(n* ? O(h/2^h))  = O(n)
h=0                      h=0  

因此,这给出了O(n)的运行时间.

NB分析来自于此.