algorithm - 次のコードの成長の順序は?

Question

次の質問を受けましたが、正しい答えを決めることができません。

for (int i=1; i<=n/2; i++)
  for(int j=i; j<=n-i;j++)
    for(int k=i;k<=j;k++)
      x++;

n の関数としての x の成長の順序は何ですか?

1. Ω(n^3)。
2. Θ(n^2.5)
3. Θ(n^2)
4. Ο(nlogn)
5. 上記のどれでもない

私はそれを理解することができました：

T(n) = n*(n-1) + T(n-2)

しかし、これは成長の順序を理解するのに実際には役立ちません。多分それを見つけるより良い方法がありますか？

Answer 1

これは宿題のように見えるので、ヒントだけを示します。

1) 内側のループがあるとします。i と j の関数として、内側のループを何回通過しますか? ループの反復ごとに実行される操作の数は? 合計で何回の操作を実行する必要がありますか?

2) ここで、内側の 2 つのループだけがあるとします。i と n の関数として、外側のループを何回通過しますか? 外側のループを通過するたびに、内側のループを何回通過しますか? (ヒント: これは j が何であるかによって異なるはずです) 合計でいくつの操作を実行する必要がありますか?

3) これで、問題全体を見る準備が整いました。内側の 2 つのループを (n の関数として) 何回通過し、各反復で何回の操作を実行する必要がありますか? 合計で何回の操作が実行されましたか? (それがあなたの答えです)

---

さて、これは宿題ではないとおっしゃいましたが、実際は思ったより難しいので、答えだけお伝えします。

各内部ループは時間 j - i で実行されます。

2 番目のループは次の時間で実行されます (i - i) + (i + 1 - i) + ... + (i + n - 2i - i) = 1 + 2 + ... + (n - 2i) = (n - 2i)(n - 2i + 1)/2、数学的帰納法による。

成長の次数を計算する場合、1 項は n 項に比べて非常に小さいため、外側のループはおよそ n^2/2 + (n-2)^2/2 + (n-4)^2/2 + で実行されます。 ... + 1/2。

これは、1^2 + 2^2 + ... + n^2 の約 4 分の 1 であり、これは帰納法により n(n+1)(2n+1)/6 になります。したがって、成長の順序は Omega(n^3) です。

Answer 2

誰かが上記のコメントで印刷ステートメントに言及しました。ここにあるいくつかの：

n = 20 --> x = 715
n = 21 --> x = 825
n = 22 --> x = 946
n = 23 --> x = 1078
n = 24 --> x = 1222
n = 25 --> x = 1378
n = 26 --> x = 1547
n = 27 --> x = 1729
n = 28 --> x = 1925
n = 29 --> x = 2135
n = 30 --> x = 2360
n = 31 --> x = 2600
n = 32 --> x = 2856
n = 33 --> x = 3128
n = 34 --> x = 3417
n = 35 --> x = 3723
n = 36 --> x = 4047
n = 37 --> x = 4389
n = 38 --> x = 4750
n = 39 --> x = 5130
n = 40 --> x = 5530

Answer 3

私はそれを計算しようとしました、そして私は見つけましたT(n) = (13/12) * n * (n² + 3*n + 2)（数学の規則！）。だからそれは立方体です。->回答1。

編集：計算にエラーがありました。本当の答えはT(n) = n * (n + 2) * (2*n - 1) / 24：

しかし、それは立方体のままです。