首页 > 试题广场 >

下列程序段的时间复杂度是（ ...

[单选题]

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

count = 1；
for(k=1;k<2n;k*=2)
    for(i=1;i<4n;i+=2)
        count++;

```
O(n2)
```
```
O(8n2)
```
```
O(nlog2n)
```
```
O(n)
```

查看答案及解析

流浪猎人+

第一个循环指数增加，复杂度为log2n第二个循环复杂度n

编辑于 2019-09-04 22:16:53 回复(4)

牛客712245668号

上面的时间复杂度的表示还是较复杂，我们一般都使用大O表示法来简化表示时间复杂度。

1、复杂度为常数，如23，9999，等等都表示为O(1)

2、复杂度包含n时，省略系数与常数项，只取n的最高阶项

如：2n+45 为 O(n) ； 4n^3+6n^2+n 为O(n^3)

3、复杂度为对数时：如log5(n)、log2(n) 等等都表示为 O(logn)

4、省略低阶，只取高阶 (即取最大的)

如：logn+nlogn 表示为O(nlogn)

发表于 2022-12-03 10:02:26 回复(0)

logic/

发表于 2021-07-26 06:43:58 回复(0)

卢木木木

线性对数阶$O(nlogn)$
线性对数阶$O(nlogn) $，就是将时间复杂度为对数阶$O(logn)$的代码循环n遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了$O(nlogn)$，如下，
for(m=1; m<n; m++)
{
i = 1;
while(i<n)
{
i = i * 2;
}
}

发表于 2021-03-11 19:09:51 回复(0)