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

Question

我试图理解语句"x = x + 1"在下面的代码中执行了多少次，作为"n"的函数:

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次。注意这是如何形成一个三角形的，事实上，这种形式的数被称为三角形数。

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

如果我们把它扩展到另一个维度，它会形成一个四面体。因为我不能在这里做3D，想象一下每个图层都是相互叠加的。

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

这些被称为四面体数，它们由以下公式产生:

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

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

如果我们注意到6 = 3!，不难看出这个模式是如何推广到更高维度的:

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

这里，r是嵌套循环的数目。

Answer 2

第三个内循环与第二个内循环相同，但你的n是一个公式。

那么，如果外部循环是n乘以…

第二个循环是n(n+1)/2乘以…

你的第三个循环是....

(n(n+1)/2)((n(n+1)/2)+1)/2

这是蛮力的，肯定可以简化，但它只是算法递归。

Answer 3

数学公式在这里

复杂度为O(n^3)

Answer 4

这个数字等于三个组{a,b,c}的个数，其中a<=b<=c<=n
因此，它可以表示为与重复的组合。在这种情况下，重复组合的总数是:n(n+1)(n+2)/6

Answer 5

1 + (1+2) + (1+2 + 3) +......+(1 + 2 + 3 +…n)

Answer 6

你知道第二个循环执行了多少次所以可以用一个循环代替前两个循环，对吧?像

for(ij = 1; ij < (n*(n+1))/2; ij++)
   for (k = 1; k <= ij; k++)
      x = x + 1;

应用与第一个相同的公式，其中'n'这次是n(n+1)/2，你会得到((n(n+1)/2)*(n(n+1)/2))/2 -乘以x = x+1执行