マージソートアルゴリズムの実行時間がBig Omega(n log n)で、平均実行時間がBig theta(n log n)である理由を説明するにはどうすればよいですか?マージソートアルゴリズムのベスト実行時間と平均実行時間
-1
A
答えて
0
Big Omegaでは下位の項や定数は無視され、通常Big Omegaは上限や最悪のシナリオを記述するために使用されます。ビッグセータは、下限と上限、および/またはベストケース、平均ケース、最悪ケース、特定のケースとして適格でなければなりません。
小さなグループで何らかの種類の並べ替えを使用するハイブリッドではなく、移動の数は同じです。n⌈log2(n)⌉(⌈⌉は整数の上限です)。比較の数は、最悪のケースではn⌈log2(n)⌉よりも小さく、最善のケースでは約1/2であるため、定数の差のみが変化します。データセット要素がレジスタに収まる場合(整数の配列のソートなど)、比較時間はメモリアクセス時間によって隠されることがあります(比較は全体の時間にほとんど影響を与えません)。外部マージソート(大容量ファイルのソートなど)を行う場合、比較時間はデバイスの読み書き時間によって隠されることがあります。
のWiki記事:
http://en.wikipedia.org/wiki/Big_O_notation
http://en.wikipedia.org/wiki/Time_complexity
http://en.wikipedia.org/wiki/Computational_complexity_theory
関連する問題
- 1. リニアサーチアルゴリズムの平均実行時間
- 2. カーネルの起動から実行までの平均時間は?
- 3. CPUパイプライン:平均命令実行時間の求め方
- 4. 時間の2つの日付の平均の平均時間
- 5. Bash、複数の平均実行時間の平均実行時間を取得するにはどうすればよいですか?
- 6. TextRank実行時間
- 7. プロシージャ実行時間
- 8. ハッシュコリジョンリニアプロービング実行時間
- 9. FlexUnit実行時間
- 10. Python:Thread実行時間
- 11. 実行時間viewcontroller
- 12. Rパッケージと実行時間
- 13. グループ化と実行時間
- 14. Movement EquationDeltaHeight =(Sin(実行時間+ DeltaTime) - Sin(実行時間));
- 15. 実行時間VSコンパイル時間(.NET)
- 16. SQLクエリ時間 - 実行時間
- 17. データマトリックスの時間平均
- 18. SQLクエリの平均時間
- 19. 平均時間のパフォーマンスカウンタタイプ
- 20. タイプとnewtypeのコンパイル時間と実行時間の差
- 21. 実行時間の比較
- 22. Ocamlの実行時間
- 23. x時間の実行コード
- 24. アルゴリズムのC++実行時間
- 25. kshスクリプトの実行時間
- 26. SSISの実行時間
- 27. javaアップデートプロパティファイルの実行時間
- 28. GCDアルゴリズムの実行時間?
- 29. Clojureプログラムの実行時間
- 30. RadixSortアルゴリズムの実行時間