论坛 › C\C++交流 › 问题

aaron.yang 发表于 2020-9-23 21:51:01

问题

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

这道题咋做？？？？？

昨非 发表于 2020-9-23 21:56:26

1+1+2+3+4+....+n = n(n+1)/2+1
所以答案是O（n^2）

乐乐学编程 发表于 2020-9-23 22:00:21

昨非 发表于 2020-9-23 21:56
1+1+2+3+4+....+n = n(n+1)/2+1
所以答案是O（n^2）

我看不懂，回复得个荣誉

aaron.yang 发表于 2020-9-24 11:56:57

昨非 发表于 2020-9-23 21:56
1+1+2+3+4+....+n = n(n+1)/2+1
所以答案是O（n^2）

那为何1+1+2+3+4+....+n = n(n+1)/2+1=O(n^2)

昨非 发表于 2020-9-24 12:03:15

aaron.yang 发表于 2020-9-24 11:56
那为何1+1+2+3+4+....+n = n(n+1)/2+1=O(n^2)

时间复杂度只看最高次项，系数和低次项都忽略的

风过无痕1989 发表于 2020-9-24 22:43:13

算法，我还没学，来学习学习

查看完整版本: 问题