求解一个算法的时间复杂度！！！！！！！！！

● 设某算法的计算时间表示为递推关系式T(n)= T(n-1) + n (n>0) 及T(0)=1，则该
算法的时间复杂度为（65）。
A. O(lgn) B.O(nlgn) C.O(n) D.O(n^2)

我怎么看都是C，但参考答案就是D。想不明白，参考答案也会错吧？？高手帮忙分析下！！！！！！！

10 个解决方案

#1

由递推关系式T(n)=T(n-1)+n(n>0)及T(0)=1，
得出：
T(n) = T(n-1) + n,
T(n) = (T(n-2) + (n-1)) + n,
T(n) = (T(n-3) + (n-2)) + (n-1) + n,
...
T(n) = T(0) + 1 + 2 + 3 + ... + n,
T(n) = (n^2 + n + 2) / 2,
所以时间复杂度为O(n^2).

#2

ls正解！

#3

ls牛

#4

顶一楼

#5

展开，直觉上这种式子想看成O(n)都难

#6

这不很像冒泡的时间复杂度么

#7

直接用数学归纳法得D
凭直觉是每次总数减少一个，但是要有O(n)的开销，总共n次，所以是O(n×n）呀

#8

LZ选择是对的，这个递归的复杂度应该是O(n)!

#9

不好意思，犯了和LZ一样的错误，没有仔细看题，题目说的是“某算法的计算时间表示为递推关系式”，
说的就是时间了，而不是这个递归本身的复杂度！

#10

很有意思的一道题目。。

#1

#2