首页 > 试题广场 >

下列程序段的时间复杂度为（ ）。

[单选题]
下列程序段的时间复杂度为（） 
int i = 0, s = 0;
while (s < n) {
    s += i;
    i++;
}
 
  • O(n^(1/2))
  • O(n^(1/3))
  • O(n)
  • O(n^2)
查看正确选项
添加回答
sgbs头像 sgbs
哪位大神可以解析下呢？
发表于 2017-07-13 08:20:21 回复(0)
菠萝X菠萝头像 菠萝X菠萝
每次循环的增量为i，且i也是累加，即：
1+2+……+x <= n,x次循环满足条件，x即为复杂度，计算可以得到
(1+x)/2*x <=n,
x为O(n^(1/2))
发表于 2017-07-13 15:45:27 回复(0)
Pinghe头像 Pinghe
  • 显然n表示规模，s=s+i和i++是基本操作
  • i与s都是从0开始，假设循环执行了m次结束，则有
    • s1 = 1
    • s2 = 1+2 = 3
    • s3 = 1+2+3 = 6
    • ...
    • s_m = 1+2+3+...+m = (等差数列求和)
  • 由以上公式可以得到等式
    • ((1+m)m)/2 + K = n（K为起修正作用的常数）
    • 由求根公式解出 图片说明
    • 即图片说明
    • 由此可知图片说明
发表于 2020-04-01 01:15:26 回复(1)
zsxf头像 zsxf
s的取值为数列：0,1,3,6,10，……a(k)（<n的最大值）
易求通项式：a(i) = i(i-1)/2
有a(k) = k(k-1)/2 <n
求得k<=(2n+1/4)^(1/2)+1/2
k即为循环次数，所以时间复杂度为O(n^(1/2))
发表于 2017-07-24 19:00:06 回复(0)
xhnxiaotu头像 xhnxiaotu
不会
发表于 2019-03-19 22:03:24 回复(0)
喜欢拱白菜的安哥拉兔在人才库头像 喜欢拱白菜的安哥拉兔在人才库
编辑于 2024-03-31 11:26:00 回复(0)
淇神头像 淇神
题咋出不来啊
发表于 2020-04-22 19:21:35 回复(0)
机智的阿库娅头像 机智的阿库娅
当n变得越来越大时，公式中的低阶，常量，系数三部分影响不了其增长趋势，可以直接忽略他们，只记录一个最大的量级就可以了。因此我们在计算时间复杂度时，只需关注循环次数最多的那段代码即可。
比如本题中，
1+2+……+y <= n，y为复杂度
y^2+y-2n=0
计算可得：y = (-1+(1+8n)^(1/2))/2
忽略一些常数，y = n^(1/2)
即复杂度O(n^(1/2))
发表于 2020-12-04 11:47:55 回复(0)
袁家小少爷头像 袁家小少爷
这个就是类似于当时高斯算法那种形式，求和1+2+3+。。。100，就是高中学习的等差数列求和公式~
发表于 2019-10-23 15:01:15 回复(0)
今天西山居发面试通知了吗？头像 今天西山居发面试通知了吗？
如果i一直为1不变, 循环次数为n, 因为i每次都自增1,所以循环次数小于n,CD排除
0+1+2+3+4·····>=n,得出循环次数约为n^1/2, 选A
发表于 2017-07-13 10:23:23 回复(0)
提交观点

问题信息

复杂度
上传者：阿奻_
难度：
10条回答 14199浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号