已知算法A的运行时间函数为T(n)=8T(n／2)+n2，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最

admin2019-07-12 31

问题已知算法A的运行时间函数为T(n)=8T(n／2)+n²，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n²，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为__________(63)。
(63)

选项 A、15
B、17
C、63
D、65

答案C

解析本题考查算法分析的基础知识。
根据主方法，先计算算法A的时间复杂度，a=8，b=2，log_ba=log₂8=3，而f(n)=n²，因此时间复杂度为Θ(n³)。然后计算算法B的时间复杂度，a=X,b=4，log_ba=log₄X，而f(n)=n²，若算法B和算法A的效率一样，则X应该为64(log₄64=3)，而现在要使得B比A快，则X应该比64小，因此最大的整数应该为63。

转载请注明原文地址:https://jikaoti.com/ti/R5G7FFFM

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

已知算法A的运行时间函数为T(n)=8T(n／2)+n2，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最

软件设计师上午基础知识考试

软考中级

在IP协议的数据报报头中，与分片和重新组装无关的字段有__________。

将一条指令的执行过程分解为取指、分析和执行三步，按照流水方式执行，若取指时间t取指=4△t、分析时间t分析=2△t、执行时间t执行=3At，则执行完100条指令，需要的时间为________△t。

Linux系统中，DHCP服务的主配置文件是(1)，保存客户端租约信息的文件是(2)。(2)

指令系统中采用不同寻址方式的目的是______。

在Windows98操作系统中，TCP／IP是以__________方式实现的。

划分VLAN的方法有多种，这些方法中不包括(56)。

DNS服务器中提供了多种资源记录，其中____________定义了区域的授权服务器。

以太网协议中使用了二进制指数后退算法，这个算法的特点是(62)。

多媒体电子出版物创作的主要过程可分为(62)。基于内容检索的体系结构可分为两个子系统：(63)。

男，6个月，出生不久哭闹时右阴囊有一包块，平卧安静时包块明显缩小或消失。2小时前因哭闹包块掉出，伴呕奶、不停哭闹、精神萎靡，右阴囊可见一似梨状包块。本例最有效的治疗措施是

护士角色是指护士在社会中特定的

人民民主专政的主要内容和特点。

当代中国坚持“发展是硬道理”的本质要求就是坚持()。

下列关于中国的航天航空发展说法正确的是：

下列不是货币政策最终目标的是()。

在树形结构中，树根结点没有

VBA语句“DimNewArray(10)asInteger”的含义是()。

Inadditiontoredistributingincomes,inflationmayaffectthetotalrealincomeandproductionofthecommunity.Anincreasei