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

文章/答案/技术大牛

发布

1回答

C++库中未使用堆排序

c++、sorting、quicksort、heapsort

由于堆排序在所有情况下，即最好情况、平均情况和最坏情况下的时间复杂度都是O(nlogn)。而快速排序在最坏情况下的时间复杂度为O(n2)。那么，尽管在最坏的情况下复杂度较低，为什么堆排序不在C++库中实现，而是在快速排序中实现。

浏览 3提问于2017-10-01得票数 0

1回答

使用链表进行堆排序和构建堆

algorithm、data-structures、heap

我知道链表不是构建堆的合适数据结构。谁能告诉我如何使用链表实现O(nlogn)复杂度(用于堆排序)？

浏览 13提问于2018-01-31得票数 0

2回答

time-complexity、pseudocode、heapsort

我试图理解不同数据结构的时间复杂性，并从堆排序开始。根据我所读到的，我想大家都同意堆排序的时间复杂度是O(nlogn)；然而，我很难理解它是如何产生的。大多数人似乎都同意heapify方法需要O(logn)，buildmaxheap方法需要O(n)，因此O(nlogn)，但是为什么heapif

浏览 160提问于2019-01-08得票数 3

回答已采纳

6回答

快速排序优于堆排序

algorithm、sorting、big-o、quicksort、heapsort

堆排序的复杂度在最坏的情况下是O(nlogn)，而快速排序的复杂度是O(n^2)。但经验证据表明，快速排序更优越。为什么会这样呢？

浏览 0提问于2009-12-06得票数 48

回答已采纳

3回答

使用链表和数组的堆排序实现

algorithm、sorting、heap

堆排序可以使用链表和数组来实现。使用数组和链表构建堆的时间复杂度是O(nlogn)吗？删除的时间复杂度是多少？

浏览 2提问于2013-01-29得票数 0

2回答

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

sorting、heap、time-complexity、heapsort、amortized-analysis

，并使用摊销分析将其求和为O(n) time 将所有数组值添加到堆中:使用摊销分析技巧将其相加为O(n

浏览 4提问于2015-08-20得票数 3

回答已采纳

1回答

用O(1)空间复杂度选择O(N^2)时间复杂度求数组中的不同值

arrays、algorithm、sorting、distinct-values

我试图了解是否有任何替代蛮力算法(或轻微的改进/最坏的性能比幼稚的蛮力算法)仍然将导致O(N^2)的时间复杂性和O(1)辅助空间。这是我的蛮力伪码： for i=0 to i < lengthend for end for

浏览 1提问于2016-03-07得票数 1

回答已采纳

2回答

从理论上如何计算某些方法的执行时间？

java、math、theory、timing、execution-time

假设我有一个“堆排序”方法，它的复杂度是O(nlogn)。当我在1000000个输入上测量这个方法的执行时间时，我得到了0.375770669秒。如何从理论上计算此方法的执行时间？

浏览 0提问于2011-05-20得票数 4

回答已采纳

5回答

为什么不总是使用堆排序？

algorithm、sorting、heapsort

堆排序排序算法的最坏情况复杂度似乎为O(nlogn)，排序操作使用O(1)空间。此外，我还看到人们将“不稳定性”这一术语与堆排序一起使用。这意味着什么？

浏览 49提问于2011-11-29得票数 71

回答已采纳

3回答

堆排序的应用

algorithms、sorting、use-case、heap

Heapsort是一种时间复杂度为O(nlogn)的排序算法，它使用O(1)空间复杂度进行排序。然而，我知道，因为它是不稳定的，它找不到多少应用程序(f.e。(与其他排序算法相比)。我知道它是用来安排时间的。编辑:正如@AProgrammer所指出的，快速排序也不稳定。

浏览 0提问于2013-04-08得票数 4

2回答

排序技术-最有效的

sorting

堆排序 我混淆了快速排序和合并排序。两者都具有nlogn的平均时间复杂度，但堆排序也具有相同的复杂性。任何投入都将不胜感激！

浏览 4提问于2020-09-17得票数 1

回答已采纳

2回答

为什么大oh (O)也用来表示算法中的平均情况和最佳情况？

algorithm、time-complexity、big-o

如果Big oh代表最坏的情况，为什么要用它来表示算法的平均和最佳情况，比如快速排序时间复杂度average is O(nlogn) best is O(nlogn)而不是Omega(nlogn) worstis O(n^2)

浏览 0提问于2017-02-10得票数 1

1回答

堆算法时间复杂度

algorithm、data-structures、time-complexity、permutation、heaps-algorithm

有人能告诉我维基百科，中这个堆算法的时间复杂度到底是多少吗？谢谢。

浏览 3提问于2017-03-18得票数 5

回答已采纳

1回答

O(nlogn) + O(n)的时间复杂度是否仅为O(nlogn)？

algorithm、time-complexity、big-o

假设我有一个长度为n的数组，我使用带有time nlogn的排序算法对它进行了排序。得到这个排序后的数组后，我遍历它以查找任何具有线性时间的重复元素。我的理解是，由于操作是分开进行的，所以应该是time O(nlogn) + O(n)而不是O(nlogn+n)。如果是这样的话，nlogn是否会

浏览 186提问于2018-09-13得票数 0

2回答

在哪些情况下我们使用堆排序？

c、sorting、heapsort

在哪种情况下可以使用堆排序？如我们所知，堆排序具有n×lg(n).的复杂性。但是它的使用要比快速合并排序少得多。那么，我们什么时候才能准确地使用这种堆类型?它的缺点是什么？

浏览 2提问于2013-08-10得票数 0

2回答

选择排序算法的标准是什么？

c++、data-structures

我正在阅读排序方法，包括冒泡排序、选择排序、合并排序、堆排序、桶排序等。它们还包含时间复杂性，帮助我们知道哪种排序是有效的。所以我有个基本问题。如果我们包含的数据比我们将如何选择排序。时间复杂度是决定排序方法的参数之一。但是，我们是否有另一个参数来选择排序方法？查询堆排序：我们在哪里使用堆排序？堆排序有什么更大的</

浏览 1提问于2012-03-21得票数 12

回答已采纳

2回答

排序一个已经被排序的数组，除了一个不正常的元素

arrays、algorithm、sorting

考虑数组中的一组'n‘元素，除了一个出现无序的元素之外，它是排序的。下面哪个排序序列需要O(n)时间？快速排序现在我已经知道最好的方法是使用插入排序，在这种情况下需要O(n)时间，但是由于它告诉了其他方面，所以我不确定使用哪一个。堆排序不会完全利用数组被排序的属性，并且将花费O(nlogn</em

浏览 2提问于2014-10-02得票数 3

回答已采纳

2回答

在“算法入门”中，“紧密代码”是什么意思？

algorithm、performance

我正在阅读“算法导论”，作者多次提到“严密的代码”。“紧”是否只意味着要编写较少的代码来实现一种算法而不是另一种算法？当然，我不认为“紧密代码”意味着没有适当的格式、额外的空格和空白行就可以编写代码。

浏览 1提问于2016-04-07得票数 3

回答已采纳

1回答

Java优先级队列在底层是如何工作的？

java、data-structures、heap、priority-queue

我似乎找不到任何信息来回答我的问题。所以Java PriorityQueue是使用堆构建的。堆的插入和删除时间为O(logn)，因此如果我要进行堆排序，则将为O(nlogn)。但是在创建堆的过程中，它只需要O(n)时间。所以假设我把这条线 PriorityQueue<Character> heap = new PriorityQueue<>(list);

浏览 15提问于2020-10-22得票数 1

回答已采纳

点击加载更多

C++库中未使用堆排序

使用链表进行堆排序和构建堆