Question

设某算法计算时间表示为递推关系式T(n)＝T(n-1)+n(n小于O)及T(0)＝1，则该算法时间复杂度为 ( ) 。

A.O(lgn)
B.O(nlgn)
C.O(n)
D.O(n^2)

Answer 1

【答案】：D
本题考查算法设计基础知识。根据题目中给出递推关系：T(n)＝T(n-1)+n＝T(n-2)+n-1+n＝…＝T(0)+1+2+…+n-1+n＝1+n(n+1)/2