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

admin2017-01-04 65

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

选项

答案因为基数排序所需的时间不仅与文件的大小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://www.kaotiyun.com/show/IQRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

简述苏联和南斯拉夫之间的冲突。

文艺复兴运动兴起的时间是()。

“我不想变成上帝，或居住在永恒之中，或者把天地抱在怀里，属于人的那种光荣对我就够了。我自己是凡人，我只要求凡人的幸福。”这句话体现的思想是()

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

宋文帝于元嘉年间发动的对北魏的北伐战争，此战又称()。

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

德国纳粹党消灭资产阶级民主制的关键性事件是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

医生的权利医务人员的道德义务

WhendidMr.Schallerbecomeinterestedinanimals?

地下水水质类型中，V类的适用功能是()

()年，中国人民银行颁布了《个人住房担保贷款管理试行办法》。

个人理财业务是建立在()基础上的银行服务。

“在整个社会主义初级和实现社会主义现代化的全过程中，都要坚持两手抓，两手都要硬的方针，绝不能一手硬一手软，也不能一段时间硬，一段时间软。”在这里，两手抓是指()。

Studythefollowingdrawingcarefullyandwriteanessayinwhichyoushould1)describethedrawing,2)interpretitsm