首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2017-01-04
37
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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://jikaoti.com/ti/k6fjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
三国鼎立局面的关键性战争是()。
简述按照恩格斯的划分方法人类的起源与进化。
在下列哪个条约中,最先出现了片面最惠国待遇?()
原始群是以()为纽带而组成的社会组织形式。
印度种姓制度中,处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍
记载了用竿标日测影以求日高的方法,并认识了勾股定理的算书是()。
晚清时期清帝年号的正确排序是
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点u出发的最小生成树T的步骤如下:初始化U
随机试题
甲与乙共谋次日共同杀丙,但次日甲凶腹泻未能前往犯罪地点,乙独自一人杀死丙。关于本案,下列哪些说法是正确的?()(2002/2/35)
根据《职业病防治法》的规定,下列选项中不属于患职业病职工享受的待遇是()
关于阴性对比剂的叙述,错误的是
既能消食化积,又能行气散瘀的药物是
疾病的病位主要与什么有关
柴某经工商部门核准从事个体经营,并办理了税务登记。之后,清湖县地税局将个体户柴某的纳税方式由过去的定额缴税变更为自行申报缴税。2008年2月,因柴某不按规定如实申报,清湖县地税局调查核实有关情况后,责令柴某限期申报缴纳相应税款、滞纳金、柴某要求延期申报和延
在体育课教学中,黄老师尽量利用学生的多种感官和已有的经验,通过各种形式的感知,丰富学生的直接经验和感性认识,使学生获得生动的表象,从而比较全面、深刻地掌握与体育相关的理论知识,这主要体现了()原则。
幼儿在家中和学校里看到了大量的桌子,掌握了“桌子”的概念,幼儿对于“桌子”这个概念学习的方式是
Forthepastfiveyears,TianjinUniversityinnorthernChinahasprovidedfreeaccommodationforparentsinwhatitcalls"tent
某单位的办公室秘书小马接到领导的指示,要求其提供一份最新的中国互联网络发展状况统计情况。小马从网上下载了一份未经整理的原稿,按下列要求帮助他对该文档进行排版操作并按指定的文件名进行保存:参照示例文件cover.png,为文档设计封面、并对前言进行适当的
最新回复
(
0
)