答えて
最も内側のループは明らかにj
回実行されます。それは1時間単位の価値の操作が含まれていると仮定すると、これは以下のようになります。
T_inner(j) = j
真ん中のループ、すなわちi
回、
T_middle(i) = Sum {j from 1 to i} T_inner(j)
= Sum {j from 1 to i} j
= i/2 * (1 + i)
最後に
実行されます:
T_outer(n) = Sum {i from 1 to n} T_middle(i)
= Sum {i from 1 to n} (i/2 * (1 + i))
= 1/6 * n * (1 + n) * (2 + n)
= 1/6 n^3 + 1/2 n^2 + 1/3 n
とし、これは明らかですO(n^3)
。
注:これは、最も内側のブロックの演算のみをカウントします。ループを実行するのに必要な操作は無視されます。しかし、それらを含めると、時間の複雑さは同じであることがわかります。
ありがとう! @NicoSchertler、それは動作します:) –
通常、アルゴリズムの複雑さが話題になると、彼らはループに必要な操作を考慮しますか、それとも常に無視されますか? –
ループを維持するために必要な操作は、反復回数(初期化操作に加えて)に常に比例します。したがって、これは内側のブロックに一定量を加えることに似ています。結局のところ、これは複雑さを変えない。 –
- 1. 与えられたコードの時間複雑さを理解する
- 2. Pythonでのdict.keys()の時間の複雑さは何ですか?
- 3. 次のプログラムの時間の複雑さは何ですか?
- 4. 私のコードの時間の複雑さは何ですか?
- 5. 私のコードの時間の複雑さは何ですか
- 6. このアルゴリズムの時間の複雑さは何ですか
- 7. 与えられた時間の複雑さでアルゴリズムを作成してください
- 8. HTML DOMルックアップの時間の複雑さは何ですか
- 9. C:qsort関数の時間の複雑さは何ですか?
- 10. 与えられたコードの複雑さを見つける
- 11. パスカル・トライアングル・アルゴリズムの時間複雑さは何ですか?
- 12. Linq OrderBy()の時間複雑さは何ですか?ThenBy()メソッドシーケンス?
- 13. 時間の複雑さと
- 14. heapqライブラリの関数の時間の複雑さは何ですか
- 15. スキーム内の 'assoc'関数の時間の複雑さは何ですか?
- 16. 時間の複雑さ(入れ子にされたループ)
- 17. 時間の複雑さと空間の複雑さ、空間の複雑さの計算方法
- 18. 時間の複雑さは、Python
- 19. 再帰アルゴリズムの時間複雑さと空間の複雑さはどのようなものですか?オペレーター?
- 20. このコードの実行時の複雑さは何ですか?
- 21. Pythonのdeepcopy()の実行時の複雑さは何ですか?
- 22. 与えられた時間から1秒を引く
- 23. 時間複雑
- 24. 時間複雑
- 25. 時間複雑
- 26. Pythonでzip()の時間の複雑さはどのくらいですか?
- 27. 与えられたテーブルから燃料の詰め替え時間を取得
- 28. 与えられた時間に何分が使用されたかを計算します。
- 29. JavaScriptのparseInt()の時間の複雑さはどのくらいですか?
- 30. 次の式の時間の複雑さはどのくらいですか?
あなたはこの問題に対して何をしましたか?たとえば、 'j'の複雑さと正確な公式を述べることができますか?複雑さを明白にする 'k'の正確な公式については、[四面体数](https://en.wikipedia.org/wiki/Tetrahedral_number)を参照してください。 –
n^3のように見えます。私は時間の複雑さにかなり悪いですが、私は間違っている可能性があります。また、これらのタグのほとんどは無関係です。 – byxor
提案通りにタグを削除しました。 @BrandonIbbotson –