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

admin2023-02-06 68

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

选项

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

学硕统考专业

《党政机关公文处理工作条例》规定，公文处理工作应当坚持的原则包括()。

关于我国教育道德，以下说法错误的是()。

课堂上经常出现这样的情况：在老师讲课的过程中，有的学生会在下面偷偷聊天；在做练习时，有的学生总是窃窃私语或很自由地大声讨论问题；一讨论起问题，学生就会争论不休。对此，下列相关表述最恰当的是()。

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

下列有关生活中常见的物理常识的叙述正确的是：

某指令流水线分为五级，分别完成取址(IF)、译码并取数(ID)、执行(EX)、访存(MEM)、写结果(WR)。设完成各阶段操作的时间依次为：90ns，60ns，70ns，100ns，50ns。试问：流水线的时钟周期应取何值?若第一条和第二条指令发

A．腰交感神经切除术B．旁路转流术C．血栓内膜剥脱术D．游离血管蒂大网膜移植术E．分期动、静脉转流术短段动脉阻塞的病人适用于（）

关于酶与底物的关系，正确的是

细胞坏死的主要形态学特征是

股票价格指数与经济周期变动的关系是()。

我国第一家全国性股份制商业银行是中国银行。()

影调往往指镜头画面的()。

下列哪一个关键码序列不符合堆的定义?

确定一个控件在窗体上的位置的属性是()。

Manyofthemostdamagingandlifethreateningtypesofweather,suchastorrentialrainsandseverethunderstorms,beginquickl

Universalizationofeducationhasbeenapolicypriority,butitstillremainsanunfulfilleddream.Asaconsequence,thespre