首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
admin
2012-06-26
126
问题
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
选项
A、O(n)
B、O(n
2
)
C、O(logn)
D、O(nlogn)
答案
D
解析
在排序过程中,每次比较会有两种情况出现,若整个排序过程中至少需要t次比较,则显然会有2
t
种情况,由于n个记录总共有n!种不同的排列,因而必须有n!种不同的比较路径,于是有:2
t
≥n!,即t≥log
2
(n!)。因为log
2
(n!)≈nlog
2
n,所以t≥nlog
2
n。
转载请注明原文地址:https://www.kaotiyun.com/show/qfxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
西汉诸侯国的政权机构和中央基本上相同,其中需要中央直接任命的有()
古埃及第24朝法老波克利斯进行改革,宣布废除奴隶制,债权人只能索取债务人的财产作抵偿,而不能占有债务人的人身,因为财产属于个人,而公民人身属于国家,国家需要他们服役。该改革旨在
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
已知一个线性表(38,25,74,63,52,48),表长为16,假定采用散列函数h(key)=key%7,计算散列地址,并存储在散列表中,若采用线性探测方法解决冲突,在该散列表上,进行等概率成功查找的平均查找长度为()。
在某个操作系统中,通过大量的实验,人们观察到在两次缺页中断之间执行的指令数与分配给程序的页框数成正比,即可用内存加倍,缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要100ns,但若发生了缺页中断就需要1ms。一个程序运行了60s,期
在采用线性探测法处理冲突所构成的散列表上进行查找,可能要探测多个位置,在查找成功的情况下,所探测的这些位置的键值()。
随机试题
以下哪种行为破坏了茶艺人员服务规范
腕关节掌侧玻璃切割伤,出现哪项体征说明有正中神经损伤
师某几年来共盗窃自行车五百多辆,案发后在横穿公路时突被一辆卡车撞死。司法机关对师某的盗窃行为可能作出的正确决定是()。
向已有地方标准的区域排放污染物时,应当执行()。
下列适用15%的企业所得税税率的企业所得有()。
国家信用的主要形式有()。
已知下列非齐次线性方程组:求解方程组(I),用其导出组的基础解系表示其通解;
MoneyinAmericaMoneyisusedtobuygoodsorservicesand【1】______debts. 【1】_________InAmerica,moneysupplycon
Americansareahighly【B1】______people.Whatfactorscausethemtomove?Thedesireforeconomicbettermentis【B2】______themo
A、Theplaneissafeeveniftwoofitsenginesfail.B、Therearethreeenginesoneachofthegiantjetplane.C、Thereisanext
最新回复
(
0
)