堆排序时间复杂度深入理解

Question

堆排序时间复杂度深入理解

sortingheaptime-complexityheapsortamortized-analysis

3

当我在大学学习数据结构课程时，我学到了以下公理：

1. 在堆中插入一个新数字的最坏情况下需要O(logn)时间（取决于将其作为叶子节点插入时它到达树的高度）。 2. 从空堆开始使用n个插入创建具有n个节点的堆，使用摊销分析总和为O(n)时间。 3. 最小值的删除在最坏情况下需要O(logn)时间（取决于新顶部节点与最后一个叶子交换后它到达的位置有多低）。 4. 逐个删除所有最小值，直到堆为空，需要O(nlogn)的时间复杂度。

提醒：堆排序算法的步骤如下：

1. 将所有数组值添加到堆中：使用摊销分析技巧，总时间复杂度为O(n)。 2. 从堆中弹出最小值n次，并将第i个值放置在数组的第i个索引中：由于弹出最小值时摊销分析技巧不起作用，因此时间复杂度为O(nlogn)。

我的问题是：为什么摊销分析技巧在清空堆时不起作用，导致堆排序算法需要O(nlogn)的时间而不是O(n)的时间？

编辑/回答：

当堆存储在数组中（而不是动态树节点带有指针时），我们可以自下而上地构建堆，即从叶子开始直到根，然后使用摊销分析，我们可以得到总时间复杂度为O(n)，而我们无法自下而上地清空堆的最小值。

- SomethingSomething

1

你的问题是为什么现有算法需要O(n log n)的时间，还是为什么不能用O(n)的时间完成所有出队操作？ - templatetypedef

从我的角度来看，这实际上是同一个问题——如果我可以在O(n)中执行所有的dequeues操作，那么我就可以在O(n)中对数组进行排序——因为我可以在O(n)中创建并清空堆。 - SomethingSomething

2个回答

1

让我“数学地”展示一下我们如何计算将任意数组转换为堆（称为“堆构建”）并使用堆排序对其进行排序的复杂度。

堆构建时间分析

为了将数组转换为堆，我们必须查看每个具有子节点的节点并“堆化”（下沉）该节点。您应该问自己我们执行了多少次比较；如果您考虑一下，就会发现（h = 树高）：

- 对于第 i 级的每个节点，我们进行 h-i 次比较：＃comparesOneNode(i) = h-i - 在第 i 级，我们有 2^i 个节点：＃nodes(i) = 2^i - 因此，通常 T(n,i) = ＃nodes(i) *＃comparesOneNode(i) = 2^i *（h-i），是在级别“i”上花费的“比较”的时间

让我们举个例子。假设有一个由15个元素组成的数组，即树的高度为h = log2(15) = 3:

在i=3级别时，我们有2^3=8个节点，并且我们为每个节点进行3-3次比较：正确，因为在第3级别上，我们只有没有子节点的节点，即叶子节点。T(n, 3) = 2^3*(3-3) = 0
在i=2级别时，我们有2^2=4个节点，并且我们为每个节点进行3-2次比较：正确，因为在第2级别上，我们只有与第3级别进行比较。T(n, 2) = 2^2*(3-2) = 4 * 1
在i=1级别时，我们有2^1=2个节点，并且我们为每个节点进行3-1次比较：T(n, 1) = 2^1*(3-1) = 2 * 2
在i=0级别时，我们有2^0=1个节点，即根节点，并且我们进行3-0次比较：T(n, 0) = 2^0*(3-0) = 1 * 3

好的，一般地：

T(n) = sum(i=0 to h) 2^i * (h-i)

但是如果您记得h = log2（n），那么我们有

T（n）= sum（i = 0到log2（n））2 ^ i *（log2（n）- i）〜2n

堆排序时间分析

现在，这里的分析非常相似。每次我们“删除”最大元素（根）时，我们将最后一个叶子移动到根，对其进行堆化，并重复此过程直到结束。那么，我们在这里执行了多少比较？

在第i层，我们有2 ^ i个节点：#nodes（i）=2 ^ i
对于每个位于级别“i”的节点，堆化在最坏情况下将始终执行与级别“i”完全相同数量的比较（我们从级别i中取一个节点，将其移到根处，调用heapify，并且在最坏情况下，heapify将该节点带回到级别i，执行“i”次比较）：＃comparesOneNode（i）= i
因此，通常T（n，i）=＃nodes（i）*＃comparesOneNode（i）= 2 ^ i * i，是用于删除前2 ^ i个根并将临时根带回正确位置所花费的时间。

让我们举个例子。假设有一个由15个元素组成的数组，即树的高度为h = log2(15) = 3：

在i=3级别上，我们有2^3=8个节点，需要将它们中的每一个移动到根位置，然后对每个节点进行堆化。每次堆化最坏情况下需要“i”次比较，因为根节点可能会下沉到仍存在的i级别。T(n, 3) = 2^3 * 3 = 8*3
在i=2级别上，我们有2^2=4个节点，每个节点需要进行2次比较：T(n, 2) = 2^2*2 = 4 * 2
在i=1级别上，我们有2^1=2个节点，每个节点需要进行1次比较：T(n, 1) = 2^1*1 = 2 * 1
在i=0级别上，我们只有一个节点，即根节点，不需要进行任何比较：T(n, 0) = 0

好的，总的来说：

T(n) = sum(i=0 to h) 2^i * i

但是如果您记得h = log2(n)，那么我们有：

T(n) = sum(i=0 to log2(n)) 2^i * i =~ 2nlogn

堆的构建和堆排序的区别

直观地看，堆排序无法“摊销”其成本，因为每次增加节点数，我们就不得不进行更多的比较，而在堆的构建功能中恰恰相反！您可以在这里看到：

堆的构建：T(n, i) ~ 2^i * (h-i)，如果i增加，节点数会增加，但比较次数会减少
堆排序：T(n, i) ~ 2^i * i，如果i增加，节点数和比较次数都会增加

所以：

第3层，#节点(3)=8，堆构建不进行比较，堆排序进行了8*3=24次比较
第2层，#节点(2)=4，堆构建进行了4次比较，堆排序进行了4*2=8次比较
第1层，#节点(1)=2，堆构建进行了4次比较，堆排序进行了2*1=2次比较
第0层，#节点(0)=1，堆构建进行了3次比较，堆排序进行了1*0=1次比较

- igol

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

假设只能通过比较两个对象的相对排名来了解它们，那么无法在时间复杂度为O(n)的情况下从二叉堆中出队所有元素。如果可以这样做，那么就可以在O(n)的时间内通过在O(n)的时间内构建堆，然后在O(n)的时间内出队所有内容来对列表进行排序。然而，排序的下限表明，为了正确，比较排序的平均运行时间必须为Ω(n log n)。换句话说，不能太快地从堆中出队，否则将突破排序障碍。

还有一个问题，为什么从二叉堆中出队n个元素的时间复杂度是O(n log n)，而不是更快的时间复杂度。这有点棘手，但基本思路如下。考虑在堆上进行的第一半出队操作。看看实际出队的值，并思考它们最初在堆中的位置。除了底层行的元素外，所有被出队的元素都必须逐个交换上移到堆顶才能被删除。你可以证明堆中有足够的元素来保证仅此操作就需要Ω(n log n)的时间，因为大约一半的节点将深入树中。这就解释了为什么平摊论证不起作用——你不断地将深层节点拖到堆顶，因此节点总共需要移动的距离很大。与堆化操作相比，大多数节点的移动距离非常小。