首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2016-03-29
84
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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
学硕统考专业
相关试题推荐
概述新中国建国初期的形势和任务。
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
罗斯福和胡佛经济政策的最大区别在于()。
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
全国高校院系调整的具体时间是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
随机试题
简述儒家和道家对中国人的影响。
下列属于肾病综合征的诊断标准的是()。
《继承法》第16条第2款规定:“公民可以立遗嘱将个人财产指定由法定继承人的一人或者数人继承。”从法的规范作用看,该项规定属于下列哪种情况?()
李某囚犯盗窃罪被扭送派出所。在公安机关审讯期间,又交代了自己的其他罪行。如果李某交代的本人其他罪行是另一起独立的盗窃犯罪行为,对其主动交代的罪行的处罚原则是()。
掉期外汇买卖实际上是由两笔金额相同、方向相反、交割日期相同的交易构成的。()
关于定性市场预测,下列说法错误的是()。
认为教师的责任在于使学生形成良好的习惯,怀抱德行与智慧的思想家是()。
传染病的预防措施主要有()。
阅读下面的材料,回答第125~128题:中共中央宣传部组织编写的《“三个代表”重要思想学习纲要》中指出:代表中国先进生产力的发展要求,代表中国先进文化的前进方向,代表中国最广大人民的根本利益,是统一的整体,相互联系、相互促进。发展先进生产力,是发展
PlagiarismLinesBlurforStudentsinDigitalAgeAtRhodeIslandCollege,afreshmancopiedandpastedfromaWebsite’sfr
最新回复
(
0
)