基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

admin2019-05-20 64

问题基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

选项 A、O(nlog₂n)
B、O(log₂n)
C、O(n)
D、O(n²)

答案A

解析此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log₂(n!)次比较。
由Stirling公式可知，log₂(n!)≈nlog₂n一1．44n+O(log₂n)。所以基于关键字比较的分类时间的下界是O(nlog₂n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

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

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

“二战”期间，美国研制了原子弹并用于实践；1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的；德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
宋代至清代我国书籍印刷的主要方式是()
“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()
“二战期间，美国研制了原子弹并用于实践；1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道；德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
赋税是我国古代国家宏观管理经济的重要手段。　　据此回答问题：明朝推行一条鞭法中“一”的内容是()
下列关于基督教的思想来源的叙述，不正确的是()。
下面对官渡之战的表述正确的是()。
1946年3月5日，英国前首相丘吉尔在富尔敦发表了()，发出第一个明白无误的“冷战”信号。
在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。
在单CPU和两台输入／输出设备(11，12)的多道程序设计环境下，同时投入3个作业J1、J2和J3运行。这3个作业对CPU和输入／输出设备的使用顺序和时间如下所示。J1：12(30ms)；CPU(10ms)；11(30ms)；CPU(10ms)；

随机试题

Word软件处理的主要对象是
一名12岁儿童于口腔科就诊，家长要求行龋病的预防临床操作中保证封闭成功的因素是
南方某放牧牛群部分牛食欲减退，精神不振，腹泻，血便，严重贫血，衰竭死亡。剖检见肝脏肿大，有多量虫卵结节。确诊该病常用的粪检方法是
某大型水闸施工过程中厂施工单位经监理单位批准后对闸底板基础进行了混凝土覆盖．在下一仓浇筑准备时，监理单位对已覆盖的基础质量有疑问，指示施工单位剥离已浇混凝土并重新检验，检测结果表明，基础质量不合格，则该返工处理的施工费用应由()承担，检测费用应由(
《中华人民共和国民法通则》第三十七条规定，法人应当具备的条件包括()。
X企业与其他单位签订完购货意向书之后，将此笔业务需要支付的款项确定为—项负债。()
1949年，胡风诗意地写道：时间开始了。这一表述的意思是，一个真正有意义的、_____的、进步的时代到来了，与这个新时代相对应的，是此前的没有意义、黑暗和_____。填入画横线部分最恰当的一项是：
课堂教学的一般过程包括()。
在关系模式R(u)中，如果X-＞Y，并且对于X的任何一个真子集X’，都有X’-＞Y，则称
Tenyearsago,JoeAllenbeganstudyingadiversegroupofseventhgradersneartheUniversityofVirginia,wherehe’saprofess

最新回复(0)

基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

计算机408

学硕统考专业

“二战”期间，美国研制了原子弹并用于实践；1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的；德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。

宋代至清代我国书籍印刷的主要方式是()

“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()

“二战期间，美国研制了原子弹并用于实践；1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道；德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。

赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题：明朝推行一条鞭法中“一”的内容是()

下列关于基督教的思想来源的叙述，不正确的是()。

下面对官渡之战的表述正确的是()。

1946年3月5日，英国前首相丘吉尔在富尔敦发表了()，发出第一个明白无误的“冷战”信号。

在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。

在单CPU和两台输入／输出设备(11，12)的多道程序设计环境下，同时投入3个作业J1、J2和J3运行。这3个作业对CPU和输入／输出设备的使用顺序和时间如下所示。J1：12(30ms)；CPU(10ms)；11(30ms)；CPU(10ms)；

Word软件处理的主要对象是

一名12岁儿童于口腔科就诊，家长要求行龋病的预防临床操作中保证封闭成功的因素是

南方某放牧牛群部分牛食欲减退，精神不振，腹泻，血便，严重贫血，衰竭死亡。剖检见肝脏肿大，有多量虫卵结节。确诊该病常用的粪检方法是

《中华人民共和国民法通则》第三十七条规定，法人应当具备的条件包括()。

X企业与其他单位签订完购货意向书之后，将此笔业务需要支付的款项确定为—项负债。()

1949年，胡风诗意地写道：时间开始了。这一表述的意思是，一个真正有意义的、_____的、进步的时代到来了，与这个新时代相对应的，是此前的没有意义、黑暗和_____。填入画横线部分最恰当的一项是：

课堂教学的一般过程包括()。

在关系模式R(u)中，如果X-＞Y，并且对于X的任何一个真子集X’，都有X’-＞Y，则称

Tenyearsago,JoeAllenbeganstudyingadiversegroupofseventhgradersneartheUniversityofVirginia,wherehe’saprofess

赋税是我国古代国家宏观管理经济的重要手段。　　据此回答问题：明朝推行一条鞭法中“一”的内容是()

1949年，胡风诗意地写道：时间开始了。这一表述的意思是，一个真正有意义的、_的、进步的时代到来了，与这个新时代相对应的，是此前的没有意义、黑暗和_。填入画横线部分最恰当的一项是：