首页 > 试题广场 >

下面程序段的时间复杂度是（） i = k = 0; whil

[单选题]

下面程序段的时间复杂度是（）

i= k = 0;
while (k < n) {
    i++;
    k += i;
}

```
O(n)
```
```
O(n^(1/2))
```
```
O(n*i)
```
```
O(n+i)
```

查看正确选项

FIVEMOON

眼瞎了没看见大括号

发表于 2021-03-31 20:38:32 回复(0)

只想划水

算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。

如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。

该程序段是对一个等差数列求和，1+2+...+k=k*(k+1)/2，当k*(k+1)/2大于等于n时结束循环，根据时间复杂度此时f(n)=n^0.5。所以选B

发表于 2019-08-12 14:54:05 回复(2)

情愿啊

设q为一共要执行的次数

1 2 3 .... q

k=0+1; k=1+1 k=2+1 ... 1+2+3+...+q=n ==>q(1+q)/2=n==>q^2+q=2n

q^2+q+1/4=2n+1/4
(q+1/2)=(2n+1/4)^1/2
q=(2n+1/4)^1/2-1/2
所以 T(n)=O(n^1/2)

发表于 2019-10-10 15:24:47 回复(11)

jfjdjdjs

加是开根号，乘是取对数

发表于 2019-12-17 17:25:14 回复(2)

小haes

写写数字, 观察规律

i= 1, 2, 3, 4, 5, 6, 7, 8

k=1, 3, 6, 10, 15, 21, 28, 36

把k的数字两个两个一起看的话, 也就是(1,3), (6,10), (15, 21), (7,8), 求和后可以发现规律(1+3=4), (6+10=16), (15+21=36), (28+36=64)

也就是2^2, 4^2, 6^2, 8^2...偶数的平方

循环在x^2>=n时终止, 可得x等于根号n,也就是n^(1/2)

循环的次数是x/2, 时间复杂度为O((1/2)n^(1/2)), 一般而言时间复杂度认为常系数为1, 所以答案就是O(n^(1/2))

发表于 2019-11-26 09:04:22 回复(0)

有可能知道的人

假设循环次数为t，则循环条件满足(t+1)t/2<n。

可以得出，循环次数 $t = \frac{1}{2}(\sqrt{8n+1}-1)$ ，故算法执行次数 $T(n) = 2t = \sqrt{8n+1}-1$ 。又T(n) = O(f(n))，所以f(n) = n^0.5

发表于 2019-08-27 16:03:17 回复(3)

自定义丶

设循环次数为 q，时间复杂度为T(n), 也就是说，每次给定一个 n，的时候，根据 T(n)可以算出来时间复杂度， 那么时间复杂度就是 q，因为其他操作都是常数时间的操作，所以决定时间复杂度的就应该是循环次数。 观察代码， 在while循环中，每次 i 会自加1，循环次数 q 也得加 1 ，也就可以看成每次都是 s 每次都加上 q , 在 s > = n 的时候结束，那么 n 和 q 的关系就是 k=0 k + 1 + 2 + +3 + ... + q <= n(q 是循环的次数 )，那就是 0 + 1 + 2 + +3 + ... + q <= n ，根据等差公式算一算就可以得到 T( n ) = n^0.5了 ====================>主要就是借着 q 算出来 n 和 T( n) 的关系。

发表于 2019-09-06 15:33:00 回复(0)

张明俊

1 先求循环次数t

假设循环次数为t,则

K < n

1+2+3+4+ ... + t < n

(t+1)t/2 < n

t^2+t < 2n

4t^2+4t +1 < 8n +1

(t2 + 1)^2 < 8n + 1

t =0.5(8n+1)^0.5-0.5

2 求执行次数T(n)

T(n) = 1+t*2 = (8n+1)^0.5

3 求时间复杂度O(n)

O(n) = T(n) = (8n+1)^0.5 = O(n^0.5)

发表于 2020-07-30 10:18:29 回复(0)

大阳阳阳

这题的时间复杂度明显小于O(n), n就当是计算的次数如果k+=1的话,时间复杂度就是O(n) 但是这里的 i是不断增长的,

k就等于 1+2+3+4+...... 。计算次数明显小于 1+1+1+1+..... 所以直接选B就好啦。

发表于 2020-08-14 23:13:33 回复(0)

牛客917200502号

i = 1, 2, 3, 4, 5...

k = 1, 3, 6, 10, 15...

k = i*(i+1)/2

退出循环条件k>=n

i*(i+1)/2>=n

得i>(2n)1/2

复杂度为O(n^1/2)

发表于 2020-05-21 15:46:34 回复(0)

若水永远

三短一长选最长

发表于 2020-03-12 21:55:49 回复(0)

努力叭

发表于 2021-10-08 09:40:47 回复(0)

LW成霏

加是开根号，乘是取对数

发表于 2021-07-05 10:47:08 回复(0)

橘足轻重

k平方等于n k等于n的二分之一次方

发表于 2021-04-01 23:43:01 回复(0)

上岸吧_来个直推

那这个空间复杂度是多少，这个计算有规律吗

发表于 2021-03-20 12:19:52 回复(0)

杰拳道

发表于 2020-09-28 11:40:38 回复(0)

牛客294847222号

算法

发表于 2020-08-21 23:36:46 回复(0)

KelvinKelvin

请问 i 作为一个一直在变的量，出现在复杂度里，可以直接排除吗？

发表于 2020-03-14 00:09:34 回复(0)

coder

竟然没人吐槽这个代码的对齐

发表于 2019-12-28 04:35:39 回复(0)

少年歌行

用递推数列的思想求循环执行的次数：

k0=0；

当i>=1时

ki=k(i-1)+i;

累加法求数列通式:

k1=k0+1

k2=k1+2

......

kj=k(j-1)+j

累加得：

kj=k0+1+2+.....j=(1+j)*j/2;

列方程：kj=n；

即：j^2+j-2n=0;

解得：

j=(-1+-(1+8n)^0.5)/2

j是循环执行的次数，当n取极限时，才是用O（）表示的渐进时间复杂度

所以，n取极限得：

O(n^0.5)

编辑于 2019-11-15 17:26:21 回复(0)

提交观点

问题信息

复杂度

来自：小米2019秋招测试开...

上传者：小小

难度：

22条回答 1884收藏 9328浏览

下面程序段的时间复杂度是（） i = k = 0; whil

问题信息

热门推荐

相关试题