首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2017-01-04
61
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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
学硕统考专业
相关试题推荐
比较工业革命和第二次工业革命,分析英、法、德、美工业革命的过程和特点。
在印度独立和巴勒斯坦建国问题上,英国扮演了什么角色?有什么影响?
格拉古兄弟改革
奥斯曼国家的第一个苏丹是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
站控系统的组成有哪些?
下面有关组织固定的描述,不正确的是
有关慢性肾炎,下列哪项是正确的
承包人不能按时开工,应在不迟于约定的开工日期(),以书面形式向工程师提出延期开工的理由和要求。
危害和整改难度较小,发现后能够立即整改排除的安全生产事故隐患是指()。
爆破拆除工程应进行(),并经当地有关部门审核批准后方可实施。
当室内高度超过6m且具有自然对流条件时,防烟分区的长边可不大于()。
简述教育行政诉讼的范围。
Oneofthebasiccharacteristicsofcapitalismistheprivateownershipofthemajormeansofproduction—capital.Theownership
HowmanypeopleturnedupforSenatorNelson’sfirstEarthDayTeach-in?
最新回复
(
0
)