0
私はこのアルゴリズムがo（nlogn）の時間複雑さを持っていることを知っていますが、私たちがマージステップだけを話すならば、これは依然としてo（nlogn）ですか？または、それはo（logn）に還元されていますか？ 2番目の答えは答えだと思いますが、まだ配列のすべての要素に触れなければならないので、複雑さは同じであると思われますmergesortのマージ・ステップの複雑さはどのくらいですか？
乾杯！
A
答えて
0
「分割」ステップはo（logn）を取るものであり、1つをマージするのはo（n）であり、これは単にコメントを介して実現されます。
+1
分割ステップではO（log n）時間はかかりません。それには時間O（n）もかかります。 O（log n）係数は、すべてのレベルの再帰ですべてのマージを実行するために必要な作業を集計することによって発生します。 – templatetypedef
関連する問題
- 1. Mergesort：マージ操作の最後のステップは何ですか？
- 2. mergesortの複雑さO（nlogn）+ O（n）？
- 3. 私のソリューションの複雑さはどのくらいですか？
- 4. このアルゴリズムの複雑さはどれくらいですか
- 5. クイックユニオンの時間複雑度はどのくらいですか？
- 6. JavaでのStringBuilder.append（）の複雑さはどのくらいですか？
- 7. Pythonでzip（）の時間の複雑さはどのくらいですか？
- 8. グラフデータベースでの検索クエリの複雑さはどのくらいですか？
- 9. JavaScriptのparseInt（）の時間の複雑さはどのくらいですか？
- 10. 次の式の時間の複雑さはどのくらいですか？
- 11. clojureのカウント関数の複雑さはどのくらいですか？
- 12. boost :: hana :: tupleの要素アクセスの複雑さはどのくらいですか？
- 13. ツリートラバーサルの時間の複雑さはどのくらいですか？
- 14. heapifyUp（）メソッドの時間の複雑さはどのくらいですか？
- 15. yieldからのツリートラバーサルの時間複雑度はどのくらいですか？
- 16. モデルはどのくらい複雑になりますか？
- 17. HashSetから取得されるストリームフィルタの複雑さはどのくらいですか？
- 18. Neo4jの検索クエリの時間複雑度はどのくらいですか？
- 19. この順列アルゴリズムの空間複雑度はどのくらいですか？
- 20. このアルゴリズム（コード）の時間複雑度はどのくらいですか？
- 21. 次のコードの時間的複雑度はどのくらいですか？
- 22. このプログラムフラグメントの時間複雑度はどのくらいですか？
- 23. この関数の時間複雑度はどのくらいですか？
- 24. このdo-whileループの時間複雑度はどのくらいですか？
- 25. この関数の時間複雑度はどのくらいですか？
- 26. javaのlastIndexOfの時間複雑度はどのくらいですか？
- 27. この擬似コードの時間複雑度はどのくらいですか？
- 28. 複雑なマージ
- 29. アルゴリズム全体の時間複雑度はどのくらいですか？
- 30. 暗号ハッシュ関数の時間複雑度はどのくらいですか？
これは、使用しているマージによって異なります。伝統的に誰もがO（n）マージを使います。私はO（lg n）マージを見て幸せ以上になります。 – silentboy
あなたは絶対に正しいです。 「分割」ステップはo（logn）を取るステップであり、1つをマージするステップはo（n）である。私は時間の複雑さを混乱させていた。これは私の質問を解決します。ありがとう!!! – nelt22
配列の分割ステップ時間の複雑さはO（1）です。問題は、トップダウンマージソートのlog2（n）レベル、ボトムアップマージソートのlog2（n）反復、および各レベルの再帰または各反復のマージのためのO（n）レベルを必要とするため、合計O（n log（n））である。 – rcgldr