某个算法时间复杂度递归式 T(n)=T(n-1)+n ，其中 n 为问题规模，则该算法渐进时间复杂度为（ ），若问题规模增加了16倍，则运行时间增加（ 此空作答）倍。
- 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 倍。
