下面程序段的时间复杂度是( )
i=s=0;
while(s<n){
i++;s+=i;
}
A. O(sqrt(n)) B. O(n2) C. O(log2n) D. O(n3)
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
登录后提交答案