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

Question

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

根据我目前的理解，内循环将增加 5 的幂，就像我在下面的 table 中描述的那样，即当 i=1、j=1、当 i=5 时， j=5 等等。

我 | 1 | 5 |25 |125 |

j | 1 | 5 |25 |125 |

这使得 j 增加，如 5^0、5^1、5^2、5^3 等。使用高斯技巧，1+2+3+4...+n = (n² + n)/2 = n²/2 + n/2，这给出了 5^((n² + n)/2).

这是否使总运行时间为 O(log base(5) n)？

Answer 1

这里不能直接应用公式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 2

您必须从 m=0 到小于 2n 的 log5(n) 求和 5^m。所以运行时间在 O(n).

例如，如果 n=125，则总和为 156 (< 2n)。

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

Answer 3

我们将考虑内循环的迭代次数与外循环的索引值无关的循环

然后我们将尝试 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

内部：

(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)

最后从pattern可以看出我们计算的时间复杂度是O(n).

link 时间复杂度用几何级数求解证明： https://justpaste.it/15fhs

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

What is the time complexity of the following nested loop dependency?

big-o

for-loop

time-complexity

nested-loops