首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2017-01-04
79
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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/IQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述美苏争霸的三个阶段,并分析其影响与教训。
格拉古兄弟改革的内容和结果是什么?
【《关于正确处理人民内部矛盾的问题》】
1949年,中共召开七届二中全会主要是为了()。
下面哪部经典是我国最早的官方史书?()
记载了用竿标日测影以求日高的方法,并认识了勾股定理的算书是()。
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
将两个长度为N的有序表归并到一个长度为2N的有序表,最少需要比较的次数是(),最多需要比较的次数是()。
随机试题
A.24小时pH监测B.食管滴酸试验C.内镜检查+活检D.食管吞钡检查诊断胃食管反流病最准确的方法
货物的使用成本主要包括()等。
沥青混凝土路面不平整的预防措施主要有( )。
控制整个项目实施阶段的进度,以及项目动用前准备阶段的工作进度,是__________的任务。()
某公司非常霞试产品定价工作。公司负责人强调,产品定价一定要正确反映企业产品的真实价值消耗和转移,保证企业简单再生产的继续进行,在下列定价方法中,该公司不宜采用的是()
下列有关类成员的叙述中,正确的是()。
Therearefivebasic【C1】______ofanewspaper:toinform,tocomment,topersuade,toinstructandtoentertain.Youmaywellthi
It______ontheInternetwithrespondentswhovolunteeredtoparticipate,andwasnotascientificallyrandomsurvey.
Thesunrisesintheeastandsetsinthewest,soitseemsasifthesun________roundtheearth.
Sincethenthenumberofpeopletakingdrivinglessons______20%.
最新回复
(
0
)