这个语句在三重嵌套循环中执行多少次？

Question

这是我的问题

for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        for(k=1;k<=j;k++)
            x++;

现在,我想知道语句x ++; 多少次迭代？我想知道解决方案的公式.

Answer 1

您正在寻找以下总和的值:

  Sum(i from 1 to n)
      Sum (j from 1 to i)
          Sum (k from 1 to j)
              1

从内到外工作:

  Sum(i from 1 to n)
      Sum (j from 1 to i)
          Sum (k from 1 to j)
              1
= Sum(i from 1 to n)
      Sum (j from 1 to i)
          j

= Sum(i from 1 to n)
      i(i + 1) / 2

从这里,我们得到

sum(i从1到n)i(i + 1)/ 2

=(1/2)和(i从1到n)(i ² + i)

=(1/2)(sum(i从1到n)i ² + sum(i从1到n)i)

=(1/2)(n(n + 1)(2n + 1)/ 6 + n(n + 1)/ 2)

然后,您可以尝试简化该多项式以获得干净,精确的值.如果你只需要渐近上界,它就是Θ(n ³).

根据Wolfram Alpha的说法,这是

Ñ ³ /6 +Ñ ² /2 + N/3

希望这可以帮助!