complexity-theory - 了解嵌套循环将运行多少次

Question

我试图理解以下代码中作为“n”的函数执行了“x = x + 1”语句的次数:

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

如果我没有记错的话，第一个循环执行n次，第二个循环执行n(n + 1)/2次，但是在第三个循环中我迷路了。也就是说，我可以指望它会被执行多少次，但是我似乎找不到公式或用数学术语来解释它。

你可以吗？

顺便说一句，这不是家庭作业或其他任何东西。我刚发现一本书，并认为这是一个有趣的概念。

Answer 1

考虑循环for (i=1; i <= n; i++)。看到这循环了n次很简单。我们可以这样画:

* * * * *

现在，当您有两个这样的嵌套循环时，您的内部循环将循环n(n + 1)/2次。请注意，这是如何形成三角形的，实际上，这种形式的数字称为 triangular numbers。

* * * * *
* * * *
* * *
* *
*

因此，如果将其扩展到另一个维度，它将形成一个四面体。由于我在这里不能做3D，因此可以想象每个图层都相互叠加。

* * * * *     * * * *     * * *     * *     *
* * * *       * * *       * *       *
* * *         * *         *
* *           *
*

这些称为 tetrahedral numbers，由以下公式生成:

n(n+1)(n+2)
-----------
     6

您应该能够通过一个小的测试程序来确认确实是这种情况。

如果我们注意到6 = 3 !，那么看到 how this pattern generalizes to higher dimensions并不难:

n(n+1)(n+2)...(n+r-1)
---------------------
         r!

在此，r是嵌套循环的数量。