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

admin2019-08-01 79

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

曾被日本维新派人士视为“枕中鸿宝”，对日本明治维新产生重要影响的著作是()。

完整地表述电磁场理论的物理学家是()。

标志着整风运动开始向反“右派”斗争转变的重要文件是()。

中国第一个资产阶级革命团体兴中会建立的时间是()。

经六朝时期的发展，南方形成了三个农业发达地区即()。

简述大化改新的内容和影响。

两税法产生的背景、内容是什么?并对其进行评价。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

()年，中国人民银行放开了银行间同业拆借利率，为利率稳步推进利率市场化改革奠定了基础。

航空货运单编号一般采用11位数字，前3位数字是()

妊娠足月胎盘的大体结构不恰当的是

吴瑭(《温病条辨》)所称"辛凉轻剂"指的是()吴瑭(《温病条辨》)所称"辛凉平剂"指的是()

治疗厌氧菌感染的急性盆腔炎时，常使用的抗生素是()

政府对金融市场实施监督的主要形式有：()。

客户关系管理中，基本层面的、面向企业内部的、与ERP(企业资源计划)有一定联系和交叉的内容有()。

circulareconomy

在SQLServer2008中，事务日志备份仅可用在完整恢复模式和【12】日志恢复模式中。