首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2019-08-01
26
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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://jikaoti.com/ti/rEGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
公元843年,查理曼的三个孙子签订《凡尔登条约》三分查理曼帝国,奠定的三个国家的形是()。①德意志②法兰西③西班牙④意大利
简述第二次世界大战中各主要战场战略性转折的时间及其代表性战役。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
公车上书后,由维新派和翰林院侍读学士文廷式发起成立的,以挽救时局为宗旨的组织是()。
()是清代管理边疆少数民族地区事务的机关,也掌管一部分外交事务。
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
某计算机系统字长为32位,包含2个选择通道和1个字节多路通道,每个选择通道上连接了2台磁盘机和2台磁带机,字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下:磁盘机:800KB/s磁带机:200KB/s
随机试题
针对预计负债的估计金额,下列说法中,错误的是()。
WhydoreadersofNewScientistcontinuetogetsteamedupaboutrace?Afterall,itcanbeusedasaninnocuoustechnicalterm
某高速公路设计车速120km/h,路面面层为三层式沥青混凝土结构。施工单位为某一大型公路专业施工企业,设施精良,技术力量雄厚。为保证工程施工质量,施工时作了如下控制:(1)选用合格的石料进行备料,严格对下承层进行清扫,并在开工前进行试验段铺筑;
根据证监会的要求,证券营业部实行责任分离制度,现金和有价证券的保管应当与财务记录相分离。( )
对于交易席位的使用,下列选项正确的是()
下列企业变动情形中,需要注销原有税务登记的是()。(2008年)
货币经纪公司的业务范围是()。
团体沟通的作用有()。
Dolphinsarenottheonlyanimals(31)humansthatusesoundsinanapparentlyintelligentmanner.Whalesalsouseacomplexsys
A、Hecan’tteareitherpieceofcloth.B、Hewantspartofeachpieceofcloth.C、Thepiecesofclotharemadebyasecretproces
最新回复
(
0
)