首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2019-08-01
56
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小n有关,而且与关键字的位数和关键字的基数有关。设关键字的基数为r,显然,十进制数基数为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/bNCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述第二次世界大战中各主要战场战略性转折的时间及其代表性战役。
列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。
论述欧洲一体化的进程及影响。
晚清时期清帝年号的正确排序是
洋务运动期间,军事企业主要采取的方式是()。
简述大化改新的内容和影响。
试述新生活运动的主要内容并作评价。
()是清代管理边疆少数民族地区事务的机关,也掌管一部分外交事务。
制瓷业是光彩夺目的一个手工业部门,北宋的制瓷业的重心在黄河流域和中原地区。回答问题:北宋的四大名窑是()
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
随机试题
小张今年5岁,智力正常,但先天腿部残疾。下列有关小张的权利能力和行为能力的说法中,正确的是()。
Themusicsounds,atfirst,likeitbelongsinapoweryogastudio:electronicandrhythmic,risingandfallinglikebreaths.Bu
硅肺可以引起
A.胆B.胃C.小肠D.大肠E.膀胱具有“主津”功能的是
请根据以上资料,选择以下栏目正确选项:“结汇方式”栏:
2018年国务院政府工作报告指出.2018年我国要继续创新和完善宏观调控,把握好宏观调控的度,保持宏观政策连续性稳定性,实行()。
游客登山扭伤,紧急处理后,患者需要多长时间后,应用热毛巾热敷患处,加速血液循环()
manipulation
Iftheworld’seducationsystemshaveacommonfocus,itistoturnoutschool-leaverswhoareproficientinmaths.Governments
December1st,2014DearMr.Dias,Furthertoyourletterof22November,Iamveryhappytosaythatwearenowinapositi
最新回复
(
0
)