某个算法的时间复杂度递归式T（n）=T（n-1）+n，其中n为问题的规模，则该算

最全题库2022-08-02 33

问题某个算法的时间复杂度递归式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

中级软件设计师

相关试题推荐

随机试题

最新回复(0)