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

时间:2022-05-19 17:19:08
● 设某算法的计算时间表示为递推关系式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


由递推关系式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


很有意思的一道题目。。