以下嵌套循环依赖关系的时间复杂度是多少？

Question

count=0; 
for(i=1;i<=n;i*=5) 
    for(j=1;j<=i;j++) 
     count++; 

根据我目前所了解的内容，内环将增加5的幂数，就像我在下面的表格中所描述的那样，即当i = 1，j = 1时，当i = 5，j = 5和等等。

---

i | 1 | 5 | 25 | 125 |

---

j | 1 | 5 | 25 | 125 |

---

这使j增加，如在5^0,5^1,5^2,5^3等等。使用高斯特技，1 + 2 + 3 + 4 ... + n =（n 2 + n）/ 2 = n 2/2 + n/2，这给出了5 ^（（n 2 + n）/2）。

这是否使总运行时间O（log base（5）n）？

Answer 1

我们会考虑循环，其中内循环的迭代次数是独立于外环的指数值

然后我们会尽量的n不同的情况，以找出正确的模式：

n = 5 

外：1 5

内：

i = 1：1次

i = 5：5次

1 + 5 = 6次，k = 2

n = 25 

外：1 5 25

内：

i = 1：1次

i = 5：5次

i = 25：25倍

1 + 5 + 25 = 31次，k = 3

n = 125 

外：1 5 25 125

内：

1 + 5 + 25 + 125 = 156次，k = 4

inn ER：

(1 + ... + n/5^2 + n/5^1 + n/5^0) 

n(1/n + ... + 1/5^2 + 1/5^1 + 1/5^0) 

n(1/5^k-1 + ... + 1/5^2 + 1/5^1 + 1/5^0) 

O(n(1/5^k-1 + ... + 1/5^2 + 1/5^1 + 1/5^0)) 

= O（n）的

最后你可以从我们计算时间复杂度为为O（n）格局看。

链接，时间复杂度解决方案的论证与等比数列： https://justpaste.it/15fhs

Answer 2

这里不能直接应用公式1 + 2 + … + n = n(n+1)/2。 5^0 + 5^1 + … + 5^m和5^(0 + 1 + … + m)是两个完全不同的东西。

该系列5^0 + 5^1 + … + 5^m是geometric series。使用式应该是

这意味着5^0 + 5^1 + … 5^m = O(5^m)。还请注意5 ^m = n。

类=>

Answer 3

您必须从m = 0到小于2n的log5（n）之和5^m。所以运行时间在O（n）。

例如，如果n = 125，则总和为156（< 2n）。

对于任何n，总和小于2n。