首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
最全题库
2022-08-02
71
问题
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为 ( ) ,若问题的规模增加了16倍,则运行时间增加 (请作答此空) 倍。A.16B.64C.256D.1024
选项
A.16
B.64
C.256
D.1024
答案
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/2425011.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
紫外线消毒空气时,若每10m安装30W紫外线灯管1支,则有效距离和消毒时间分别为
下列不符合臭氧消毒的说法是A.消毒时间应≥30分钟 B.臭氧发生器将空气中的氧
紫外线消毒空气时,若每10m安装30W紫外线灯管1支,则有效距离和消毒时间分别为
胎心监护发现胎心率减速与宫缩关系不恒定。持续时间长短不一,出现时下降迅速,幅度大
胎心监护发现胎心减慢开始于宫缩高峰后。下降缓慢,持续时间长。恢复亦缓慢,表示A.
生理性黄疸消退的时间为婴儿出生后 A.2~3天 B.3~7天 C.7
脐带脱落的时间为婴儿出生后 A.2~3天 B.3~7天 C.7~10
正常产褥期的时间为 A.产后10天 B.产后3周 C.产后3~4周
针对组织内部的具体问题,在较小范围内和较短时间内实施的计划属于A.指令性计划
医院感染暴发是指A.医院科室的住院病人中,在短时间内突然发生许多医院感染病例的现
随机试题
Whatpercentageoftheworld’sknownpetroleumreservesdoesKuwaithave?[origi
PASSAGETWO[br]WhoseopinioninthepassageismostsimilartoKimOser’s?Chri
Whensomeonecommitsacriminalact,wealwayshopethepunishmentwillmatc
"He’snomoreabletoreadJapanesethanIam."ThesentencemeansthatA、neither
ACMEAtlanticisawell-knownandrespectedtradingcompany.Wehandlewith
以下药材粉末镜检可见草酸钙簇晶的是A.白芍 B.半夏 C.甘草 D.天麻
D
A.IgA B.SIgA C.IgG D.IgM E.IgE牙周病免疫中
急性上消化道大量出血是指A.24小时内失血量至少超过1000ml或循环血量的20
可用于治疗头痛、牙痛及鼻渊的药物是A.细辛 B.桂枝 C.辛夷 D.
最新回复
(
0
)