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

admin2023-02-06 89

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

个体身心的某些方面在较早的年龄就已达到较高的发展水平，而有些方面则需要到较晚的年龄阶段才能达到成熟水平。这一特点要求()。

赫尔巴特认为教学过程可分为()、联想、系统和方法四阶段。

下列中国古代著名文学家及其主要作品对应错误的是()。

()主张评价应关注非预期的结果、评价的重点应放在课程计划实际的结果上、更多地考虑课程计划满足实际需要的程度。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

制作药酒的热浸法，即煮酒法，先将_______同煎后冷密封储存，约15天左右可取清液，如青梅煮酒。

伤后眩晕临床常见于（）

甲企业与乙运输公司签订了货物运输合同，在合同履行过程中，甲企业未按合同内容履行合同，乙运输公司可将其货物()。

企业的法定盈余公积按税后利润的10%计提，当盈余公积达到注册资本的25%时，可不再提取。()

概念的内涵与外延成正比。()

反映一个国家或地区教育工作总要求的是()

根据婚姻法的有关规定，下列财产属于婚姻关系存续期间，夫妻共有财产的有()。

实践是认识的基础。它对认识的决定作用主要表现在

在窗体上添加文本框Text1，然后编写下列程序：PrivateSubForm_Load()Text1.Text=""EndSubPrivateSubText1_KeyPress(KeyAsciiAsIn