首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
最全题库
2022-08-02
85
问题
某个算法的时间复杂度递归式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处理与销售相关的所有细节,仅需要发送一个包含销售量、价格和时间的
随机试题
Roy:______?Earl:Notreally,IthinkIhavebrokenmyknees.Roy:Oh,myGod
Anumberoffactorsrelatedtothevoicerevealthepersonalityofthespeak
甲状腺髓样癌是一种()。A.交界性肿瘤 B.错构瘤 C.未分化癌 D.迷
模块A、B和C包含相同的5个语句,这些语句之间没有联系,为了避免重复,把这5个
董事会:我们不应该再在甲项目上浪费资金了。实际上,此项目开始后,公司的市场占有率
2013年6月,社会消费品零售总额18827亿元,同比增长13.3%。其中,限额
X市的有线电视付费频道的用户数量比Y市要多,因此X市的市民比Y市市民更加了解国际
溶血性贫血红细胞中出现的异常结构〒包括 A.嗜酸性点彩B.Howell-J
某公司2016年净利润为750万元,全年发生利息费用为200万元,其中 150
(2016年真题)某制氧站经过招投标,由具有安装资质的公司承担全部机电安装工程和
最新回复
(
0
)