首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知算法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
57
问题
已知算法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
软件设计师上午基础知识考试
软考中级
相关试题推荐
网络用户只能接收但不能发送Email,不可能的原因是______。
DHCP客户端不能从DHCP服务器获得__________。(2010年上半年试题)
WindowsServer2008R2默认状态下没有安装IIS服务,必须手动安装。配置下列()服务前需先安装IIS服务。
某主机接口的IP地址为192.16.7.131/26,则该IP地址所在网络的广播地址是(56)________________。
在Windows系统中监听发送给NT主机的陷入报文的程序是____________。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的值表示完成活动所需要的时间,则关键路径长度为__________。(2011年下半年试题)
阅读下列说明以及图4-4和图4-5,回答问题1、问题2和问题3,将解答填入答题纸的对应栏内。[说明]某电话公司决定开发一个管理所有客户信息的交互式网络系统。系统的功能如下。1.浏览客户信息:任何使用因特网的用户都可以浏览电话公司所有
数据流图4-1(住宅安全系统顶层图)中的A和B分别是什么?数据流图4-2(住宅安全系统第0层DFD图)中的数据存储“配置信息”会影响图中的哪些加工?
阅读以下说明和VisualBasic代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape,现有三个类CPoint、CLine和CCircle,它们都具有IShape界面。相应的类图关系如图7-1所示。
随机试题
定金的数额由当事人约定,但不得超过主合同标的额的
【背景资料】某安装公司总包氮氢压缩分厂全部机电安装工程,其中氮氢压缩机为多段活塞式,工作压力32MPa,电机与压缩机本体分两件进场,现场用齿式联轴器连接。压缩机系统的管道随机组订货,现场组装试验。开工前,安装公司决定压缩机系统的机械设
下列关于利润表的表述中,正确的有()。
下面所列举的迁移种类,确实存在的有()
某高校旅游管理专业学生组成甲、乙、丙、丁、戊5支队伍,暑期赴安徽、山西、湖北、四川、广西5省调研旅游景点管理现状。他们各自有一个特定的调研对象,分别是寺庙、道观、园林、海滩及村落,没有遗漏也没有重复。已知:(1)甲队比调研寺庙的队伍出发早,但比调
中国汽车工业协会发布的2009年4月份中国汽车产销数据显示,在其他国家汽车销售进一步疲软的情况下,国内乘用车销量却持续上升,当月销量已达83.1万辆,比3月份增长7.59%,同比增长37.37%。乘用车细分为基本型乘用车(轿车)、多功能车(MPV
简述南京国民政府时期法律制度的主要特点。
TheAmericanDream:MythorRealityI.Orignoftheterm:A.begantobewidelyusedin(1)______(1)______B.firstappearedina
【B1】【B15】
A、Inarestaurant.B、Inabookshop.C、Inarecordstore.D、Inatheater.C
最新回复
(
0
)