首页
登录
从业资格
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
最全题库
2022-08-02
68
问题
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,则该算法的时间复杂度为( )。另已知算法B的运行时间函数为T(n)=XT(n/4)+n2,其中n表示问题的规模。对充分大的n,若要算法B比算法A快,则X的最大值为( )。问题1选项A.Θ(n)B.Θ(nlgn)C.Θ(n2)D.Θ(n3)问题2选项A.15B.17C.63D.65
选项
答案
DC
解析
本题需要用到特定形式的递归式分析法:
在本题中,a=8,b=2,故符合(1)的情况。时间复杂度为:Θ(n3)。第一空选择D选项。对于算法B的运行时间函数为T(n)=XT(n/4)+n2,同样带入分析,a=X,b=4,f(n)=n2。若要算法B与算法A一样快,即时间复杂度一致,则满足条件(1),且
,此时带入算法B的变量,即log4X=3,即X=64,现在要求算法B更快,即时间复杂度更小,所以X应该小于64,可取的最大值为63。第二空选择C选项。
转载请注明原文地址:https://tihaiku.com/congyezige/2410383.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
IT资源管理能否满足要求主要取决于IT基础架构的配置及运行情况的信息,配置管理就
IT资源管理能否满足要求主要取决于IT基础架构的配置及运行情况的信息,配置管理就
系统运行管理制度是系统管理的一个重要内容,它是确保系统按预定目标运行并充分发挥其
要进行企业的软件资源管理,就要先识别出企业中运行的()和文档,将其归类汇总、登
系统日常操作日志应该为关键性的运作提供审核追踪记录,并保存合理时间段。利用日志工
DES是一种()加密算法,其密钥长度为56位,3DES是基于DES的加密方式,
以下①~⑥中属于项目管理知识领域的是()。①项目范围管理②项目时间管理③项目成
软件开发过程中,常采用甘特(Gantt)图描述进度安排。甘特图以()。A.时间
()要求关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。A.1NF
()算法是不稳定的排序算法。A.简单选择 B.冒泡 C.直接插入 D.归
随机试题
DiseaseandHistoryP1:Epidemiologyisthestudyandanalysisofthepatterns,
TheMarriageContractAmarriageisacontract.You
Foraboutthreecenturieswehavebeendoingscience,tryingscienceout,us
The“threearmsofgovernment”ofAustral
介于舞蹈样运动和手足徐动之间的不随意运动协调障碍称为A.肌阵挛 B.手足徐动
条件致病菌致病的主要原因是()A.致病菌在一定条件下引起 B.机体免疫亢进
简述现代企业人力资源管理各个历史发展阶段的特点。
通过经济手段征税,把碳排放作为一项成本,计入工业生产和个人生活中,在经济学上顺
不属于G-蛋白偶联受体的是()A.M受体 B.多巴胺受体 C.a-肾上
施工单位编制竣工图的一般修改方法包括()。A.杠改法 B.重新绘制 C.套改
最新回复
(
0
)