マージソートの繰り返し - 必要説明

Question

これは、マージソート手順のワーストケース実行時間T（n）の繰り返しです。

Tは何ですか？

理由2T（N/2）？

どの操作がO（n）であるか？簡単にするため

Answer 1

各分割工程は、2つの部分問題は、サイズの両方を正確にN/2が得られるように、nが2の累乗であると仮定する。

ベース場合は、n = 1の場合

≥2 n個のマージソートステップの時間に発生：

ディバイド：だけ定数かかりpとRの平均値としてのqを計算します時間Θ（1）である。

理由2T（N/2）？

征服：再帰的2T（N/2）である2つの副問題、サイズN/2の各々を、解決します。動作について

はO（N）ですか？

組み合わせ：n要素のサブアレイに MERGEはΘ（n）は時間を要します。

は加算それらがΘ（n）は、Nに線形な関数を与えます。したがって、マージソート実行時間の再発は、

です。