マージソートアルゴリズムのベスト実行時間と平均実行時間

Question

マージソートアルゴリズムの実行時間がBig Omega（n log n）で、平均実行時間がBig theta（n log n）である理由を説明するにはどうすればよいですか？

Answer 1

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

http://en.wikipedia.org/wiki/Analysis_of_algorithms