首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2016-03-29
43
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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
学硕统考专业
相关试题推荐
绿林军领袖为了大影响,拥立汉宗室()为皇帝,恢复汉的国号,以公元23年为更始元年。
西哥特人图鲁兹建立起第一个得到罗马帝国承认的蛮族王国——西哥特王国的时间是()。
新王朝时期出现了什么类型的墓?()
春秋大国争霸与战国兼并战争如何区别?
第二次世界大战给全人类的启示是()①维护世界和平是当代各国人民的共同任务②必须坚持反对霸权主义和强权政治③必须发展和壮大世界和平力量④必须建立国际政治经济新秩序
永元四年(公元92年),汉和帝用宦官()掌握的一部分禁军,消灭了窦氏势力。郑众从此参预政事,并受封为侯,这是宦官用权和封侯的开始。
简述希腊地理环境对其历史的影响。
下列哪一个不是罗马王政时代的管理机构?()
四位运算器框图如下图所示,ALU为算术逻辑单元,A和B为三选一多路开关,预先已通过多路开关A的SW门向寄存器R1,R2送入数据如下:R1=0101,R2=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下:(1)R1
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中:P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
随机试题
驾驶机动车在路口遇到这种情况要随时准备停车礼让。
A.X线钡剂灌肠示结肠铅管征B.X线钡剂检查示回肠末端呈线样C.X线钡剂检查示回盲部呈钡影激惹征D.X线钡剂检查示胃肠运动加速,结肠袋加深,张力增强Grohn病
X线片上可以没有明显骨质破坏表现的病变是
轻质隔墙包括()。轻质隔墙的特点有()。
组织承诺的影响后果是很明显的,员工对组织的承诺越高,离职率()。
企业合并,在一般性税务处理条件下,当事各方下列处理正确的有()。
2015年,某省对农民工在本市(区、县)创业的意愿进行了调查,共完成有效样本3000个,调查结果如下:以下折线图中,能准确反映2011—2014年该省平均每创办一个企业所需的创业者人数的变化关系的是:
关于我国诉讼程序中的鉴定,下列说法错误的是()。
创建查询的方法有两种,分别为“使用向导”创建和【】创建。
Wheredoesthetalktakeplace?
最新回复
(
0
)