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

ここから、

合計 (1 から n までの i) i(i + 1) / 2

= (1/2) 合計 (1 から n までの i) (i ² + i)

= (1/2) (合計 (1 から n までの i)i ² + 合計 (1 から n までの i) i)

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

次に、その多項式を単純化して、クリーンで正確な値を得ることができます。漸近的な上限だけが必要な場合は、Θ(n ³ ) です。

Wolfram Alphaによると、これは

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

お役に立てれば！