首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
最全题库
2022-08-02
72
问题
某个算法的时间复杂度递归式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.急性感染症状
随机试题
Theword"girl"originallymeant"youngpersonofeithersex",butnowitmeans
Sports,inshort,areakindofeducation,whichcanteachimportantlifeskills
[originaltext]W:Youarelateagain!We’vebeenexpectingyouforanhour.For
孙武是春秋末期(thelateSpringandAutumnPeriod)杰出的军事家(strategist)。他所著的《孙子兵法》(Sun
考忠有两个因素的多因素APT模型,股票A的期望收益率是18%,对困素1的贝塔值是
患者,女,30岁。带下量多,色黄而稠,少腹隐痛,阴部瘙痒,舌苔黄腻,脉滑数。不使
气温是指空气的温度,通常用离地面()m高的位置上测得的空气温度来代表。A.1
市场有效性的外生性将驱动市场价格趋于一致,同种商品在不同市场将遵循一价原则。(
下列关于商业银行关系人的表述中,错误的是()。A.商业银行不得向关系人发放信用
知识点:宫内节育器 女,25岁。结婚2个月,月经规律B超检查见宫内一强回声光
最新回复
(
0
)