三个相互依赖的嵌套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时间.

因此,我们知道总共将存在(n(1 + n)(1 + 2 n))/6j的值,并且对于每个值,第三个循环将执行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).