首页
登录
从业资格
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
最全题库
2022-08-02
76
问题
已知算法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.归
随机试题
WriteonANSWERSHEETTWOanoteofabout50-60wordsbasedonthefollowing
WhichofthefollowingadverbscanNOTbeusedtocomplete"______everybodyca
TheCaseAgainstRetirementAh,retirement!Beforet
下列关于企业战略制定的表述,正确的是()。A.企业的使命是在企业战略目标的
A.频率较低的 B.音调较高的 C.能量较小的 D.响度较小的
治疗疫毒痢应为下列哪种方法为主?( )A.清热利湿和胃 B.清热凉血解毒
A.10日内 B.5日内 C.20日内 D.7日内 E.15日内负责组织
下列哪项符合单纯性代谢性酸中毒A.低PaCO,低HCOB.高PaCO,高HCOC
关于冻疮的药物治疗对局部发生水疱和糜烂者可涂敷A.10%氧化锌软膏 B.10%
口服药物治疗甲亢的适应证是() A.超过30岁 B.病情轻,甲状腺较小者
最新回复
(
0
)