将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

admin2023-02-06 69

问题将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

选项

答案因为基数排序所需的时间不仅与文件的大小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/tBwD777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

计算机408

学硕统考专业

小组教学是指把一个班暂时分成若干个小组，教师制定共同的学习任务，学生分组学习的班级教学形式。关于小组教学的优点，下列说法正确的有()。

教育功能是教育活动和教育系统对个人发展和社会发展产生的作用与影响。影响教育功能发挥的主要因素不包括()。

批复正文的开头部分，首先应当写出的是()。

赫尔巴特认为教学过程可分为()、联想、系统和方法四阶段。

保护学生安全不属于《中小学教师职业道德规范》的要求。()

下列有关生活常识的叙述，不正确的是：

实现领导决策的保证是

成人白细胞计数为【】

可引起杵状指(趾)的疾病是

肾脏疾病中出现血尿的最常见原因是

A．阴茎套B．宫内节育器C．复方短效口服避孕药D．绝育术E．安全期避孕生育2个以上的妇女避孕方法应选用

A．卡铂B．环磷酰胺C．氟尿嘧啶D．阿霉素E．长春新碱

(2018·山西)小学生在课外开展的航模小组、无线电小组、计算机小组属于()(常考)

李明倡导低碳出行，每天骑自行车上下班，如果他每小时的车速比原来快3千米，他上班的在途时间只需原来时间的；如果他每小时的车速比原来慢3千米，那么他上班的在途时间就比原来的时间多：

()是公共部门在履行社会经济管理职能过程中，提供特别行为或服务而收取的补偿费用。