堆排序的时间复杂度是(),堆排序中建堆过程的时间复杂度是()。
A. O(n^2),O(n*log(n))
B. O(n),O(n*log(n))
C. O(n*log(n)),O(n)
D. O(n*log(n)),O(n*log(n))
C
堆排序的时间,主要由建立...
用户登录可进行刷题及查看答案
堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。时间复杂度O(n*logn)
如果从底部最后的父节点开始建堆,那么我们可以大概算一下: 假如有N个节点,那么高度为H=logN,最后一层每个父节点最多只需要下调1次,倒数第二层最多只需要下调2次,顶点最多需要下调H次,而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个,所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N),近似的时间复杂度就是O(N)。
登录后提交答案
暂无评论,来抢沙发