首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2019-08-01
57
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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/bNCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述第二次世界大战中各主要战场战略性转折的时间及其代表性战役。
曾被日本维新派人士视为“枕中鸿宝”,对日本明治维新产生重要影响的著作是()。
明清时期专制主义空前加强,据此回答问题:清代在散文方面,声势最大、影响最广的是桐城派,不属于该派的是()
二次大战后,主要资本主义国家经历了增长时期,首先开始这个进程的国家是()。
在太平天国时期,对晚清兵制以及政局产生深远影响的是()。
据史记《商君传》商鞅变法,“为田开阡陌封疆,而赋税平”其目的
试论魏孝文帝改革的内容及其意义。
简述大化改新的内容和影响。
()是清代管理边疆少数民族地区事务的机关,也掌管一部分外交事务。
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
随机试题
在PowerPoint2003中,可以使幻灯片上的文本、图形、图表或其他对象具有动画效果。设置动画效果时,除了采用“自定义动画”功能外,还可以采用“_______”功能简化动画设计。
耳鸣、耳聋的病因为
患者男,15岁。颈部淋巴结肿大,皮肤瘙痒,间歇性发热3个月。查体:脾大,左肋下3cm,颈淋巴结活检为霍奇金病。HD最常见的自发症状为
女,29岁,婚后6年未孕。月经7~20天/35~120天。发育良好。妇科检查:双侧卵巢稍增大,余未见明显异常。如男方精液检查正常,输卵管通畅,最先考虑的疾病为
关于护理记录错误的是()。
有关装饰装修裱糊工程的质量要求,下列表述何者不对?[2004年第116题]
银行审核支票付款的依据是支票出票人的()。
用如图所示电路测量干电池的电动势和内阻(电动势约为1.5V,内阻约0.5Ω,允许通过的最大电流为0.6A)。图中电压表的量程为2.0V,内阻为3000Ω;电流表的量程为0.10A,内阻为5.0Ω。除被测电池、开关和导线外,还有如下器材:A.滑动变阻器:
《推进共建“一带一路”教育行动》提出沿线各国教育合作的重点是()。
下列关于计算机病毒的4条叙述中,有错误的~条是
最新回复
(
0
)