首页
登录
从业资格
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
最全题库
2022-08-02
70
问题
已知算法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.归
随机试题
A.primeB.addedC.byD.reproductiveE.excessiveF.takeG.extends
Duringthe________oftherain,shereturnedhomeimmediately.A、spinB、flickC、lu
TheUnitedStateshasamajorproblemonitshands.Theonlywaytosolveit
为了保证报警阀组及其附件的安装质量和基本性能要求,报警阀组到场后,重点检查(验)
工程项目标准体系必须要参考工程项目的技术要求。
C
ADSL采用(上题)技术把PSTN线路划分为话音,上行下行三个独立的信道,同时提
A. B. C. D.
关于我国刑事起诉制度,下列哪些选项是正确的?A:实行公诉为主、自诉为辅的犯罪追诉
A.牢脉 B.革脉 C.紧脉 D.弦脉 E.伏脉脉来弦急中空,如按鼓皮,
最新回复
(
0
)