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

admin2019-08-15 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://www.kaotiyun.com/show/1KCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

为了顺利开展武装起义的准备工作，在彼得格勒苏维埃中成立了()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

清朝的()划定了中俄两国中段边界，是继续谈判确立两国相互关系的全面条约的基础

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。

下面元件存取速度最快的是()。

胃的募穴是心包的募穴是

房地产开发项目工程设计，一般分为()阶段。

犯罪未遂具有()特征。

从我国历史和现实的国情出发，社会主义道德建设要坚持的最根本的原则是：

凯洛夫《教育学》曾对我国教育理论与实践产生过重大影响，其思想的主要特点是()。(2013年)

设Ω是由曲面y2+x2=1，｜x+y｜=1，｜x－y｜=1围成，则Ω的体积V=_______．

以下关于数据字典说法错误的是______。A)数据元素词条描述图中每一个数据结构都是由数据元素构成的B)数据元素是数据处理中的最小单位C)数据存储描述信息包含数据存储名D)数据流不可为记录、组合项或基本项

子过程Plus完成对当前库中"教师表"的工龄字段都加1的操作。SubPlus()DimwsAsDAO.WorkspaceDimdbAsDAO.DatabaseDimrsAsDAO.RecordsetDimf