の 時間計算量 マージソートの O(n log n) 両方で 平均 そして 最悪の場合 。空間の複雑さ マージソート は の上） 。

マージソートの時間計算量分析:

次の用語を考慮してください。

T(k) = k 要素のソートにかかる時間
M(k) = k 要素をマージするのにかかる時間

したがって、次のように書くことができます

文字列置換すべてのJava

T(N) = 2 * T(N/2) + M(N)
= 2 * T(N/2) + 定数 * N

これらの N/2 要素はさらに 2 つに分割されます。それで、

T(N) = 2 * [2 * T(N/4) + 定数 * N/2] + 定数 * N
= 4 * T(N/4) + 2 * N * 定数
。 。 。
= 2^k* T(N/2^k) + k * N * 定数

ls コマンド、Linux

要素が 1 つになるまで最大分割できます。つまり、N/2^k= 1。 k = 対数 ₂ N

T(N) = N * T(1) + N * log₂N * 定数
= N + N * 対数₂N

したがって、時間計算量は次のようになります。 O(N * ログ ₂ N) 。

したがって、最良の場合、最悪の場合、および平均的な場合の時間計算量は同じです。

jsセット

マージソートの空間複雑性分析:

マージソート があります 空間の複雑さ の の上） 。これは、サイズの補助配列を使用するためです。 n 入力配列のソートされた半分をマージします。補助配列はマージされた結果を格納するために使用され、入力配列はソートされた結果で上書きされます。