首页 > 试题广场 >

下面程序的时间复杂度是？

[单选题]

下面程序的时间复杂度是

for(int i=1;i<n;i*=3)             
   for(int j=i/3;j<i;j++){             
        Foo();                   
}

已知n是一个正数，Foo()时间复杂度为0(1),上述代码的时间复杂度是（）

```
O(logn)
```
```
O(n)
```
```
O(n*log(n))
```
```
O(n^2)
```

推荐

晓宇大美女~

编辑于 2016-04-13 20:32:01 回复(24)

yql

外层i的取值为 1，4，7，10，13……i 有差不多N/3个取值

对与外侧的每个i能对于的执行次数 1，3，5，7， 9……（i-1）-i/3+1=(2i)/3,每次增加的次数是2次

i的最大值与n接近。（ 1+ 2n / 3）*n/3 最高次方为2 所以时间复杂度为O(N^2)

发表于 2015-09-17 10:14:42 回复(3)

大脸猫联萌

编辑于 2017-03-29 11:57:08 回复(0)

searchcoding

i=1时，j=1/3=0,执行1次,j 取0

i=3时，j=1;j<i;执行2次，j取 1,2

i=9时：j=3，j取[3,8],执行6次

总结：

从i每次乘3，但j是初始化为i/3，可以理解为j是从上一轮循环的i开始执行内循环，直到j为当前i-1;

内外层合在一起就是

for(i=0;i<n;i++)

{

foo();

}

发表于 2016-01-25 11:57:47 回复(0)

blnik

外层循环，i的变化大概是 1 ,3 ,9,27 ,…… n（假设n=3^k，这个不影响复杂度的分析）

内部循环，j从i/3到i，每次+1，大概需要比较的次数就是 2i/3，那就是 2/3( 1, 3, 9 ,27 ,……,n)

sum（内部循环次数）=(3^(k+1)-1)/3 =(3n-1)/3 所以是O(n)

发表于 2015-10-11 15:54:53 回复(0)

t^t999999

O(n^2)吧？

发表于 2015-09-16 17:04:42 回复(6)

Wrong Answer

把这个遍历过程想象成一个有n个结点的满三叉树。那么就是层序遍历一边这个三叉树的复杂度。

发表于 2016-08-23 20:24:05 回复(0)

风＊继续吹

其实就是个等比数列求和，公比是3，外部的循环次数就是数列的项数，总共是log3(n)

根据等比数列的求和公式 sum = (1 - 3^(log3(n))) / (1 - 3) 约为 n/2

可能不是很精确，但是复杂度就是O(n)

发表于 2015-10-31 19:23:52 回复(0)

妮可

考虑循环次数， i=1时，j可以等于0，执行1次； i变为3，j可以等于1，2，执行2次； i变为9，j可以取i*2/3次，也就是6次； ……… 所以总的执行次数是， 1*2/3 + 3*2/3 + 9*2/3 + ………+ n*2/3 也就是2/3*(1+3+9+……+n) 用等比数列求和公式。所以等于，2/3 * (n-1)/(3-1) 也就是(n-1)/3，所以是O(n)

发表于 2016-03-24 11:54:38 回复(0)