首页
登录
从业资格
某个算法的时间复杂度递归式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/2425012.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
妊娠合并心脏病开始使用抗生素预防感染合适时间是A.无论什么时候使用均可 B.产
紫外线消毒空气时,若每10m安装30W紫外线灯管1支,则有效距离和消毒时间分别为
胎心监护发现胎心率减速与宫缩关系不恒定。持续时间长短不一,出现时下降迅速,幅度大
胎心监护发现胎心减慢开始于宫缩高峰后。下降缓慢,持续时间长。恢复亦缓慢,表示A.
生理性黄疸消退的时间为婴儿出生后 A.2~3天 B.3~7天 C.7
生理性黄疸开始出现的时间为婴儿出生后 A.2~3天 B.3~7天 C
两次月经第一天的间隔时间为A.月经期B.增生期C.分泌期D.月经前期E.月经周期
产后子宫进入盆腔,在腹部摸不到宫底的时间为 A.产后10天 B.产后3周
正常产褥期的时间为 A.产后10天 B.产后3周 C.产后3~4周
使用抗生素的时间不当的是A.预防性用药在手术后1~3小时使用 B.急性感染症状
随机试题
[audioFiles]audio_eham_j07_001(20082)[/audioFiles]A、Sittingonherdesk.B、Sitt
DeutscheBahnAGDeutscheBahn(DB)AGwasfounded
[originaltext]M:Itdoesn’tmakeanysensetogohomeforspringvacationnow.
A.2~7岁 B.1~5岁 C.2岁内婴幼儿 D.6个月~2岁 E.5~
下列哪种病人临床上不出现发绀()A.严重贫血 B.急性肺炎 C.自发性
下列关于市值回报增长比(PEG)的说法,正确的有()。 Ⅰ.市值回报增长b匕
下列哪项不属于镇心安神药组A:龟甲,鳖甲B:龙齿,琥珀C:龙骨,珍珠母D:
环糊精包合物的包合过程是A.化学过程B.物理过程C.扩散过程D.溶出过程E.交换
患儿,女,6岁。全身大面积开水烫伤送来急诊。四肢、后背大面积烫伤,创面红肿、大水
下列标准成本差异中,通常不由生产部门承担主要责任的有( )。A.直接材料价格差异
最新回复
(
0
)