首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知算法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
47
问题
已知算法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
软件设计师上午基础知识考试
软考中级
相关试题推荐
WindowsServer2003采用IPSec进行保密通信,如果密钥交换采用“主密钥完全向前保密(PFS)”,则“身份验证和生成密钥间隔”默认值为480分钟和(33)个会话。
DHCP客户端不能从DHCP服务器获得__________。(2010年上半年试题)
设有两个子网202.118.133.0/24和202.118.130.0/24,如果进行路由汇聚,得到的网络地址是(46)。
DNS正向搜索区的功能是将域名解析为IP地址,WindOWSXP系统中用于测试该功能的命令是__________。(2012年下半年试题)
划分VLAN的方法有多种,这些方法中不包括(56)。
以太网协议中使用了二进制指数后退算法,这个算法的特点是(62)。
计算机指令一股包括操作码和地址码两部分,为分析执行一条指令,其______。
根据上述说明,请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。对于表2-1、表2-2所示的“职员”和“部门”关系,请指出下列各行是否可以插入“职员”关系,为什么?
国际标准MPEG—Ⅱ采用了分层的编码体系,提供了4种技术,它们是(46)。数字音频采样和量化过程所用的主要硬件是:(47)。AC-3数字音频编码提供了5个声道的频率范围是:(48)。要把一台普通的计算机变成多媒体计算机要解决的关键技术是:(
随机试题
正常一般情况下,主动脉弓的分支有
边缘封闭区副承托区
建设工程设计合同的主体可以是( )。
由于承包人责任引起的暂停施工,如承包人在收到监理人暂停工指示后()天内不认真采取有效的复工措施,造成工期延误,可视为承包人违约,由承包人承担违约责任。
下列关于金融业营业税计税营业额的确定方法中,符合营业税法律制度规定的是()。
期权合约必须履行的时间是()。
2010年2月12日,中国银行业监督管理委员会颁布了()。
人民币超额准备金率等于()。
物质帮助权只能是公民在失去劳动能力时获得。()
下列推断不正确的是()。
最新回复
(
0
)