首页
登录
从业资格
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
最全题库
2022-08-02
71
问题
已知算法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.归
随机试题
[originaltext]Areyousometimesalittletiredandsleepyintheearlyafte
机械保养不包括()。A.二级保养 B.三级保养 C.每班保养 D.初级保
总承包单位依法将建设工程分包给其他单位施工,若分包工程出现质量问题时,应当由(
胎儿宫内生长受限指孕37周后,胎儿出生体重低于同孕龄正常体重的A、一个标准差
教师是一种从事专门职业活动的专业人员,其资格的特定要求有( )。A.要有较好的
与国内建筑安装工程费构成相比,国外建筑安装工程费用的材料费用构成的区别主要表现为
该地区人口出生率最高是: A1965年 B1975年 C1980年
各种运输方式内外部的各个方面的构成和联系,就是( )。 A.运输系统
教育目的就是教育方针。
2022年6月29日,由中华全国新闻工作者协会主办的2022年“一带一路”记者组
最新回复
(
0
)