首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-01-04
53
问题
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、D(n
2
)
答案
A
解析
此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log
2
(n!)次比较。由Stirling公式可知，log
2
(n!)=nlog
2
n一1．44n+O(log
2
n)。所以基于关键字比较的分类时间的下界是O(nlog
2
n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
转载请注明原文地址:https://kaotiyun.com/show/mQRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列改革内容不是在《天朝天亩制度》中提出的一项是()
1824～1828年分别用不同的无机物通过不同的途径合成了同一种有机物——尿素，证明了化学定律对有机物和无机物是同样适用的科学家是()。
1837年倡导用无机肥料来补充土壤中耗去的化学元素的化学家是()。
简述雅典民主政治的形成过程。
最早以立法形式巩固大化改新成果的法令是()。
十六国时期的历史，可以划分为前后两个时期，其分界线是()。
下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()
设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。
42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
随机试题
甲、乙共谋伤害丙，进而共同对丙实施伤害行为，导致丙身受一处重伤，但不能查明该重伤由谁的行为引起。对此，下列说法错误的有()。
A．糖衣片B．植入片C．薄膜衣片D．泡腾片E．口含片以碳酸氢钠和枸橼酸为崩解剂的片剂是
下列说法正确的是()。
编制人工定额时，工人工作必须消耗的时间包括()。
企业征信的业务流程包括()。
国务院关于2010年度国家科学技术奖励的决定各省、自治区、直辖市人民政府，国务院各部委、各直属机构：为全面贯彻党的十七大和十七届五中全会精神，深入贯彻落实科学发展观，大力实施科教兴国战略和人才强国战略，推进科技进步和自主创新。国务院决定，对为我
中国特色社会主义道路的内涵，体现了( )的原理。中国特色社会主义道路之所以科学，因为它符合( )的原理。
2012年1－6月，江西省十大战略性新兴产业固定资产投资（以下简称“十大产业投资”）总量突破千亿元，达1112.52亿元，比上年同期增长24.0%，占全省固定资产投资（计划投资500万元及以上项目固定资产投资，下同）的23.5%;对全省固定资产投资增长的贡
汇编程序和编译程序翻译的目标程序需经【】连接成可执行的程序。
有如下程序：OptionBase1PrivateSubForm_Click()Dimarr,sumSum＝0arr＝Array(1,3,5,7,9,11,13,15,17,19)Fori＝1TO
最新回复
(
0
)
