三个相互依赖的嵌套 for 循环的渐近分析

Question

我要分析的代码片段如下：

int sum = 0;
for (int i = 0; i < n; i++)
   for (int j = 0; j < i * i; j++)
      for (int k = 0; k < j; k++)
         sum++;

我知道第一个循环的时间复杂度为 O(n)，但这就是我所得到的。我认为第二个循环可能是 O(n^2) 但我越想它就越没有意义。任何指导将不胜感激。

Answer 1

第一个循环执行 n 次。每次，值i都会增长。对于每个这样的 i，第二个循环执行 i*i 次。这意味着第二个循环执行 1*1 + 2*2 + 3*3 + ... + n*n 次。

这是平方和，其公式为 众所周知。因此，我们有第二个循环执行 (n(1 + n)(1 + 2 n))/6 次。

因此，我们知道 j 总共有 (n(1 + n)(1 + 2 n))/6 个值，对于每个值，第三个循环将执行 1 + 2 + ... + j = j(j+1)/2 次。实际上计算第三个循环总共执行了多少次是非常困难的。幸运的是，您真正需要的只是函数阶数的最小上限。

您知道，对于 j 的每个 (n(1 + n)(1 + 2 n))/6 值，第三个循环将执行 less超过 n(n+1)/2 次。因此，您可以说操作 sum++ 将执行少于 [(n(1 + n)(1 + 2 n))/6] * [n(n+1)/2 ] 次。经过快速心算，这相当于一个最大次数为 5 的多项式，因此您的程序是 O(n^5)。

Answer 2

int sum = 0;                  
for (int i = 0; i < n; i++)            // Let's call this N
   for (int j = 0; j < i * i; j++)     // Let's call this M
      for (int k = 0; k < j; k++)      // Let's call this K
         sum++;

N 是整个程序的步骤数，M 是两个内部循环执行的步骤数，最后 K 是最后一个循环执行的步骤数。

容易看出K=j，需要j步来做。

Then M = Sum(j=0,i^2,K) = Sum(j=0, i^2, j)

（第一个参数是迭代器，第二个参数是上限，最后一个参数是我们要添加的参数）

这实际上是 n 个数字到 i*i 的总和。这意味着我们可以应用公式 ((n+1)*n)/2

 M = Sum(j=0,i^2,j) = ((i^2+1)*(i^2))/2 = (i^4 + i^2)/2

 N = Sum(i=0, n, M) = 1/2 * ( Sum(i=0, n, (i^4)) + Sum(i=0, n, (i^2)) )

这些都是众所周知的公式，玩一会儿后您会得到：

 N = (n^5)/10 + (n^4)/4 + (n^3)/3 + (n^2)/4 + n/15

这应该是循环所采取的确切步数，但如果您有兴趣O 表示法，您可以注意到 n^5 是最强增长部分，因此解决方案是 O(n^5)

Answer 3

如果您有条不紊地使用西格玛表示法，您最终将得到以下结果：

Answer 4

尝试计算内部循环执行了多少次：

中间循环运行

0*0 times when i == 0
1*1 times when i == 1
2*2 times when i == 2
...
n*n = n^2 times when i == n.

所以它是O(n^2)。