算法的时间复杂度为 (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).
得出:
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)呀
凭直觉是每次总数减少一个,但是要有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).
得出:
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)呀
凭直觉是每次总数减少一个,但是要有O(n)的开销,总共n次,所以是O(n×n)呀
#8
LZ选择是对的,这个递归的复杂度应该是O(n)!
#9
不好意思,犯了和LZ一样的错误,没有仔细看题,题目说的是“某算法的计算时间表示为递推关系式”,
说的就是时间了,而不是这个递归本身的复杂度!
说的就是时间了,而不是这个递归本身的复杂度!
#10
很有意思的一道题目。。