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

admin2018-08-12 52

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

晚清时期清帝年号的正确排序是()

埃及曾两次被波斯帝国征服，波斯第二次征服埃及的时间是()。

毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。

我国古代推算最准确和使用最久的历法是()。

简述按照恩格斯的划分方法人类的起源与进化。

解放军渡江战役中横渡长江的东西两个攻击点是()。

下列哪两个国家是第二次工业革命的发源地和“中心”?

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

空腔脏器破裂主要的临床表现是

下列各项，不属于肉桂功效的是

外观设计取得专利权的条件是()。

我国商业银行经营的核心原则是()。

和是办理支付结算的工具。

音位的区别特征指的是音位之间的___________。(厦门大学2016)

设矩阵A与B相似，其中(Ⅰ)求x与y的值；(Ⅱ)求可逆矩阵P，使得P-1AP=B．

打开考生文件夹下的演示文稿yswg．pptx，按照下列要求完成对此文稿的修饰并保存。使用“透视”模板修饰全文，全部幻灯片切换效果为“覆盖”。