首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
最全题库
2022-08-02
47
问题
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(请作答此空),若问题的规模增加了16倍,则运行时间增加( )倍。A.O(n)B.O(nlgn)C.O(n2)D.O(n2lgn)
选项
A.O(n)
B.O(nlgn)
C.O(n2)
D.O(n2lgn)
答案
C
解析
对于递归式,假设T(1)=1,则:T(n)=T(n-1)+n=T(n-2)+n-1+n=T(n-3)+n-2+n-1+n=1+2+…+n-1+n=n(n+1)/2可见,时间复杂度为O(n2)。若问题的规模增加了16倍,则运行时间增加了162=256倍。
转载请注明原文地址:https://tihaiku.com/congyezige/2407857.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户服务要
当用户需求不清晰,需求经常发生变化,系统规模不太大时,最适宜采用软件开发方法是(
有关评估系统效率质量特性,以下论述正确的是( )。A.响应时间越长,系统执行效
软件生命周期中持续时间最长的是( )阶段。A.需求分析 B.程序编码 C.
加密和解密是明文和密文之间的可逆转换,( )不属于加密算法。A.RSA B.
以下控制流图的圈复杂度V(g)为( )。 A.4 B.6 C.8 D.
软件复杂性是指理解和处理软件的难易程度。其度量参数不包括()。A.规模 B.类
在软件开发过程中,详细设计的内容不包括()设计A.软件体系结构 B.算法
某系统中,模块A处理与销售相关的所有细节,仅需要发送一个包含销售量、价格和时间的
随机试题
TheplaywrightDavidHenryHwanghasbeeninhighdemandinrecentyears—not
私家车privatecar
英国是世界上最早建立存款保险制度的国家。
独语多由上述何种因素引起?( )A.心阴大伤 B.心气不足 C.热扰心神
浮船坞是一种修造舰船的大型装备,外观就像是把一个干船坞从岸边“刨”了出来。主结构
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性: A.如
被称之为“中国科学史上的里程碑”的著作是()。A.北宋李诫编写的《营造法式》
阅读下列材料: 材料、 今天,全国政协十届一次会议在京开幕.当人们看到一位
下列建设工程进度计划编制工作中,属于绘制网络图阶段工作内容的是( )。A.确定进
对于采用新设法人进行筹资的项目,在确定项目资本金结构时,应通过协商确定投资各方的
最新回复
(
0
)