下面程序段的时间复杂度是( )
i=s=0;
while(s<n){
i++;s+=i;
}
A. O(sqrt(n)) B. O(n2) C. O(log2n) D. O(n3)
下面程序段的时间复杂度是O(√n)。具体解释如下：
程序段中有一个while循环，循环条件是s<n，其中s的初始值为0，i的初始值为1。在循环体内，每次迭代s增加i，i自增1。循环继续直到s大于或等于n。
s<n
s
i
n
为了确定循环的次数，我们需要找到s与i的关系。在第k次迭代时，s的值是1 + 2 +... + k = k*(k+1)/2。当s达到n时，循环终止，即k*(k+1)/2 >= n。解这个不等式，我们可以得到k的最小值是√(2n)。
k
1 + 2 +... + k = k*(k+1)/2
k*(k+1)/2 >= n
√(2n)
由于i的值在每次迭代中增加1，i的最大值也就是循环的次数。因此，循环的次数是O(√n)。
综上所述，该程序段的时间复杂度是O(√n)。所以，答案是选项A。
A
根号n
时间复杂度为 O(sqrt(n))，因为 s 是 i 的前缀和，每次循环 i 和 s 都会增加 1，因此最多需要循环 sqrt(n) 次。
答案应该是根号n吧（
admin 回复 lamda： 感谢提醒，已修正
admin 回复 j0___yo： 已修正
答案错了，应该是根号n
admin 回复 knvgfjuce： 感谢提醒，已修正
答案要是错了就赶紧修正啊
admin 回复 碎钻： 已修正
答案错了 应该是sqrt（n），2017统考真题有类似题，i自增1。s=0+1+2+3+...+i=（1+i）*i/2
admin 回复 2951136820： 感谢提醒，已修正
lichuang 回复 2951136820： 大佬 膜拜
O(sqrt(n))
我也觉得是O根号n啊
不应该是O（sqrt（n））吗
C
不应该是n的1/2次方吗
i=0,s=0
i=1,s=1
i=2,s=3
…… i(i+1)/2<n
所以应该是O(sqrt(n))
admin 回复 范闲： 感谢提醒，已修正
admin 回复 pangpang： 是的，已修正
答案错了吧不应该是 (√n) 吗
admin 回复 Strive： 已修正
应该是根号n
admin 回复 我的火舞： 是的，已修正
这个题目出错了吧？假设算法执行的次数为k，那么满足条件k(k+1)/2 < n，即k^2<2n，那么就有k<2n开根号(根号不知道怎么写，将就着看)吧。这道题的答案给错了吧？
mrshisan 回复 Bratislava ： 你说的题号是多少，P1009的是O(n)
admin 回复 Bratislava ： 感谢提醒，已修正
这题出错了吧
用户登录可进行刷题及查看答案
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案