首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2016-03-29
72
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
光绪皇帝颁布“明定国是”诏书的时间是()。
分析战后美国经济发展出现黄金时期的原因。(厦门大学2015年历史学基础真题)
战国初期,上党地区在下列哪一个国家的控制范围之内?()
第二次世界大战期间,苏、美、英三国首脑达成的协议中未能实现的是()。
下列关于清朝军机处的叙述,不正确的是()。
德里苏丹国前三位苏丹均为奴隶,同时皆属于()。
假定有一条通带为100kHz的信道,每路信号的带宽为3.2kHz,各路信号间的防护带宽为0.8kHz。若采用频分多路复用,那么最多可以同时传输()路信号。
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
出现下列的情况可能导致死锁的是()。
两个进程P、Q都需要三个资源1,2,3,系统中有资源1、2、3各一个,如果P请求资源的顺序是1、2、3,Q请求资源的顺序任意,共有3!=6种排列,其中共有()个排列可能导致死锁。
随机试题
下列选项中,有关仲裁裁决的表述正确的有()
人民检察院上下级之间的关系是()
女性,65岁,发现左侧肢体活动不能1.5小时。既往有高血压病10年。检查:意识清楚,瞳孔等圆,肌力2级。为明确诊断,最有鉴别价值的辅助检查为
A.风寒感冒证B.风热感冒证C.暑湿感冒证D.外感风寒挟湿证E.外感风寒、内伤食积证感冒清热颗粒的主治是()。
支气管扩张病人出现哪种情况提示有混合性厌氧菌感染( )。【历年考试真题】
《中央企业重大法律纠纷案件管理暂行办法》中的重大法律纠纷案件是指()案件。
函数y=f(x)在点x=x0处取得极小值,则必有()。
受托机构应与信用评级机构就资产支持证券跟踪评级的有关安排作出约定,并应于资产支持证券存续期内每年的()前向投资者披露上年度的跟踪评级报告。
根据专家推断,2006年内人民币将升值3%左右,按4月5日外汇市场美元兑人民币汇率的中间价推算,人民币对美元的汇率到2006年年底将跌至多少?()2005年中国的外汇储备增幅为()。
地球上四分之三的物种在白垩纪古近纪分界时的大灭绝事件中消失了.有人认为希克苏鲁伯陨石撞击是主因,德干暗色岩火山喷发是次因。但二者时间接近,很难区分。科学家利用新发现的化石记录研究了此事件。研究显示,物种大灭绝和两次温度迅速上升相对应。第一次灭绝事件与火山爆
最新回复
(
0
)