Question

设某算法的计算时间表示位递推关系式T(n)=T(n-1)+n(n位正整数)及T(0)=1,则该算法的时间复杂度为

Answer 1

T(n)
=T(n-1)+n
=T(n-2)+(n-1)+n
=T(n-3)+(n-2)+(n-1)+n
...
=T(0)+1+2+...+(n-2)+(n-1)+n
=1+1+2+...+(n-2)+(n-1)+n
=1+(n+1)*n/2
所以为 O(n²)，选D。