在最坏情况下，堆排序的时间复杂度是( )。

admin2016-04-07 64

问题在最坏情况下，堆排序的时间复杂度是( )。

选项 A、O(lgo₂n)
B、O(nlog₂n)
C、O(n²)
D、O(n^1.5)

答案B

解析若有n个元素的序列，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆，大根堆是指所有节点的值大于或等于左右子节点的值；小根堆是指所有节点的值小于或等于左右子节点的值。在调整建堆的过程中，总是将根节点值与左、右子树的根节点进行比较，若不满足堆的条件，则将左、右子树根节点值中的大者与根节点值进行交换。堆排序最坏情况下需要O(nlog₂n)次比较，所以时间复杂度是O(nlog₂n)，B选项正确。

转载请注明原文地址:https://kaotiyun.com/show/VkDp777K

本试题收录于：二级C语言题库NCRE全国计算机二级分类

二级C语言

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

在最坏情况下，堆排序的时间复杂度是( )。

二级C语言

NCRE全国计算机二级

下列程序的运行结果是______。#include＜stdio.h＞main(){intfun();fun();}fun()

以下说明语句中，【】是结构体类型名。typedefstruct{intn；charch[8]；}PER；

下列程序的运行结果是()。#include＜stdio.h＞#include＜string.h＞main(){char*s1="abDuj";char

数据库设计包括两个方面的设计内容，它们是______。

算法的时间复杂度是指______。

设有定义“struct{inta；floatb；charc；}abc，*p_abc=&abc；”，则对结构体成员a的引用方法可以是abc.a和p_abc【】a。

mystrlen函数的功能是计算str所指字符串的长度，并作为函数值返回。请填空。intmystrlen(char*str){inti；for(i=0；【】!＝’\0’；i++)；return(i)；}

对于长度为n的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是______。

用筛选法可得到2～n(n

用筛选法可得到2～n(n

遗嘱继承人可以是法定继承人范围以内的人，也可以是法定继承人范围以外的人。()

急性腹痛放射至肩部是因为

在收益率计算中,可预测物业预期可获得的收益,尤其包括物业的租金和额外利润,这是与投资回报率之间的最大区别。()

单位工程概算是编制()的依据。

银行公司治理的主体包括股东大会、董事会、监事会和高级管理层，其中股东履行自己责任的机构与场所是()。

在企业面临的所有风险类型中，最便于管理的是()。

计算机系统软件中，最基本、最核心的软件是________。

WhodoesNOTbelongtotheundisputedmastersofmodernAmericanpoetry?

Withtheadvancementofmedicaltechnologyandsocialwelfare,oldageis,tomanypeople,nolongeraproblem.However,therei