首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
最全题库
2022-08-02
90
问题
某个算法的时间复杂度递归式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.急性感染症状
随机试题
•Readtheadvertisementandthememobelow.•Completetheformontheopposite
Helena:Oh,welcome,comein,please.Jack:______Andhere’sasmallgift.Letm
ReducingWasteFoodExpertsinthefoodindustry
图 北方某地区粮食作物产量统计图表(万斤/单位) 秋粮作物中产量最大的是产
某公用事业公司的股票,由于每年业绩相差不多,因此每年的分红都保持相当的水平,每股
Thechangeinthatvillagewasmiraculou
战国宋玉《对楚王问》,很早就点出“阳春白雪”与“下里巴人”之间的差别,然而在我们
某女,35岁,久居湿热环境,患风湿热痹与脚气浮肿,宜选用的药物是A.萆薢 B.
根据《建设工程质量管理条例》的规定,建设单位有()行为的,责令改正,处20
一项病例对照研究,探讨妊娠期母亲的各种暴露史与新生儿先天性畸形之间的联系。在调查
最新回复
(
0
)