首页 > 试题广场 >

在堆排序的过程中,建立一个堆的时间复杂度是()

[单选题]
在堆排序的过程中,建立一个堆的时间复杂度是()
  • O(n)
  • O(logn)
  • O(nlogn)
  • O(n2)
22王道数据结构8.4.2 p315:建含n个元素的堆时,关键字的比较次数不超过4n,即可以在线性时间内建堆 搬运思路: https://blog.csdn.net/qq_41647726/article/details/113278623
发表于 2021-04-24 12:40:00 回复(0)
建堆时间复杂度:O(n)
调整堆、插入、删除:O(log2n)
堆排序平均时间复杂度:O(nlog2n)
空间复杂度:O(1)

记住!
发表于 2021-12-13 17:13:58 回复(1)
建堆时间复杂度:O(n)
调整堆、插入、删除:O(log2n)
堆排序平均时间复杂度:O(nlog2n)
空间复杂度:O(1)
发表于 2021-11-15 14:27:43 回复(0)
初始建堆时间复杂度O(n),

一次重建堆时间复杂度O(logn)

堆排序时间复杂度为O(nlogn),
发表于 2021-08-30 16:59:27 回复(0)

构建堆的过程中,从完全完全二叉树最下层最右边的非终端结点开始构建,将它与其孩子进行比较和若有必要的互换,对于每个非终端结点来说,其实最多进行两次比较和互换操作,因此整个构建堆的时间复杂度为O(n);
在正式排序时,第i次取堆顶需要用O(log i)的时间,需要取(n-1)次堆顶记录,因此重建堆的时间复杂度为O(nlogn),即堆排序的时间复杂度为O(nlogn)。

发表于 2021-05-11 11:27:49 回复(0)
???不是nlog2n吗?
发表于 2021-04-30 16:50:55 回复(1)