首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2017-01-04
30
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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
学硕统考专业
相关试题推荐
简述美国全球外交战略的演变过程。
关于希腊古风时代和古典时代的叙述不正确的是()。
下列不是苏俄实行战时共产主义政策原因的是()。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式,最早提出这种方式的是()
西汉的主要赋税形式中。征收对象是儿童的是()。
到1869年为止,人类已发现了多少种化学元素()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
随机试题
Forthispart,youareallowed30minutestowriteacompositiononthetopicChoosinganOccupation.Youshouldwriteatleast
休克治疗过程中,动脉压较低,中心静脉压也较低,提示_____________;如动脉压较低,而中心静脉压偏高,提示_________________。
最易发生DIC的急性非淋巴细胞白血病的亚型是
髂-股静脉血栓行取栓术的时限是()
A、酸枣仁B、朱砂C、磁石D、远志E、合欢皮治肝阳上扰,失眠眩晕,宜选用的药物是()
景区讲解员讲解时要视游客的类型、兴趣、爱好的不同有所侧重,因人施讲,内容的取舍应以()为原则。
A、 B、 C、 D、 A观察阴影,三个图各不相同,故答案为A。
看涨期权的买方具有在约定期限内按()价格买入一定数量金融资产的权利。
下面关于算法的叙述中,正确的是()。
HumanMigrationHumanmigration:thetermisvague.Whatpeopleusuallythinkofisthepermanentmovementofpeoplefromoneho
最新回复
(
0
)