将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

admin2016-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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

计算机408

学硕统考专业

概述新中国建国初期的形势和任务。

()是一部上起传说中的黄帝，下迄汉武帝时期的中国通史，是中国历史上第一部内容完整、结构周密的历史著作。

罗斯福和胡佛经济政策的最大区别在于()。

1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

全国高校院系调整的具体时间是()。

下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府

简述儒家和道家对中国人的影响。

下列属于肾病综合征的诊断标准的是()。

《继承法》第16条第2款规定：“公民可以立遗嘱将个人财产指定由法定继承人的一人或者数人继承。”从法的规范作用看，该项规定属于下列哪种情况?()

李某囚犯盗窃罪被扭送派出所。在公安机关审讯期间，又交代了自己的其他罪行。如果李某交代的本人其他罪行是另一起独立的盗窃犯罪行为，对其主动交代的罪行的处罚原则是()。

掉期外汇买卖实际上是由两笔金额相同、方向相反、交割日期相同的交易构成的。()

关于定性市场预测，下列说法错误的是()。

认为教师的责任在于使学生形成良好的习惯，怀抱德行与智慧的思想家是()。

传染病的预防措施主要有()。

PlagiarismLinesBlurforStudentsinDigitalAgeAtRhodeIslandCollege,afreshmancopiedandpastedfromaWebsite’sfr