首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2016-03-29
34
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小n有关,而且与关键字的位数和关键字的基数有关。设关键字的基数为厂,显然,十进制数基数为10,二进制数的基数为2。要建立r个空队列所需时间为O(r);把n个记录分放到各个队列中,重新收集起来需要的时间为O(n),因此一趟排序所需的时间复杂度为O(n+r);若每个关键字有d位,则总共要进行d遍排序,所以基数排序的时间复杂度为O(d(n+r))。由于关键字的位数d与基数r和最大关键字取值有关。因此不同的r和关键字将需要不同的时间。所以,本题中总的时间复杂度为O(d(n+2)),d为关键字最大值对应的二进制数位数,即将十进制的关键字用二进制数表示时,复杂度增大了。另外只需要设置两个指针队列,即将十进制的关键字用二进制数表示时,空间复杂性减少了。
解析
转载请注明原文地址:https://kaotiyun.com/show/11Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
19世纪80年代,国际工人运动中影响最大的是()。
简述美国“柯立芝繁荣”的主要表现,分析其产生原因。
解析两个战场的地位、作用及相互关系。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
在捍卫和传播生物进化论方面做出了贡献的是()。
1936年,德奥双方通过(),德国基本上控制了奥地利的内政和外交。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
IEEE754标准规定的64位浮点数格式中,符号位为1位,阶码为11位,尾数为52位。则它所能表示的最小规格化负数为()。
设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
随机试题
决定肺部气体交换方向的主要因素是( )。
类风湿关节炎的特征性关节改变是
根据《物权法》的规定,下列财产可以设定抵押权的有()。
昆曲是国粹、是遗产,对大多数人而言,不过是阳春白雪,很多人都没有品尝过_______的昆曲.但是由昆曲演化而来的京剧,倒是_______。填入划横线部分最恰当的一项是:
A.Well,aboutcostumesB.ButyouknowmewithfashionC.Ikindoffeelthatit’smoreaboutmusicitselfD.Soyouhavetoch
据统计,西式快餐业在我国主要大城市中的年利润率,近年来稳定在2亿元左右。扣除物价浮动因素,估计这个数字在未来数年中不会因为新的西式快餐网点的增加而有大的改变。因此,随着美国快餐之父艾德熊的大踏步迈人中国市场,一向生意火爆的麦当劳的利润肯定会有所下降。以下
设随机变量U服从二项分布B(2,),随机变量求随机变量X—Y与X+Y的方差和X与Y的协方差。
某系统的可靠性结构框图如下图所示。该系统由4个部件组成,其中2、3两部件并联冗余,再与1、4部件串联构成。假设部件1、2、3的可靠度分别为0.90、0.70、0.70。若要求该系统的可靠度不低于0.75,则进行系统设计时,分配给部件4的可靠度至少应为___
Conventionalwisdomaboutconflictseemsprettymuchcutanddried.Toolittleconflictbreedsapathyandstagnation.Toomuch
A、Forprotectionagainstotherdogs.B、Forprotectionagainstotheranimals.C、Justforfun.D、Forthepurposeofguardingtheh
最新回复
(
0
)