首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
最全题库
2022-08-02
50
问题
某个算法的时间复杂度递归式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处理与销售相关的所有细节,仅需要发送一个包含销售量、价格和时间的
随机试题
MorethanayearlaterhearrivedbackinAmerica______.A、ill,tiredandunhappy
初中数学《解二元一次方程组》 一、考题回顾 题目来源:5月18日上午湖北
建筑耐火等级是指根据建筑中墙、柱、梁、楼板、吊顶等各类构件不同的耐火极限,对建筑
安全生产管理通常是指管理者对安全生产工作进行的决策、计划、组织、指挥、协调和控制
根据以上材料可以看出,机关工作人员()。 A.职业道德应该有明确的行为规范
小砌块墙体的搭砌长度不得少于块高的1/3,且不应少于多少?A.80mm B.
实行工程监理的过程中,()是工程监理的受托方。 A、监理单位 B、建设
单体蓄电池电压测量应每月至少1次,蓄电池内阻测试应每半年至少1次
A型行为特征不包括A.时间紧迫感 B.争强好胜 C.脾气急躁 D.对人有敌
对于超过一定规模的危险性较大的分部分项工程专项方案,应由()组织召开专家论
最新回复
(
0
)