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

admin2016-03-29 103

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

选项

答案因为基数排序所需的时间不仅与文件的大小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

学硕统考专业

同盟会影响下发生的第一次大规模武装起义的地点在()。

光绪皇帝颁布“明定国是”诏书的时间是()。

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

下列关于第二三次科技革命的说法，不正确的是()。

中国封建社会后期的第一个启蒙学派是由王艮开创的()。

中古时代实行索贡巡行赋税征收方式的国家是()。

武昌起义是由哪个团体发动的?()

案例分析题适当的组织结构制订良好的计划常常因为管理人员没有适当的组织结构予以支持而落空。在某一时期还是合适的组织结构，可过了一两年后就不再合适。格里•利兹(GerryLeed

关于肱骨的描述，错误的是

治疗慢性肺心病心力衰竭的首要措施是（）

高某系一抢劫案的被害人。关于高某的诉讼权利，下列哪些选项是正确的?

下列哪一项属于后台管理系统应当符合的要求?()

下列旋律属于()

某单位有52人投票，从甲、乙、丙三人中选出一名先进工作者。在计票过程中的某时刻，甲得17票，乙得16票，丙得11票，如果规定得票比其他两人都多的候选人才能当选，那么甲要确保当选，最少要再得票()张。

试述牙萌出的顺序及特点。

已知y=，则y″=______。