首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
admin
2017-01-04
51
问题
将十进制的关键字用二进制数表示,对基数排序所需的时间和附设空间分别有什么影响?各是多少?
选项
答案
因为基数排序所需的时间不仅与文件的大小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
学硕统考专业
相关试题推荐
下列改革内容不是在《天朝天亩制度》中提出的一项是()
关于闭关政策的叙述中,不正确的是()。
论述太平天国起义对晚清政局的影响。(中南大学2014年中国近代史真题)
1543年发表解剖学专著《人体结构论》的是()。
拉美独立后,各国政治上的一种普遍现象是(),实质上它是拉美各国大地主专政的一种特殊形式。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
将两个长度为N的有序表归并到一个长度为2N的有序表,最少需要比较的次数是(),最多需要比较的次数是()。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
随机试题
磷酸果糖激酶是葡萄糖酵解过程中最关键的调节酶,ATP与该酶的关系()。
能用于常规查体,且能发现早期肾癌的简便方法是
患儿男性,12岁,自幼发现心脏杂音,平素易感冒,查体发现胸骨左缘第2肋间收缩期轻震颤及杂音,超声心动图提示降主动脉及肺动脉之间可见分流。患儿近2周来感冒后反复出现寒战、高热,无明显胸痛,偶有咳嗽、咳痰。行超声心动图检查提示肺动脉内可见赘生物,此时最可能
《开发区区域环境影响评价技术导则》中“对开发区规划的环境可行性进行综合论证”的内容不包括()。
记账人员记账时将某笔经济业务漏记,期末进行试算平衡时检查不出这一错误,故要用其他方法检查。()
在招股说明书中,发行人应披露有关股本的情况,主要包括()
简述语文课程资源的内容。
甲、乙两杯奶茶分别重300克和120克,甲中含奶茶粉120克,乙中含奶茶粉90克。从两杯中应各取出多少克才能兑成浓度为50%的奶茶140克?
如下关于开源操作系统的说法,正确的是()。
WhatcanbelearnedaboutYukioHatoyamafromthepassage?
最新回复
(
0
)