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