c++ - 三重嵌套循环中的这条语句执行多少次？

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

从这里，我们得到

总和 (i 从 1 到 n) i(i + 1) / 2

= (1/2) sum (i from 1 to n) (i ² + i)

= (1/2) (sum (i from 1 to n)i ² + sum (i from 1 to n) i)

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

然后，您可以尝试简化该多项式以获得干净、精确的值。如果您只需要渐近上限，则为 Θ(n ³ )。

根据Wolfram Alpha的说法，这是

n ³ / 6 + n ² / 2 + n / 3

希望这可以帮助！