下面程序段的时间复杂度是( )
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 : 感谢提醒,已修正
这题出错了吧
用户登录可进行刷题及查看答案
登录后提交答案