首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
最全题库
2022-08-02
79
问题
某个算法的时间复杂度递归式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处理与销售相关的所有细节,仅需要发送一个包含销售量、价格和时间的
随机试题
Ateamofinternationalresearchershasfoundnewevidencethatanendangere
Whatwillthespireonthetopofthenewbuildingsuggest?[originaltext]W
[originaltext]Tobesuccessfulinajobinterview,youshoulddemonstratec
Thelocaleducationauthoritycompiledalistof"potentialsecurityproblem
按照软件配罝管理的基本指导思想,受控制的对象应是()。A.软件元素 B.
案例: 下面是某化学教师关于“分子”的教学片段 环节一:情境创设,引入新课。
244)当电压互感器二次星形侧发生相间短路时,在熔丝或自动开关未断开以前,电压回
电影院、KTV、溜冰场均设置在多层商店建筑内,则该疏散楼梯间按()的要求进行设
为避免产生“阿司匹林抵抗”,应用阿司匹林时应注意A.规范应用阿司匹林,75~10
无效合同包括主体不合格、内容不合格和( )不合格。A.程序 B.形式 C.
最新回复
(
0
)