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

最全题库2022-08-02  58

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

最新回复(0)