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

admin2016-03-29 65

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

选项

答案因为基数排序所需的时间不仅与文件的大小n有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为厂，显然，十进制数基数为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/11Ri777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

元代对边疆地区的统治方式不同于其他三地的一地是()。

战国初期，上党地区在下列哪一个国家的控制范围之内?()

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

法国历史上的第一部共和制宪法是()。

宋代由于旧坊制被打破，城市中行业分区性逐渐消失，北宋政府通过()来控制商人和商业。

武则天时期，为了管理天山以北的广大区域而设立了()。

系统产生死锁的可能原因是()。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

腋肿，甚则胸胁支满，是哪条经脉病证的临床表现

fluidextracts：

某写字楼建设工程施工，对基槽进行检测，填写基槽验线记录。基槽验线记录的填写要求有哪些?

()是负刑事责任的依据。

混凝土耐久性包括混凝土的()等。

根据《公司法》规定，属=F有限责任公司特征的是()。

下列选项中，符合所给图形的变化规律的是：

____________的《普通教育学》被认为是真正教育学建立的标志。(暨南大学2016)

Ifanewcharteroftherightsofpeople(intheFirstWorld,orNorth,orwhateveryouliketocallthepartwherepeopletono