首页
登录
从业资格
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,
最全题库
2022-08-02
93
问题
已知算法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.归
随机试题
FamousChristmasPlacesTherearemany【T1】______trad
Whyitisveryhardtogetachocolateorfacecreamoutofitsbox?[br]Theau
Whenitstartedtosnow,weturnedroundand______thehotel.A、gotbyB、searched
Moneyseemscutanddried—youcanrepresentitwithnumbersand【C1】______po
在防火的基本方法中,静电消除设备、接地避雷、设置火星熄灭装置等方法属于()
乙公司明知甲公司经营部部长被取消了对外签订合同的授权,还继续与其签订设备采购合同
维生素D缺乏性佝偻病的预防工作下列哪种是错误的A.母乳喂养及时添加辅食 B.孕
蛋白质和热能缺乏引起的营养不良,临床表现有消瘦型和( )。A.水肿型 B
C注意到各项分母是一个以2为公比的等比数列,故待填项分母是32;每一项的分子=分母-1=31,选C。
2007年7月,中国证监会制定了(),自2008年8月4日起施行。A:《上市公司
最新回复
(
0
)