首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2023-02-06
33
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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/tBwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
李老师为了讲解好“买方市场与卖方市场”这一知识点,为学生播放了不同的买卖视频录像,让学生更为直观地理解买方市场与卖方市场的区别。在这种导课方式中,李老师主要是()进行导课的。
古语“不愤不启,不悱不发”启示教师在教学过程中要注意运用()的教学原则。
说服教育法的方式主要有()。
教育目的的个人本位论认为,要根据个体的本能需要、兴趣和爱好来确定教育目的。()
关于我国教育道德,以下说法错误的是()。
某中学在学期末开展对学生的综合素质评价工作,不仅提前公布了评价的内容、标准、方法、程序以及相关评价人员和制度,设置了教师、学生、家长等多种人员参与的评价体系,还建立了相应的学生申诉制度。其最终目的是确保评价工作的()原则。
长棘海星,这种像仙人球一般长满尖刺的生物,是珊瑚礁生态系统的主要捕食者。成年长棘海星的身体直径可以达到35厘米,有记录的最大个体甚至能超过75厘米。长棘海星以各类珊瑚,尤其是造礁珊瑚为食,被啃食的珊瑚只会留下白森森的外骨骼。如同肆虐于草原和农田的蝗灾一样,
把(1)图放在最左边,(2)(3)(4)图放在后面,共有6种排列,其中()能使四图之间存在逻辑关系。
一部真正意义上的通史,绝非只是对史事的_____,而是要努力探求历史变迁的内在联系。所以通史不仅指史事在时序上的先后承继、转合_____,而且还包括历史文化中各重要问题的_____与变迁的_____,即所谓“通古今之变,成一家之言”。填入横线处的词语最恰
指令流水线中,不同的指令在指令流水的不同功能段中可以()。
随机试题
乳蛾的治疗原则是
根据规定,对于银行汇票,下列说法正确的有()。
在中国共产党创建初期和国民革命时期,标志着毛泽东思想萌芽的是新民主主义革命基本思想的提出。()
在发行可转换债券时,设置赎回条款,主要是为了保护债券持有人资产安全性。()(东北财经大学,2011)
在我国,决定省、自治区、直辖市的范围内部分地区进入紧急状态的机关是
2
设A是m×n矩阵,且m>n,下列命题正确的是().
OnceEinsteingavealectureinmanyplacesinAmerica.Hisdriveralwayslistenedtohimandknewthelecturesowellthathew
Expertspredictthattheprinted,paperandgluebookwillberenderedobsoletebyelectronictextdeliverysystems,ofwhichon
AstronomersattheUniversityofCaliforniadiscoveredoneofthemostdistant______
最新回复
(
0
)