如何建立一个堆为O（n）的时间复杂度？ [英] How can building a heap be O(n) time complexity?

问题描述

有人可以帮忙解释一下如何构建一个堆为O（n）的复杂性？

Can someone help explain how can building a heap be O(n) complexity?

将项目放入堆是 O（log n）的，插入重复n / 2次（其余的是叶，不能违反堆属性）。因此，这意味着复杂性应该是为O（n log n）的，我想。

Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the heap property). So, this means the complexity should be O(n log n), I would think.

换句话说，对于每个项目，我们heapify，它有可能使有一次为每个级别为堆迄今（这是日志n级）过滤下来。

Put another way, for each item we "heapify", it has the potential to have to filter down once for each level for the heap so far (which is log n levels).

我在想什么？

推荐答案

您的分析是正确的。然而，这是不紧。

Your analysis is correct. However, it is not tight.

这不是很容易解释为什么建立一个堆是一个线性操作，你应该更好地阅读它。

It is not really easy to explain why building a heap is a linear operation, you should better read it.

算法的大分析可以看出<一href="http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf">here.

其主要思想是， build_heap 算法在实际 heapify 成本并不 O（log n）的的所有元素。

The main idea is that in the build_heap algorithm the actual heapify cost is not O(log n)for all elements.

在 heapify 被调用，运行时间取决于多远的元素可能倒在树中的进程终止之前移动。换句话说，这取决于在堆中的元件的高度。在最坏的情况下，元素可能会往下走一路叶级。

When heapify is called, the running time depends on how far an element might move down in tree before the process terminates. In other words, it depends on the height of the element in the heap. In the worst case, the element might go down all the way to the leaf level.

让我们来细数逐级完成的工作水平。

Let us count the work done level by level.

在最底层，有 2 ^（H）节点，但我们不叫 heapify 上所有这些，所以工作是0。在地级有 2 ^（H - 1）在未来节点，每个可能下降1级移动。在从底部3级，有 2 ^（H - 2）节点，每一个可能降低2级移动

At the bottommost level, there are 2^(h)nodes, but we do not call heapify on any of these, so the work is 0. At the next to level there are 2^(h − 1) nodes, and each might move down by 1 level. At the 3rd level from the bottom, there are 2^(h − 2) nodes, and each might move down by 2 levels.

正如你所看到的不是所有的heapify操作 O（log n）的，这就是为什么你得到 O（N）。

As you can see not all heapify operations are O(log n), this is why you are getting O(n).

这篇关于如何建立一个堆为O（n）的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！