首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2017-01-04
81
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
西哥特人图鲁兹建立起第一个得到罗马帝国承认的蛮族王国——西哥特王国的时间是()。
新王朝时期出现了什么类型的墓?()
下列现象由中国近代社会的半殖民地半封建性质所决定的有()。①民族资产阶级提不出彻底的民主革命纲领②中国无产阶级先于中国民族资产阶级而产生③帝国主义在华的“租界”林立④中国革命必须走农村包围城市的道路
简述苏联建立“东方战线”的过程及其影响。
以下称呼不是指代李自成的是()。
中共中央通过《关于建国以来党的若干历史问题的决议》的会议是()。
斯蒂文逊负责勘测和修建的世界上的第一条公共交通铁路通车于()。
在1875年宪法中关于法国立法权的叙述,不正确的是()。
埃及巴达里文化、涅伽达文化工、涅伽达文化Ⅱ三个阶段属于什么时代的文化?()
在因特网中,IP数据报的传输需要经由源主机和中途路由器到达目的主机,下面说法正确的是()。
随机试题
设f(x)在[a,b]上连续,且a≠-b,则下列各式不成立的是()
该症最主要的临床表现为对心内膜强力纤维增生症.主要应用洋地黄控制心力衰竭,需长期服用,直到
下列有关国有独资公司的说法正确的是:
现行企业所得税具有的特点有()。
金银首饰与其他产品组成成套消费品零售的,应将金银首饰与其他产品的销售额分摊,并按分摊后金银首饰的销售额征收消费税。()
二次型f(x1,x2,x3)=x12+ax22+x32+2x1x2+2x1x3+2x2x3的正惯性指数为2,a应满足什么条件?
面向对象程序设计的基本思想是封装和可扩展性,可扩展性体现在继承性和______两个方面。
下面关于多窗体程序设计描述不正确的是
Henrywantedtheclerktosendagooddoctortohisroom.Henrywantedtoknowhowmuchitcosttogotothedoctor.
Forthispart,youareallowed30minutestowriteashortessayentitledArtEducationCoursesinColleges.Youshouldwriteat
最新回复
(
0
)