首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n/4)+n2,其中n表示问题的规模。对充分大的n,若要算法B比算法A快,则X的最
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n/4)+n2,其中n表示问题的规模。对充分大的n,若要算法B比算法A快,则X的最
admin
2019-07-12
41
问题
已知算法A的运行时间函数为T(n)=8T(n/2)+n
2
,其中n表示问题的规模,则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n/4)+n
2
,其中n表示问题的规模。对充分大的n,若要算法B比算法A快,则X的最大值为__________(63)。
(63)
选项
A、15
B、17
C、63
D、65
答案
C
解析
本题考查算法分析的基础知识。
根据主方法,先计算算法A的时间复杂度,a=8,b=2,log
b
a=log
2
8=3,而f(n)=n
2
,因此时间复杂度为Θ(n
3
)。然后计算算法B的时间复杂度,a=X,b=4,log
b
a=log
4
X,而f(n)=n
2
,若算法B和算法A的效率一样,则X应该为64(log
4
64=3),而现在要使得B比A快,则X应该比64小,因此最大的整数应该为63。
转载请注明原文地址:https://kaotiyun.com/show/46CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
Telnet采用客户端/服务器工作方式,采用______格式实现客户端和服务器的数据传输。
在某路由器上查看路由信息,结果如下所示。其中标志“S”表明这条路由是(28)。
WindowsServer2003采用IPSec进行保密通信,如果密钥交换采用“主密钥完全向前保密(PFS)”,则“身份验证和生成密钥间隔”默认值为480分钟和(33)个会话。
设有两个子网202.118.133.0/24和202.118.130.0/24,如果进行路由汇聚,得到的网络地址是(46)。
以太网的最大帧长为1518字节,每个数据帧前面有8个字节的前导字段,帧间隔为9.6us。快速以太网100BASE—T发送两帧之间的最大间隔时间约为(60)________________us。
路由器则的连接和地址分配如下图所示,如果在R1上安装OSPF协议,运行下列命令:router ospf 100,则配置SO和EO端口的命令是(53)。
访问控制列表(ACL)配置如下,如果来自因特网的HTTP报文的目标地址是162.15.10.10,经过这个ACL过滤后会出现什么情况?(58)
根据E-R图中给出的词汇,按照“关系模式名(属性,属性,…)”的格式,将此E-R图转换为4个关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。创建Customers表时,cid使用INTEGER数据类型,cnarne使用
国际标准MPEG—Ⅱ采用了分层的编码体系,提供了4种技术,它们是(46)。数字音频采样和量化过程所用的主要硬件是:(47)。AC-3数字音频编码提供了5个声道的频率范围是:(48)。要把一台普通的计算机变成多媒体计算机要解决的关键技术是:(
随机试题
肾性高血压患者的首选药物是
钩蚴培养法的最适温度为
下列属于无阈值效应的是
城镇土地利用现状与潜力调查的步骤主要包括()。
声环境影响评价范围在对于以固定声源为主的建设项目在满足一级评价的要求时,一般以建设项目边界向外()m为评价范围。
发生粉尘爆炸的首要条件是()。
吊顶工程饰面板安装的主要安装方法有()。
与其他股利分配政策相比,企业选择剩余股利政策,通常比较有利于()。
发生在商品生产者或持有者与用户或消费者之间的物流活动是()。
根据以下资料,回答以下问题2013年,我国境内民用航空(颁证)机场共有193个(不含香港、澳门和台湾,下同),其中定期航班通航机场190个,定期航班通航城市188个。2013年年内定期航班新通航的城市有内蒙古阿拉善左旗、内蒙古阿拉善右旗、内蒙古
最新回复
(
0
)