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

最全题库2022-08-02 48

问题某个算法的时间复杂度递归式 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://www.tihaiku.com/congyezige/2408345.html

中级软件设计师

相关试题推荐

随机试题

最新回复(0)