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

admin2017-01-04 83

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

概述汉代从“黄老之学”到“霸王道杂之”的思想演变。(首都师范大学2013年历史学基础真题)

简述20世纪20年代末国共两党之外的第三势力。

简述弭兵之会的背景、过程和结果。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。

唐朝时期，每丁服徭役二十天，是为正役，国家若不需要其服役，则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准，交足二十天的数额以代役，称为()。

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

简述国家的本质和职能。

清胃散中黄连是黄连解毒汤中黄连是

一男童，春感温毒，咽喉红肿疼痛，吞咽困难，口干欲饮，发热面赤，脉滑数，治疗宜首选何药

目前诊断子宫内膜异位症的最佳方法是

安全事故隐患按其可能的后果，可分为()。

中共中央政治局就中国特色社会主义理论和实践进行第七次集体学习。中共中央总书记习近平在主持学习时强调，()问题是最根本的问题。

中国近代第一位驻外公使是

Insportsthesexesareseparate.(36)andmendonotrunorswiminthesameraces.Womenarelessstrongthanmen.That(3

Thenatureofworkischanging.Recenttechnologicaladvances,ashiftfrommanufacturingtoservice-basedorganizations,incr