单选题
某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为 （ ） ，若问题的规模增加了16倍，则运行时间增加 （请作答此空） 倍。
A16
B64
C256
D1024
正确答案
答案解析
对于递归式，假设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倍。