首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2016-03-29
80
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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://www.kaotiyun.com/show/11Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
凡尔赛体系是由一系列条约组成的,其中战胜国与匈牙利签订的条约为()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
中共十一届三中全会后对外开放开始起步,1980年中央决定设立()。
中华人民共和国恢复了在联合国合法席位的时间是()。
东汉时期成书的崔定()主要是地主经营田庄的家历,但是,书中所记农业技术经验也很丰富,为后人所取法。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是()。
我国第一部系统的史学理论著作是()。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
随机试题
Readingisthoughttobeakindofconversationbetweenthereaderandthetext.Thereaderputsquestions,asitwere,tothet
去年以来,全国许多主要城市的房地产价格出现不同幅度的增长,有些城市甚至创出近期新高。这是自去年国家出台一系列调控措施后,房地产价格再次出现上涨。这也使社会舆论再次就经济是否过热展开了争论。在此背景下,有人认为,国家去年出台的宏观调控措施未达到预期效果。以
下列不属于时间估算中可以利用的历史资料是()。
纳税人享受减税、免税待遇的,在减税、免税期间可以暂不办理纳税申报。()
当学生获得好的成绩后,老师和家长给予表扬和鼓励,这符合桑代克学习规律中的()。
空调:遥控器:电视
执法为民是社会主义法治的本质要求。下列哪一做法不符合执法为民的理念?
红色政权能够存在和发展的客观条件有
Therewasachildreadytobeborn.SoheaskedGod,"TheytellmeyouaresendingmetotheearthbuthowamIgoingtoliveth
DietingadvisorDr.RobertAtkinsrecommendseatingadiethighinproteinforthosewhowanttoloseweightandkeepitoff.Th
最新回复
(
0
)