for-loop - 三个相互依赖的嵌套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次。

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

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

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