首页 > 试题广场 >

下面代码的时间复杂度是： void func(i

[单选题]

下面代码的时间复杂度是：

void func(int n) {
  int v = 1;
  while (v < n) {
    for (int i=1; i < v;) {
      i+=2;
    }
    v*=2;
  }
}

```
O(logn)
```
```
O(nlogn)
```
```
O(n^2)
```
```
O(n)
```

查看正确选项

pein531

外层循环执行log2(n)次，内层循环的循环次数是一个等比数列：1,2,4,...，因此复杂度就是对这个等比数列的前log2(n)项进行求和，结果为(1-2^log2(n))/(1-2)=n-1，复杂度为O(n)

发表于 2021-01-04 11:57:26 回复(0)

理想汽车部门直推官

题解：首先根据外层循环可知，总共循环次数是log₂n次，内层循环与第i次有关系，是第i次的2^i/2次，那么，就是一个等比数列求和，等比数列为2^1/2+2^2/2+2^3/2+。。。。。。,就是1,2,4,8,16，。。。。。。，所以，一共log₂n项，计算可知：（1-2^log₂n）/1-2，化简可知的n-1，故为O（n）次

发表于 2020-09-04 15:50:25 回复(0)