为什么堆排序的时间复杂度是O(nlogn)？

2024-07-12 17:56| 来源: 网络整理| 查看: 265

看起来你对堆排序的时间复杂性感到困惑。从一个未排序的数组构建一个maxheap确实需要O(n)时间，而弹出一个元素需要O(1)时间。但是，在从堆中弹出顶部元素后，您需要将堆中的最后一个元素(A)移动到顶部，并将heapy移到顶部以保持堆的属性。对于元素A，它最多向下弹出log(n)次，这是堆的高度。因此，在弹出最大值之后，您最多需要log(n)时间来获得下一个最大值。下面是堆排序过程的一个示例。

代码语言：javascript复制 18 15 8 7 11 1 2 3 6 4 9

在你弹出数字18之后，你需要把数字9放在最上面，然后堆9。

代码语言：javascript复制 9 15 8 7 11 1 2 3 6 4

我们需要弹出9，因为9< 15

代码语言：javascript复制 15 9 8 7 11 1 2 3 6 4

我们需要弹出9因为9< 11

代码语言：javascript复制 15 11 8 7 9 1 2 3 6 4

9>4，这意味着heapify过程已经完成。现在，您可以安全地获得下一个最大值15，而无需破坏堆属性。

对于需要执行heapify过程的每个数字，您都有n个数字。因此，堆排序的时间复杂度为O(nlogn)

【本文地址】

公司简介

联系我们